史上最细快速排序讲解（Hoare，挖坑，双指针，非递归）
史上最细快速排序讲解（Hoare，挖坑，双指针，非递归）
快速排序是一种高效的排序算法，由C.A.R. Hoare在1962年提出。其基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列的目的。本文将详细介绍快速排序的各种实现方法，包括递归方法、Hoare方法、挖坑方法、双指针方法以及非递归方法。
前言
快速排序是计算机科学中一种非常重要的排序算法，其效率高且应用广泛。本文将从多个角度深入讲解快速排序的实现细节，帮助读者全面理解这一算法。
一、递归方法快速排序
1. 递归主要思想
快速排序的基本思想是：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序的思想如下：
- 首先选择一个数组，从中找到一个基准值，使得基准值左侧的所有数据全都小于基准值，基准值右侧的所有数据全都大于基准值。
- 然后，对基准值左侧的部分再划分一个基准值，分成小于和大于基准值的两侧。
- 原本基准值的右侧也同理。
- 然后继续细分，直到划分到只有一个或没有元素。
- 可以把它看成二叉树的结构，对于每一个结点，排列好的数组就相当于它左右子树通过基准值排列好的样子叠加起来。
- 对于初始的数组来说，最主要的任务就是如何找基准值，以及如何遍历数组。
2. 递归代码实现
这是我们初始的数组。假设有一个函数：
int _QuickSort(int* arr, int left, int right)
的功能是实现返回数组 arr 中左边界 left 和右边界 right 的基准值。
那么我们就可以用这个数组模拟前序遍历的方式遍历这个数组：
- 假设基准值为
keyi，那么它的左子树就是[left, keyi-1]，右子树就是[keyi+1, right]。
递归的结束条件是 left >= right。
因此我们可以写出代码：
//快速排序
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = _QuickSort(arr, left, right);
//遍历它的左子树
QuickSort(arr, left, keyi - 1);
//遍历它的右子树
QuickSort(arr, keyi + 1, right);
}
二、Hoare方法实现找基准值
1. Hoare思想
Hoare方法如何找基准值呢？
还是我们的数组，我们将第一个元素定位基准值，left 为第二个元素，right 为最后一个元素。
- 首先，
right从右向左找小于基准值的位置，left从左向右找大于基准值的位置。 - 然后交换
arr[left]与arr[right]。 - 交换过后
left++，right--。 - 此时
left与right走到相同位置。 - 注意：在
left与right相等时还需要继续循环，为了二分左右子树。 - 我们接着
right从右向左找小于基准值的位置，left从左向右找大于基准值的位置。 - 但是现在
left <= right，因此不交换，结束循环。 - 将
keyi位置的值与right位置的值进行交换，此时right的位置就是基准值的位置。 - 特殊情况：如果
right或者left找到的值刚好等于基准值呢？我们来看一个特殊的数组。如果right或者left找到的值刚好等于基准值还能循环的话最后就会变成这样，right就会来到如图所示的位置，那么最后我们return right相当于左子树为空，其余元素全在右子树，我们快排就是要一直二分数据。因此如果right或者left找到的值刚好等于基准值不能循环。
2. Hoare代码实现
//找基准值
int _QuickSort(int* arr, int left, int right)
{
int keyi = left;
left++;
//对于传来的left与right,left从左往右找大，right从右往左找小
while (left <= right)
{
//问题2：有没有等于? 答：没有，假设数组元素全部都是基准值，那么每次递归之分出去一个数据
//问题3: 为什么要加left <= right，因为left<=right就可以结束了不用循环了
while (left <= right && arr[right] > arr[keyi])
{
right--;
}
while (left <= right && arr[left] < arr[keyi])
{
left++;
}
//出了这两个循环之后，就代表 left 与 right 都找到了各自的值，如果没找到也就越界了
if (left <= right)
{
Swap(&arr[left++], &arr[right--]);
}
}
//出了大的while循环就代表left已经超过right了,那么就需要交换right位置的值和保存的基准值
Swap(&arr[keyi], &arr[right]);
//right位置就是我们的基准值下标
return right;
}
//快速排序
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = _QuickSort(arr, left, right);
//遍历它的左子树
QuickSort(arr, left, keyi - 1);
//遍历它的右子树
QuickSort(arr, keyi + 1, right);
}
三、挖坑方法实现找基准值
1. 挖坑思想
挖坑方法如何找基准值呢？
我们先来看一张动图：
思路：
- 创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放入当前的"坑"中，返回当前"坑"下标（即分界值下标）。
看下图是我们初始的数组：
我们定义一个坑（hole），让他等于 left。
假设 key 保存数组最左边的数据，记作基准值。
接下来让 right 从右往左找小，如果小于基准值，就用这个值来填坑，再让 right 位置变为新的坑。
接下来让 left 从左往右找大，如果大于基准值，就用这个值来填坑，再让 left 位置变为新的坑。
重复上述步骤直到 left 不在小于 right。
此时，left 与 right 重合。
此时，让我们最开始保存的 key 填坑，返回 hole 就是基准值。
2. 挖坑代码实现
//挖坑法
int _QuickSort2(int* arr, int left, int right)
{
int key = arr[left];
int hole = left;
while (left < right)
{
while (left < right && arr[right] > key)
{
right--;
}
if (left < right)
{
arr[hole] = arr[right];
hole = right;
}
while (left < right && arr[left] < key)
{
left++;
}
if (left < right)
{
arr[hole] = arr[left];
hole = left;
}
}
arr[hole] = key;
return hole;
}
四、双指针方法实现找基准值
1. Lomuto前后指针法思想
思想：
- 创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。
我们来看一张动图：
还是那个数组我们来具体看一看每一步是怎么实现的~
先定义 keyi 保存基准值下标，定义 prev = left，cur = left + 1。
cur 从左往右找小，如果找到比基准值小的数组，就让 prev++，并且交换 prev 和 cur 中的数据。
注意：如果此时 ++prev 后与 cur 重合就不交换了。
cur 继续++执行前两项任务
直到 cur > right 结束循环，此时交换 key 与 prev 中元素，prev 的值就是基准值。
2. Lomuto前后指针法代码实现
//lomuto前后指针法
int _QuickSort3(int* arr, int left, int right)
{
int keyi = left;
int prev = left, cur = left + 1;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
return prev;
}
五、非递归方法快速排序
1. 非递归主要思想
非递归版本的快速排序需要借助数据结构：栈
非递归快速排序使用栈来模拟递归过程，避免函数的递归调用栈过深的风险。这里，我们通过图文详细讲解非递归版的快速排序。
非递归快速排序的基本步骤如下：
- 选择基准元素（pivot）：从数组中选择一个基准元素，通常是第一个或最后一个元素。
- 分区（partitioning）：将数组分成两部分，左边的元素都小于基准元素，右边的元素都大于基准元素。
- 栈的操作：使用栈来存储未处理的数组边界（左右索引）。在每次分区后，将左、右子数组的边界推入栈中，继续处理子数组。
- 重复分区：重复上述过程，直到栈为空为止。
详解步骤：
初始数组：
我们以数组 {5, 3, 9, 6, 2, 4, 7, 1, 8} 为例，并且以第一个元素 5 为基准元素进行排序。
原始数组： 5 3 9 6 2 4 7 1 8
第一步：选择基准元素
选取数组的第一个元素 5 作为基准元素。接下来，我们需要将小于 5 的元素移动到它的左边，大于 5 的元素移动到右边。
第二步：分区操作
使用双指针法（prev 和 pcur）遍历数组。初始状态下：
prev指向基准元素5。pcur从5的下一个元素开始。
我们遍历数组，将比 5 小的元素交换到 prev 所在的位置，最后将 5 和 prev 指针指向的元素交换。
位置 5 3 9 6 2 4 7 1 8
初始 5 3 9 6 2 4 7 1 8
交换 5 ↔ 3 5 9 6 2 4 7 1 8
交换 5 ↔ 2 3 5 9 6 4 7 1 8
交换 5 ↔ 1 3 2 5 9 6 4 7 8
现在数组的左边元素都小于 5，并将 5 归位：
| 新数组： |1| 3 | 2 | 4 |5| 6 | 9 | 7 | 8 |
基准元素 5 的最终位置为索引 4。
第三步：处理子数组
基准元素确定之后，我们将左右子数组的范围压入栈中：
- 左子数组范围：
[0, 3]，对应元素{1, 3, 2, 4}。 - 右子数组范围：
[5, 8]，对应元素{6, 9, 7, 8}。
我们从栈中取出右子数组 [5, 8]，选择新的基准元素 6，进行同样的分区操作。
对右子数组 [6, 9, 7, 8] 的处理：
原数组： 6 9 7 8
基准元素： 6 9 7 8
交换后 6 9 7 8
6 的位置已经确定，无需交换。继续对剩下的子数组 [9, 7, 8] 进行分区。
对子数组 [9, 7, 8] 的处理：
原数组： 9 7 8
基准元素： 9 7 8
交换后 7 8 9
9 归位，右子数组完成排序。
左子数组 [1, 3, 2, 4] 的处理：
我们从栈中取出左子数组 [1, 3, 2, 4]，选择 1 作为基准元素。由于所有元素都大于 1，无需交换，继续处理子数组。
- 子数组
[3, 2, 4]选择3作为基准元素，进行分区。
原数组： 3 2 4
基准元素： 3 2 4
交换后 2 3 4
至此，所有子数组都已处理完毕，数组完全有序。
- 完成排序的结果：
最终，数组经过多次分区操作，排序结果如下：
| 排序后数组： | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
2. 非递归代码实现
//使用遍历的方法
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
int keyi = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[prev], &arr[cur]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
//根据基准值划分左右区间
//左区间：[begin,keyi-1]
//右区间：[keyi+1,end]
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
STDestroy(&st);
}
总结
到这里，我们快速排序就写完啦！
要记住快速排序时间复杂度通常为O(n log n)，空间复杂度为O(log n)~