【数据结构】快速排序详解（递归版本）

0. 前言

快速排序算法是霍尔（Hoare）在1962年提出来的。

本期博客给同学们介绍，如何通过递归的不同写法的方法来实现简单的快速排序。

1. 快速排序的基本思想

快速排序是一种 二叉树结构 的交换排序方法，其基本思想为：

任取待排序元素序列中的某元素作为 基准值(称其为key) ，按照该排序码将待排序集合 分割成两子序列 ，左子序列中所有元素 均小于 基准值，右子序列中所有元素 均大于 基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

这一过程相当于二叉树的前序遍历，先让基准值排列在相应位置，然后分割子序列，每次分割左右子序列都排好一个基准值，然后再分割左右子序列，直到序列中只有一个元素时即为最小子问题，当每一个根都排在了相应位置，那么序列就变得有序了，所以很容易就想到了用递归来实现快速排序这一算法。

2. 快速排序的不同版本的实现

为了简单描述快排的思想，这里我们排整形数据而且排成升序。

2.1 hoare版本

2.1.1 单趟排序动图演示

单趟排序的结果：

我们可以看到，我们以这个区间内的最左边的元素为key，然后定义了左、右指针来指向数组的下标(这里是两个整型变量，存储下标)，先让右指针从数组右边开始向左遍历元素，当遍历到的值比key值小时停下来，然后启动左指针，从左边开始遍历数组，当遍历到的值比key值大时停下来，这个时候左指针指向数组中比key值大的数值的下标，右指针指向数组中比key值小的数值的下标，这个时候我们交换这两个值，这样小的值就被换到了前面，大的值就被换到了后面，直到左右指针相遇。当左右指针相遇时的地方就是key值应该排在的相应位置，这个时候将key和相遇的地方交换数值就完成了单趟的排序。此时发现，key左边的值都比key小，右边的值都比key大。这样我们就排好了key这个元素。

在这个过程中，有同学可能会有这样的问题：

如果相遇位置的值比基准值 key 位置上的值大怎么办呢？

但其实我们发现这种情况是不存在的，

交换后的结果仍然是符合左边值的比key小，右边的值比key大。

其原因是，我们是先让右指针先向左遍历找比key小的值，找到后才让左指针向右遍历，这样可以保证相遇的时候指向的值比key小。

这需要分两种情况进行讨论的：一种是 key 在左边，另一种就是 key 在右边。

第一种情况是：当右指针停下了，左指针向右遍历时没找到比key大的值，左指针与右指针相遇，这个时候指向的值一定是比key小的。

另一种情况是：右指针向左遍历的时候没有找到比key小的值，直接与左指针相遇了，这个时候又可以分成两种情况：

第一种情况是：左指针没动，指向key的位置，这个时候说明key本身的位置就是其相应的位置，不需要进行移动，这里自己跟自己交换相当于没移动。

第二种情况是：左指针先前发生过与右指针的交换，交换后左指针指向的值一定是小于key的，这个时候右指针与左指针相遇后指向的值与key值交换，可以保证交换的值比key小。

2.1.2 递归展开多个子区间进行单趟排序

我们通过单趟排序将key排到了正确的位置上，按照同样的方法，key位置左区间右区间分别进行同样的操作，每次单趟排序选出key排到相应位置，每排好key的位置后，就将key的左右分成两个区间，再在左右区间中选出key排好后再分成左右区间，我们发现他是一个函数递归的过程，递归的思想本质就是把大事化小，最后区间内只剩下一个元素时（只有一个元素可以认定为有序）或者区间内没有元素时是最小子问题。最后每个元素都排在了相应的位置上，数组就变有序了。

下面是递归展开图：

我们可以从上面的递归展开图看到，我们每次在区间内排出好key的位置，然后再在key的左右区间进行递归，再次排出key的位置，再分成两个子区间，每次递归就排好了一个值，直到区间内只有一个元素或者没有元素时结束递归。这样下来，我们的数组就变有序了。

2.1.3 代码的具体实现

2.1.3.1 霍尔法单趟排序代码

