Skip to content

Latest commit

 

History

History
379 lines (280 loc) · 10.8 KB

7.quick_sort.md

File metadata and controls

379 lines (280 loc) · 10.8 KB
Raw

快速排序及其优化

总的思想就是每次取一个数，比他小的就放前面，比他大的放后面

选择基数+partition

不断的循环

这是一个递归的过程

快排的思想牛逼就牛逼在它每次都能将数据的$n!$种排列组合瞬间降到$\frac{n!}{2}$

因为他不是分割成了两段么，并且两段都有确定的大小关系

就极大的降低了数据复杂度

因为每次都是分成了1/2 所以一段是logn 但是遍历这n个就成了nlogn

排序算法可以降低系统的熵（复杂度）

从c++ STL中学习快速排序

WHY NOT 堆排序？

堆排序比较稳定，时间复杂度恒定在$nlogn$

并且需要额外的二叉树空间

快排在理想状态下(一次partition)，可达到$logn$

插入排序在数字基本有序的情况下可达到$n$

STL中的sort是将内省排序和插入排序结合了起来

内省排序

我们知道快速排序会因为基数的选择而掉入陷阱，最垃圾达到$n^{2}$

那么就设定一个阈值为$2logn$，超过这个值就启用堆排序

WHY $2logn$ ? 因为要比logn大一丢丢

这样既能保证最坏$nlogn$，又能最快$logn$

具体做法

  1. 单边递归法

    将传统的快排进行

    quick_sort(num, l, mid);
quick_sort(num, mid + 1, r);

    变成单边递归，只递归左边，这就相当于减小了一半的开销-相当于减去了二叉树的右子树。右边用循环做。

    quick_sort(num, l, mid);
r = mid - 1;//有点像二分哈哈

  2. 无监督partition法:

    即将快排递归函数的边界条件去掉用其他的方式替代，这样能避免它进入死循环

    少了个判断

  3. 三点取中法:

    partition时取base,取first, first + (last - first) / 2, last - 1中间的值

  4. 小数据规模，停止快排过程

  5. 插入排序进行收尾

c++中的sort

混合排序：快速$(nlogn-n^2)$+堆$(nlogn)$

在递归quick_sort的时候记录一个深度阈值，如果超过这个阈值$(x \ nlogn) 一般取2 \ nlogn$就用堆排序。

这种情况下快排每次选数都选不到好的数，导致快排退化到$n^2$

实际实现的时候源码还将待排序序列分成了若干份，每份长__stl_threshold,即16

对于份之间即宏观上用混合排序，份内部用插入排序

const int __stl_threhold=16;         // 阈值，用于评估序列大小

// 千万注意： sort() 只适用于 RandomAccessIterator
template <class RandomAccessIterator>
inline void sort (RandomAccessIterator first, RandomAccessIterator last) {
  if (first != last) {
      // 内省排序
      // 是分成若干个大小为16的小块分别进行内省
      // 最后一个选项就是2logn
    __introsort_loop (first, last, value_type(first), __lg (last - first) * 2);
      // 最后的插入排序
    __final_insertion_sort (first, last);
  }
}

//__lg() 用来控制分割恶化的情况。
// 找出 2^k <= n 的最大值 k 。例， n=7 ，得 k=2 ， n=20 ，得 k=4 ， n=8 ，得 k=3 。
template <class Size>
inline Size __lg (Size n) {
  Size k;
  for (k = 0; n > 1; n >>= 1) ++k;   
  return k;
}

// 完成后将返回母函数 sort() 在进入 __final_insertion_sort() 最终完成排序
template <class RandomAccessIterator, class T, class Size>
void __introsort_loop (RandomAccessIterator first,
                      RandomAccessIterator last, T*,
                      Size depth_limit) {
  // 以下， __stl_threshold 是个全局常数，稍早定义为 const int 16 。
  // 判断序列大小，如果小于等于 16 使用 Quick Sort 的排序，留给 Insertion Sort 最终完成排序
  while (last - first > __stl_threshold ) {
    if (depth_limit == 0) {               // 至此，切割恶化，改用 heapsort
      partial_sort (first, last, last);    // partial_sort 是以 Heap Sort 实现
      return;
    }
    --depth_limit;
    // 以下是 median-of-three partition ，选择一个够好的枢轴并决定切割点。
    // 切割点将落在迭代器 cut 身上。
    RandomAccessIterator cut = __unguarded_partition
      (first, last, T( __median (*first, *(first + (last - first)/2),
                               *(last - 1))));
    // 对右半段递归进行 sort.
    __introsort_loop (cut, last, value_type(first), depth_limit);
    last = cut;
    // 现在回到 while 循环，准备对左半段递归进行 sort.
    // 这种写法可读性较差，效率并没有比较好。
  }
}

// 以插入排序完成最后的排序
template <class RandomAccessIterator>
void __final_insertion_sort (RandomAccessIterator first,
                            RandomAccessIterator last) {
  if (last - first > __stl_threshold ) {
    // 分为两段前者调用插入排序，因为后段的元素总是比前段大（由 Quick Sort 性质可知），所以先
    // 调用前者完成前段排序，然后将后段从尾部遍历的方式插入已序的元素中
    __insertion_sort (first, first + __stl_threshold);
      // 无监督的插入排序
      // 因为前半段的已经排序完了
    __unguarded_insertion_sort (first + __stl_threshold, last);
  }
  else
    __insertion_sort (first, last);
}

template <class RandomAccessIterator>
inline void __unguarded_insertion_sort (RandomAccessIterator first,
                                RandomAccessIterator last) {
  __unguarded_insertion_sort_aux (first, last, value_type(first));
}

