• 快速排序
  • 代码实现
    ⚪单趟排序 版本一
    ⚪快速排序 递归
    关于快排优化
    ⚪单趟排序 版本二
    ⚪单趟排序 版本三
    ⚪快速排序 非递归
  • 特性总结

快速排序

快速排序作为效率相对较高的排序，分别有递归与非递归两种写法，但都是

进行单趟排序，随后再解决其余问题。

快速排序的平均时间复杂度为O(N*logN)，最坏情况下为O(N^2)，空间复杂度为O(logN)

先介绍单趟排序的版本一紧接着是快速排序递归法，快排后是单趟排序的另外两版本，最后是快速排序非递归

代码实现

单趟排序 版本一

1.左右指针

  • 在序列中定义一个key，一般选择序列首位或末尾。
  • 分别在首位和末尾定义left和right，如果左作key则right先走，右作key则左先走，且右找小于key的，左找大于key的元素。
  • 假设首位为key，则right先走，找到小的停下；后left走，找到大的停下；随后left,right下标元素交换。直到left与right相遇，把key与相遇位置交换。
  • 则实现相遇位置左侧都小于key，右侧都大于key（单趟）。
  • 下面代码中三数取中法两行是优化，非排序必需。

//O(N)//左右指针int Partion1(int* a, int left, int right){// 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况//将中间值作key，放到序列首位int mini = GetMidIndex(a, left, right);Swap(a[left], a[mini]);int keyi = left;while (left < right){//右先走，找小//对于极端情况比如序列所有元素相同的情况，必须在内部while也写left<right，否则可能存在left或right超出序列范围while (left = a[keyi])right--;//左后走，找大while (left < right && a[left] <= a[keyi])left++;//交换将小于key的放到左边，大于key的放到右边Swap(&a[left], &a[right]);}//此时left与right相遇，将该位置元素与key元素交换Swap(&a[keyi], &a[left]);return left;}

对于递归程序，若递归深度太深，容易造成栈溢出

这里解释一下三数取中，快速排序在不使用三数取中法的情况下，最坏情况下时间复杂度为O(N^2)，即当所有元素有序或接近有序。

快排的时间复杂度取决于选择的key，如果选择的key是序列的最大值/最小值，时间复杂度就是最坏；
而三数取中法就是选取任意三个数的中间大小值（我们选择left mid right），尽可能避免选到最坏情况下的key值。

快速排序 递归

快速排序的核心思想是 每次当单趟排序后；

序列都会被分为 [begin, keyi-1] keyi [keyi+1, end] 三部分，左侧均小于key，右侧均大于key；

此时将 左侧/右侧 再次进行单趟排序，循环往复直到当分出的序列中left>=right则此序列有序并返回，最后序列有序。

void QuickSort(int* a, int left, int right){if (left >= right){return;}int keyi = Partion1(a, left, right);//[left, keyi-1]keyi[keyi+1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}

关于快排优化

  1. 在单趟排序中使用的三数取中是一种优化，前有进行讲述，这里不再过多赘述（主要用于选择合适的基准值，尽量减少时间复杂度最坏情况）
  2. 小区间优化：快排在遇到排序序列规模较小时，效率不及其他排序算法，可以自行判断当序列在某个范围内不再进行递归，直接将剩余元素排序(这里选择插入排序，相比于其他排序更适合)
void QuickSort(int* a, int left, int right){if (left >= right)return;// 小区间优化，当分割到小区间时，不再用递归分割思路让这段子区间有序// 对于递归快排，减少递归次数if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);}else{int keyi = Partion3(a, left, right);// [left, keyi-1] keyi [keyi+1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}}

单趟排序 版本二

挖坑法

思路用图片大致解释

void Partion2(int* a, int left, int right){// 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况int mini = GetMidIndex(a, left, right);Swap(a[left], a[mini]);int key = a[left];//存储序列首位元素int hole = left;while (left < right){//右先走，找小while (left = a[left])right--;//找到较小数放到a[hole]，此时right处留空（最后将key补充）a[hole] = a[right];//将空移到righthole = right;while (left < right && a[left] <= a[hole])left++;//同理将空转移到此时lefta[hole] = a[left];hole = left;}//将最初元素补到空上a[hole] = a[key];return hole;}

单趟排序 版本三

  • 版本三用前后两指针（下标），思路用图片解释

int Partion3(int* a, int left, int right){//三数取中选择合适的keyint mini = GetMidIndex(a, left, right);Swap(&a[left], &a[mini]);//定义下标int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){//如果++prev == cur就没必要交换if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}++cur;}Swap(&a[keyi], &a[prev]);return prev;}

快速排序 非递归

快排非递归可以采用队列或者是栈的方式，前者类似二叉树

这里使用栈的方式

  1. 将原数组左右边界入栈。
  2. 循环弹出栈顶的左右边界，对该范围内元素进行快排，若左右边界相等或者左边界大于右边界，此时跳出循环。
  3. 有key将数组分为两部分，将小于key值放左边，大于key值放右边
  4. 左序列的左右边界入栈
  5. 右边界的左右边界入栈
  6. 重复第二步，直到栈为空停下
void QuickSortNonR(int* a, int left, int right){ST st;StackInit(&st);StackPush(&st, left);StackPush(&st, right);while (!StackEmpty(&st)){int end = StackTop(&st);StackPop(&st);int begin = StackTop(&st);StackPop(&st);int keyi = Partion3(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]if (keyi + 1 < end){StackPush(&st, keyi + 1);StackPush(&st, end);}if (begin < keyi - 1){StackPush(&st, begin);StackPush(&st, keyi - 1);}}}

特性总结

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以叫快速排序
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(logN)
  4. 稳定性：不稳定