void Swap(int* px, int* py)
{int tmp = *px; *px = *py;*py = tmp;
}// 快速排序hoare版本 单趟排序
int PartSort1(int* a, int left, int right)
{if (left >= right)return 0;//最小子问题 ://区间内只有一个值(left == right)或者为空(left >= right)int end = right;//先从右边往左找比key值小的数丢到前面int begin = left;//从左边下标从右找比key大的数丢到后面int key = left;//要排序的下标while (begin < end)//当左右指针相遇时结束{//从右往左找比key小的数while (begin < end && a[end] >= a[key]){end--;}//找到比key小的数后就从左往右找比key大的数while (begin < end && a[begin] <= a[key]){begin++;}//交换这两个数Swap(&a[begin], &a[end]);//功能相当于swap}//出来后说明begin和end相遇了，此时该下标位置就是key值排序后所在的位置Swap(&a[key], &a[begin]);//将key换到相应的位置key = begin;//更新key的下标return key;//返回排好了的元素的下标
}

2.3.1.2 霍尔法递归代码

void QuickSort(int* a, int left, int right)
{if (left >= right)//当只有一个元素时是最小子问题return;//此区间执行单趟排序//hoare法int key = PartSort1(a, left, right);//接收已经排好了的元素下标//递归子区间   [left,key - 1]key[key + 1,right]QuickSort(a, left, key - 1);QuickSort(a, key + 1, right);return;
}

写完后我们可以随机生成一个数组

我们就用刚才的那组数据{6,1,2,7,9,3,4,5,10,8}, 来测试一下

我们发现他按照升序排序成了{1,2,3,4,5,6,7,8,9,10}，说明我们的代码没有任何问题！

2.2 挖坑法

挖坑法的思路与霍尔法的思路大致相同。

挖坑法思路过程分析：

创建左右指针。
首先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）

2.2.1 单趟排序方法动图演示：

单趟排序后的结果：

下面我给大家画个图具体演示上面动图的过程

还是以同样的数列 6，1，2，7，9，3，4，5，8，10 为例：

1. 先将第一个数存放到 key 中，形成一个坑位：分别有 left 和 right 指向数列的最左端与最右端；

2. right 先走，找到比 key 小的数，将该数丢到坑里；同时又形成了一个新的坑；

3. left 开始走，找到比 key 大的数，将该数丢到坑里；同时形成一个新的坑；

4. right继续找小，进行重复的操作；

5. left 找大；

6. right 找小；

7. left 找大；

8.若二者相遇就停下来；将 key 值放入坑；

至此，一趟排序已经完成！

这个方法和上面的hoare版本都是先让右指针向左遍历找比key小的值，所以不会存在导致出现排完序后出现key值左边出现大于key的元素。

2.2.2 递归展开多个子区间进行单趟排序

快速排序挖坑法的递归和hoare法差不多，将排好后的key值左右两边分成左右子区间进行递归。但是有一点要注意：这两种方法对同一个数组进行一次单趟排序后的数组元素位置不一定对应相同。

我们将下面这组数进行递归，每次递归进行一次单趟排序排好key的位置

如果是hoare法，排好6后元素的顺序是这样：

如果是挖坑法，排好6后元素的顺序是这样：

我们可以发现这两种单趟排序后6的左右区间的元素顺序不是一一对应的，但是都符合快速排序的思想，即6的左边元素都小于6，6的右边的元素都大于6。

递归展开图：

2.2.3 代码的具体实现

2.2.3.1 挖坑法单趟排序代码

//单趟 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{//最小子问题 ://区间内只有一个值(left == right)或者为空(left >= right)if (left >= right)return left;//先从右边往左找比key值小的数填到坑里 然后right指向的地方就变成了新坑int end = right;//一开始坑是最左边的元素。//之后从左边下标从右找比key大的数填到右边的坑中。//然后左指针指向的元素就变成了新坑.int begin = left;int key = a[left];//保存要排序的值while (begin < end)//当左右指针相遇时结束{while (begin < end && a[end] >= key)//从右往左找比key小的值填到坑里{end--;}//此时begin位置是坑a[begin] = a[end];//将比key小的值填入坑while (begin < end && a[begin] <= key)//从左往右找比key大的值填到坑中{begin++;}//此时end位置是坑a[end] = a[begin];}//begin和end相遇的地方是key对应的位置a[end] = key;return end;//返回排好位置的元素的下标
}

