【数据结构与算法】快速排序（详解：快排的Hoare原版，挖坑法和双指针法|避免快排最坏时间复杂度的两种解决方案|小区间优化|非递归的快排）

引言

快速排序作为交换排序的一种，在排序界的影响力毋庸置疑，我们C语言中用的qsort，C++中用的sort，底层的排序方式都是快速排序。相比于同为交换排序的冒泡，其效率和性能就要差的多了，本篇博客就是要重点介绍快速排序的实现，以及其代码和效率的优化。

话不多说，开始我们今天的内容。

快速排序的基本逻辑

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，使左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

用通俗的语言讲：

1. 从一组元素序列中（称这个序列为A0）随机取出一个数，我们可以称这个数为k
2. 将比k元素小的数放在k的左边，比k元素大的数放在k的右边
3. 此时分别将K左右两边边的元素，拿出来各成一个序列（称为A1和A2）
4. 同样用处理A的方式处理A1，A2序列

最后，序列中所有左边的数都会比右边的小，完成快速排序。

可以先来处理第一步和第二步，也就是快速排序的第一层排序。

快速排序的第一层

这里有一张gif动图，大家可以先预热一下，如果看懂了，可以跳过一部分的讲解。

第一步，取第一个元素（下标为key）为基准值，我们的目的是使基准值左边的数都比基准值小，基准值右边的数都比基准值大。

第二步，定义两个下标变量，一个变量从右往左走（R），一个变量左往右走（L）。首先从R开始往左走（走的时候左边的L保持不动），每走一步都与基准值相比较。

让 R 停下来的条件有两个：① R 位置的值比基准值小。   ② R 与 L 相遇。

第三步，如果让R停下来的条件为①，则L开始往右一步步走，每走一步也都与基准值比较。

让 L 停下来的条件也有两个：① L 位置的值比基准值大。  ② R 与 L 相遇。

第四步，如果让 L 停下来的条件为①，则交换 L 和 R 两位置所存的值，回到第二步， R 开始往左移动，重复此过程，直到 L 和 R 相遇。

在整个四步过程中，一旦出现 R 和 L 相遇，则第一层数据遍历结束，交换 L 和基准值key存的值并进入下一层的排序。

注：在第二步的时候要统一由 R 先开始移动，这样可以保证在L和R相遇时一定会是比key小的数。这是因为R先移动，在找到比基准值小的数前是不会停止的；而L移动的前提条件是R找到了比基准值小的数（这一特性使R静止的位置一定会是比基准值key小的数）。

故：L和R静止一方的值必定比基准值key小。

关于L和R相遇时一定会是比key小的数这个问题如果还没搞懂，可以拿张纸来画一画。

上面就是一层快速排序的全过程，在这一层排序过后，可以找到一个基准值的真正位置，也让基准值左边的数都小，右边的数都大。

