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

引言

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

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

快速排序的基本逻辑

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

用通俗的语言讲：

从一组元素序列中（称这个序列为A0）随机取出一个数，我们可以称这个数为k
将比k元素小的数放在k的左边，比k元素大的数放在k的右边
此时分别将K左右两边边的元素，拿出来各成一个序列（称为A1和A2）
同样用处理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动图了解大致思路：

规则很简单：

cur >= key ，++cur
cur < key ，++prev ，交换prev和cur的值
结束条件：cur > end
结束后，交换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原版快速排序，挖坑法和双指针法，避免快排最坏时间复杂度的两种解决方案，小区间优化，非递归的快排等内容，希望能帮助大家快速理解和学会快速排序。

感谢大家的支持！

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

引言

快速排序的基本逻辑

快速排序的第一层

递归版快速排序的实现

Hoare版快速排序

挖坑法快速排序

前后指针版快速排序

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

1.随机选key

2.三数取中

小区间优化

快速排序的非递归实现

结语

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

引言

快速排序的基本逻辑

快速排序的第一层

递归版快速排序的实现

Hoare版快速排序

挖坑法快速排序

前后指针版快速排序

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

1.随机选key

2.三数取中

小区间优化

快速排序的非递归实现

结语

热门文章

最新文章

相关课程

相关电子书

相关实验场景