2.2.3.2 挖坑法递归代码

void QuickSort(int* a, int left, int right)
{if (left >= right)//当只有一个元素时是最小子问题return;//此区间执行单趟排序//hoare法//int key = PartSort1(a, left, right);//接收已经排好了的元素下标//挖坑法int key = PartSort2(a, left, right);//接收已经排好了的元素下标//递归子区间   [left,key - 1]key[key + 1,right]QuickSort(a, left, key - 1);QuickSort(a, key + 1, right);return;
}

2.3 前后指针法

2.3.1 单趟排序方法动图

单趟排序的结果：

和hoare版本的排序一样，将最左边的值作为待排序的key值，然后定义了前后指针prev和cur。这里的prev和cur指针不再是一左一右遍历，而是都以最左边为起点，然后cur先向右遍历，直到cur指向的值比key小，然后prev向后走一步，交换cur和prev指向的值，然后cur再向右遍历，找比key小的值，重复以上步骤，直到cur走到尽头的下一个越界的位置，这个时候我们prev所指向的位置就是key值所对应的位置，我们再交换这两个值，key就排到了其相应的位置上。

单趟排序存在的问题思考：

这里单趟排序是把cur找到小于key的值与prev交换，所以prev指向的值不是key自己就是比key小的数，所以最后一次将key和prev位置对换时，必定是小的数和key交换，所以不会出问题。

2.3.2 递归展开多个子区间进行单趟排序

有了前面的铺垫，这里的递归方法也是相同的，就是单趟排序排好key的位置后，递归key的左右子区间，再次排出key，再次递归左右子区间。

注意：这三种排key的方法都不相同，所以单趟排序同一个数组后的元素排列顺序也不尽相同。

我们将下面这个数组进行递归，每次递归进行一次单趟排序排好key的位置

下面是递归展开图：

2.3.3 代码的具体实现

2.3.3.1 前后指针法单趟排序代码

void Swap(int* px, int* py)
{int tmp = *px; *px = *py;*py = tmp;
}//单趟排序 快速排序前后指针法
int PartSort3(int* a, int left, int right)//返回排好了的数据key下标
{//最小子问题 ://区间内只有一个值(left == right)或者为空(left >= right)if (left >= right)return left;int prev = left, cur = left + 1;//前后指针while (cur <= right)//当cur指向数组外时结束{//让后指针向右遍历找到比要排序的数小的值，// 如果找到了，那就让prev先++ 如果prev和cur指向同一个地方那就不交换// prev和cur指向不同元素就交换prev和cur的值 // 当cur走到排序的区域外时，prev的位置就是要排序的数所在的位置if (a[cur] < a[left] && ++prev != cur){Swap(&a[prev], &a[cur]);}cur++;//cur指针往右走}//此时prev的位置就是key的位置Swap(&a[prev], &a[left]);return prev;//返回排好位置的下标
}

2.3.3.2 前后指针法递归代码

void QuickSort(int* a, int left, int right)
{if (left >= right)//当只有一个元素时是最小子问题return;//此区间执行单趟排序//hoare法//int key = PartSort1(a, left, right);//接收已经排好了的元素下标//挖坑法//int key = PartSort2(a, left, right);//接收已经排好了的元素下标//左右指针法int key = PartSort3(a, left, right);//接收已经排好了的元素下标//递归子区间   [left,key - 1]key[key + 1,right]QuickSort(a, left, key - 1);QuickSort(a, key + 1, right);return;
}

以上就是我们的三种不同的单趟排序进行递归实现快速排序的方法！

那么有同学思考说，有没有不用递归的方法呢？

这期博客我们先就讲到这儿，下期博客我们来探究一下，用非递归的方法如何实现快速排序！

如果你觉得博主讲的还不错对你有帮助的话，给我的博客留个赞和关注，

后期不断给大家讲解新的知识。我们下期见哦~👋👋