接下来是这一层排序的代码实现：

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}int left = 0, right = n - 1;
int keyi = 0;
while (left < right) {while (right > left && a[right] >= a[keyi]) {right--;}while (right > left && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);

递归版快速排序的实现

Hoare版快速排序

写完了第一层之后，其他的工作就轻松多了，就是运用递归，每层递归时，需要调整left和right的值。这个过程和二叉树的前序遍历非常相似，以下就是完整的hoare版的快速排序：

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void QuickSort1(int* a, int left, int right)
{//当left>=right时递归结束if (left >= right)return;int begin = left, end = right;int keyi = left;while (left < right) {while (right > left && a[right] >= a[keyi]) {right--;}while (right > left && a[left] <= a[keyi]) {left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);QuickSort1(a, begin, left - 1);QuickSort1(a, left + 1, end);
}

在递归的过程中，递归的第一个区间是：[begin , left - 1(left - 1即相遇的前一个位置) ]，递归的第二个区间：[left + 1(left + 1即相遇的后一个位置) , end]

在快速排序的递归实现中，除了发明快速排序的大佬hoare的原版排序方式。还有两种方式，虽然底层原理都是一样的，但这两种方式也有各自的特点。

挖坑法快速排序

什么是挖坑法，顾名思义，就是挖一个坑。在理解了hoare版本快速排序的基础上理解这个方式并不困难，下面来看看挖坑法的gif格式动图：

第一步，将基准值挖出存在key中，基准值位置下标用一个变量hole位记录（相当于一个坑位）

第二步，首先从R开始往左走（走的时候左边的L保持不动），每走一步都与基准值相比较。

让 R 停下来的条件有两个：① R 位置的值比基准值小。   ② R 与 L 相遇。

第三步，如果使R停下来的条件为①，则将R下标位置的值放入坑位hole中，同时将R下标赋给hole，这时候坑位变成R的位置。

第四步，如果让R停下来的条件为①，则L开始往右一步步走，每走一步也都与基准值比较。

让 L 停下来的条件也有两个：① L 位置的值比基准值大。  ② R 与 L 相遇。

第五步，如果使L停下来的条件为①，则将L下标的值放入hole中，同时将L下标赋给hole，这时候坑位变成L的位置。

这里遍历停止的标志也同样是L和R相遇，相遇的位置也是一个坑位，直接把key的值放到坑位中，第一层整个数据处理就结束了。

下面是挖坑法的实现代码：

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void QuickSort2(int* a, int left, int right)
{if (left >= right)return;int begin = left, end = right;int valk = a[left]; int holei = left;while (left < right) {while (right > left && a[right] >= valk) {right--;}a[holei] = a[right]; holei = right;while (right > left && a[left] <= valk) {left++;}a[holei] = a[left];holei = left;}a[holei] = valk;QuickSort2(a, begin, left - 1);QuickSort2(a, left + 1, end);
}

挖坑法的优势在于好理解，就是保持一个坑位，不断往里面填数字然后变换坑位的过程。

前后指针版快速排序

前后指针版本的快速排序不好理解，但是代码量出奇的少，先看一下gif动图了解大致思路：

规则很简单：

1. cur >= key ，++cur
2. cur < key ，++prev ，交换prev和cur的值
3. 结束条件：cur > end
4. 结束后，交换prev和key的值

在整个过程中，prev的位置之前的数据都小于基准值key，而prev和cur之间的值都保证大于基准值key，在prev和cur的值交换的过程中，相当于把大的数字往后甩，把cur找到的小的值往前插入。在cur遍历到最后，比基准值小的数字也就成功都插入到了前面，而比基准值大的数字也都被甩到了后面。这时交换prev和key的值也就达到了快速排序第一层遍历后的效果。

下面是前后针法的实现代码：

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void QuickSort3(int* a, int left, int right)
{if (right <= left)return;int pcur = left + 1, prev = left, keyi = left;while (pcur <= right) { if (a[pcur] < a[keyi] && ++prev != pcur) Swap(&a[pcur], &a[prev]);++pcur;}Swap(&a[keyi], &a[prev]);QuickSort3(a, left, prev - 1);QuickSort3(a, prev + 1, right);
}

建议大家可以把前后指针法的实现理解后背下来，后期Hr面试问的时候搓起来会很爽。

避免最坏时间复杂度的两种解决方案

快速排序排起来是很快，但我们上面所写的快排真的就没有缺陷吗？

现在你可以试想一种场景，如果用上面所写的代码去排一个有序数组会如何。

这时候的复杂度将会是一场灾难。基准值如果每次都是数组的第一个值，那么这种情况就很有可能会出现。对于这种由于顺序引起的最坏时间复杂度问题，这里提供两种解决方案。

1.随机选key

既然害怕数组顺序无法选出随机数，那么让选的基准值下标值为随机取的不就能解决问题了吗？就是我们所说的随机选key。

这里随机数需要用到rand()函数，头文件<stdlib.h>

int randi = rand();
randi %= (right - left + 1);
randi += left;
Swap(&a[randi], &a[left]);

以上就是随机key的取法，(right - left + 1) 是为了控制范围防止越界对随机数做的一个处理。

 把这种处理方式放入快排代码中就是这个样子，以Hoare版为例：

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void QuickSort1(int* a, int left, int right)
{//当left>=right时递归结束if (left >= right)return;int begin = left, end = right;int keyi = left;//取随机key部分int randi = rand();randi %= (right - left + 1);randi += left;Swap(&a[randi], &a[left]);//-----------while (left < right) {while (right > left && a[right] >= a[keyi]) {right--;}while (right > left && a[left] <= a[keyi]) {left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);QuickSort1(a, begin, left - 1);QuickSort1(a, left + 1, end);
}

2.三数取中

具体思路是，找三个下标left，right ，mid对应的数，取三个数中处于中间位置的作为key（基准值），其中 mid = (left + right) / 2 。

这里我们专们写一个三数取中的函数，这一过程相对比较复杂：

//三数取中函数
int GetMid(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]) {if (a[mid] < a[right])return mid;else if (a[left] > a[right])return left;else return right;}else {if (a[mid] > a[right])return mid;else if (a[left] > a[right])return left;else return right;}
}