template <class RandomAccessIterator, class T, class Compare>
void __unguarded_insertion_sort_aux (RandomAccessIterator first,
                                    RandomAccessIterator last,
                                    T*, Compare comp) {
  for (RandomAccessIterator i = first; i != last; ++i)
    __unguarded_linear_insert(i, T(*i), comp);
}

// 对指定区域完成插入排序
template <class RandomAccessIterator>
void __insertion_sort (RandomAccessIterator first, RandomAccessIterator last) {
  if (first == last) return;
  for (RandomAccessIterator i = first + 1; i != last; ++i)   // 外循环
    __linear_insert (first, i, value_type(first));    // first,i 形成一个子范围
}

template <class RandomAccessIterator, class T>
inline void __linear_insert (RandomAccessIterator first,
                                  RandomAccessIterator last, T*) {
  T value = *last;      // 记录尾元素
  if (value < *first) { // 尾比头还小（那就别一个个比较了，一次做完…）
    copy_backward (first, last, last + 1); // 将整个范围向右递移一个位置
    *first = value;      // 令头元素等于原先的尾元素值
  }
  else
     __unguarded_linear_insert (last, value);
}

// 由末尾遍历，将数据插入到已序元素中去。
template <class RandomAccessIterator, class T>
void __unguarded_linear_insert (RandomAccessIterator last, T value) {
  RandomAccessIterator next = last;
  --next;
  while (value < *next) {  
    *last = *next;      
    last = next;        
    --next;             
  }
  *last = value;
}

// 传回 a,b,c 之居中者
template <class T>
inline const T& __median (const T& a, const T& b, const T& c) {
  if (a < b)
    if (b < c)      // a < b < c
      return b;     
    else if (a < c) // a < b, b >= c, a < c
      return c;
    else
      return a;
  else if (a < c)   // c > a >= b
    return a;       
  else if (b < c)       // a >= b, a >= c, b < c
    return c;
  else
    return b;
}

// 无监督的partition
// 特定条件下免去边界检验条件也能正常运行
template <class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition (RandomAccessIterator first,
                                           RandomAccessIterator last,
                                           T pivot) {
  while (true) {
    while (*first < pivot) ++first;    // first 找到 >= pivot 的元素，就停下来
    --last;                     // 调整
    while (pivot < *last) --last; // last 找到 <= pivot 的元素，就停下来
    // 注意，以下 first < last 判断动作，只适用于 random iterator
    if (!(first < last)) return first;    // 交错，结束循环。
    iter_swap (first, last);               // 大小值交换
    ++first;                       // 调整
  }
}

参考

自己实现快速排序

void quick_sort_v1(vector<int> &nums, int l, int r) {
    int x = l, y = r, z = nums[l];
    while (x < y) {
        while (x < y && nums[y] >= z) y--;
        if (x < y) nums[x++] = nums[y];
        while (x < y && nums[x] < z) x++;
        if (x < y) nums[y--] = nums[x];
    }
    nums[x] = z;
    quick_sort_v1(nums, l, x - 1);
    quick_sort_v1(nums, x + 1, r);
    return ;
}
void quick_sort_v2(vector<int> &nums, int l, int r) {
    while (l < r) {
        int x = l, y = r, z = nums[l];
        while (x < y) {
            while (x < y && nums[y] >= z) y--;
            if (x < y) nums[x++] = nums[y];
            while (x < y && nums[x] <= z) x++;
            if (x < y) nums[y--] = nums[x];
        }
        // 一次partition之后x，y都在同一个位置
        nums[x] = z;
        // 右侧还用递归
        quick_sort_v2(nums, x + 1, r);
        // 但是因为重设了r的值为左侧区间
        // 并且满足while循环条件
        // 左侧相当于用循环做
        // 这样就是相当于在一层的栈空间内完成
        // 少了一倍的栈空间展开
        r = x - 1;
    }
    return ;
}
int getMid(int a, int b, int c) {
    if (a > b) swap(a, b);
    if (a > c) swap(a, c);
    if (b > c) swap(b, c);
    return b;
}

void __quick_sort_v3(vector<int> &nums, int l, int r) {
    while (r - l > __threshold) {
        int x = l, y = r, z = getMid(nums[l], (nums[(l + r) >> 1]), nums[r]);
        do {
            while (nums[x] < z) x++;
            while (nums[y] > z) y--;
            if (x <= y) {
                swap(nums[x], nums[y]);
                x++, y--;
            }
        } while (x <= y);
        __quick_sort_v3(nums, x + 1, r);
        r = y;
    }
}

void final_insert_sort(vector<int> &nums, int l, int r) { 
    // 无监督
    // 先找到最小值放到第一位去
    // ind存最小值的下标
    int ind = l;
    for (int i = l + 1; i <= r; i++) {
        if (nums[i] < nums[ind]) ind = i;
    }
    while (ind > l) {
        swap(nums[ind], nums[ind - 1]);
        ind--;
    }
    // 还记得我们是分成了很多组么
    // 组间其实是内省排序
    // 组内是插入排序（小数据）
    for (int i = l + 2; i <= r; i++) {
        int j = i;
        while (nums[j] < nums[j - 1]) {
            swap(nums[j], nums[j - 1]);
            j--;
        }
    }
    return ;
}

void quick_sort_v3(vector<int> &nums, int l, int r) {
    __quick_sort_v3(nums, l, r);
    final_insert_sort(nums, l, r);
    return ;
}

快排的拓展算法-快速选择算法-findK

解决查找排名第k位元素