与上述随机取key时放置的位置一样

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void QuickSort1(int* a, int left, int right)
{//当left>=right时递归结束if (left >= right)return;int begin = left, end = right;int keyi = left;//三数取中部分int midi = GetMid(a, left, right);Swap(&a[midi], &a[left]);//-----------while (left < right) {while (right > left && a[right] >= a[keyi]) {right--;}while (right > left && a[left] <= a[keyi]) {left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);QuickSort1(a, begin, left - 1);QuickSort1(a, left + 1, end);
}

到这里，避免最坏时间复杂度的两种方案就介绍完了。

小区间优化

什么是小区间优化？

你是否考虑过这样一个问题，当快排递归到最后几层时，会产生多少小区间。

这里出现了一个很明显的问题：待排序的数很少，但是走递归的消耗较大，最后几层的递归占整个递归的80%~90%。

这里给出的小区间优化方式就是，当递归进入待排序数字只剩10个左右的时候，使用直接插入排序的方式对小区间进行排序。

//小区间优化方式
if(right - left + 1 < 10)
{//插入排序，减少90%的递归InsertSort(a + left, right - left + 1);
}

放到hoare版快排中就是这样的，可以省去if判断return。

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void QuickSort1(int* a, int left, int right)
{//小区间优化方式if(right - left + 1 < 10){//插入排序，减少90%的递归InsertSort(a + left, right - left + 1);}//-------------int begin = left, end = right;int keyi = left;while (left < right) {while (right > left && a[right] >= a[keyi]) {right--;}while (right > left && a[left] <= a[keyi]) {left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);QuickSort1(a, begin, left - 1);QuickSort1(a, left + 1, end);
}

此方式优化了大部分的递归，但得益于计算机对递归的处理，这种优化和原版的效率比起来就没有那么明显了。

快速排序的非递归实现

讲了这么多，总算是到了咱们的最后一个问题，快速排序非递归的实现。既然不让递归，咱们可以换个思路，用栈模拟个递归不就行了。在栈中存放左右区间，可以和递归达到同一个效果。

你问我栈是什么？emm，我之前写了一遍关于栈的博客，供参考：

初阶数据结构之---栈和队列（C语言）

取区间的方式：

先插入总区间，进入一个大循环中，循环结束的条件为栈为空，每次取栈顶弹栈，处理区间后再次往栈中插入被分割出来的有效区间，继续循环。

主体思路就是用栈模拟一个递归的过程，栈本来应该是构建一个结构体存左右区间，不过这里我就直默认顺序接插入右区间和左区间，取的时候依次就是是左区间和右区间，不再麻烦造个结构体了。

以下是非递归实现快速排序，复用上次栈的代码：

typedef int STDataType;
typedef struct stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}void STDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity) {int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (tmp == NULL) {perror("realloc tmp fail:");exit(1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;++ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)) {int begin = STTop(&st); STPop(&st);int end = STTop(&st); STPop(&st);if (begin >= end)continue;int keyi = begin, prev = begin, pcur = begin + 1;while (pcur <= end) {if (a[pcur] < a[keyi] && ++prev != pcur)Swap(&a[prev], &a[pcur]);++pcur;}Swap(&a[prev], &a[keyi]);STPush(&st, prev - 1); STPush(&st, begin);STPush(&st, end); STPush(&st, prev + 1);}
}

结语

以上就是快速排序的所有内容，本篇博客关于快排的内容，讲到了Hoare原版快速排序，挖坑法和双指针法，避免快排最坏时间复杂度的两种解决方案，小区间优化，非递归的快排等内容，希望能帮助大家快速理解和学会快速排序。

感谢大家的支持！