目录
一、快排的基本思想
- 将需排序的数据中取某一个值做基准值。
- 通过基准值将数组分成两个区间，左区间的数据都小于基准值，右区间的数据大于小于基准值
- 之后左右区间可以独立排序，再取一个基准值，重复上述步骤，直到左右区间为不存在或一个值时，排序完成
二、Hoare版本（左右指针法）
2.1 单趟排序
目的：
key左边的值都比key小，key右边的值都比key大
实现思路：
- 记录key位置，一般最左边或最右边以此作为分区条件，左右两个指针从两端开始往中间走
- right先走，找到比key小的值停下，left后走，找到比key大的值停下。
- left停止后，说明left的值比key大和right的值比key小，两个数据交换，大的在右边，小的就在左边
- left和right相遇时，需要将key和相遇位置的交换，目的达成，key比左边的值要大，比右边的值要小
代码如下：
// hoare（左右指针法），单趟升序
int left = begin, right = end;
int keyi = left;
// 相遇就结束
while (left < right)
{
// 右区间找小数
while (left < right && a[right] >= a[keyi])
{
right--;
}
// 左区间找大数
while (left < right && a[left] <= a[keyi])
{
left++;
}
// 交换
Swap(&a[left], &a[right]);
}
// 此时begin和end在同一位置，需要将其中key和其中一个交换
// 交换后，左边都比key小，右边都比key大
Swap(&a[left], &a[keyi]);
keyi = left;
注意事项：
- 为什么是right先走，而不是left先走呢?
- right先走找小可以确保最后相遇的位置是比key小，如果是left先走找大，最后一次的停下的位置的值可能会大于key，在交换的话就乱了，因为有条件left<end，最后一次先走的那个找到想要的值就会停下，后走那个绝对不会超过先走的，可以理解为最后一次先走的那个位置，就是相遇点
- 找值的条件，
left < end，如果没有添加这个条件，就会造成越界，虽然我在外循环的条件设置了left < right，但是在内部两个循环left和right在递增过程会越界。
- 通过下图例子就可以发现，right会越界
- 找值的条件，
a[right] >= a[keyi]，这里必须要>=，没有=可以解决上面越界问题，但是会造成死循环
- 通过下图例子发出，如果left和right的值一样，没有加
=的情况，就会死循环
经过一些举例，key的位置是最左边，right就先走，是最右边，left就先走
找值的时候条件必须有left<end和=的情况，
2.2 多趟排序（排序完成）
单趟完成后，此时数据就分成了两个区间，左边都是比key小，右边都是比key大。
我们利用分治的思想，让左右区间在进行单趟排序，在区间里在选一个key，在进行分区，直到最后左右区间不存在或者只有1个数，因为这种序列也可以认为是有序的，这样排序就完成了
key排序好后，将两个区间递归进行
这思想类似二叉树前序遍历
- 根 -> 左子树 -> 右子树
- 先排好key的位置 -> key的左区间 -> key的右区间
左区间[left, keyi - 1]，右区间[keyi + 1, right]
递归结束条件：区间不存在或者区间只有一个数，这中序列也是有序的，begin == end或begin > end，因为分区的特性，区间不存在的情况是begin>end。
hoare（左右指针法）多趟代码
// hoare（左右指针法)
void QuickSort(int* a, int begin, int end)
{
// 结束条件：区间不存在或只有一个数，该情况是有序的
if (begin >= end)
return;
int left = begin, right = end;
int keyi = left;
// 相遇就结束
while (left < right)
{
// 右区间找比key小的数
while (left < right && a[right] >= a[keyi])
{
right--;
}
// 左区间找比key大的数
while (left < right && a[left] <= a[keyi])
{
left++;
}
// 交换
Swap(&a[left], &a[right]);
}
// 此时begin和end在同一位置，需要将其中key和其中一个交换
Swap(&a[left], &a[keyi]);
keyi = left; // 更新keyi的位置
// [begin, keyi-1] keyi [keyi+1, end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
三、挖坑法
hoare版本中，为什么左边置为keyi右边就要先走无法理解，因此挖坑法诞生了，由国内大佬想出，大致思路和hoare版本差不多，但是更利于理解
两个单趟排序完结果不同，有的题目就会考察快排第一趟排序完的结果是什么？因为有多种方式，所以结果也不相同，所以快排的各个方法我们都需要了解
实现思路：
- 记录key，key一般都是最左边，目的就是为了把key排到正确的位置，同时将key设为坑位
- 开始坑在左边，右边开始找值补坑，right找到比key小的值，放入坑位，right形成新的坑
- 现在坑在右边，左边开始找值补坑，left找到比key大的值，放入坑位，left形成新的坑
- 直到left和right相遇就结束，最后把key放到坑位，key就排到正确的位置
- 以排好的key（下标为pivot）开始左右分区，[begin, pivot - 1] pivot [pivot + 1, end]，进行分治递归
挖坑法代码：
void QuickSort_pivot(int* a, int begin, int end)
{
if (begin >= end)
return;
int left = begin, right = end;
int key = a[left];
int pivot = left;
while (left < right)
{
// 找小于key的数
while (left < right && a[right] >= key)
{
right--;
}
// 找到小的数放到左边的坑里，自己形成新的坑位
a[pivot] = a[right];
pivot = right;
// 找大于key的数
while (left < right && a[left] <= key)
{
left++;
}
// 找到大的数放到右边的坑里，自己形成新的坑位
a[pivot] = a[left];
pivot = left;
}
// 最后pivot会指向相遇点，相遇点就是key排好的位置
a[pivot] = key;
// [begin, pivot-1] pivot [pivot+1, end]
QuickSort_pivot(a, begin, pivot - 1);
QuickSort_pivot(a, pivot + 1, end);
}
四、前后指针法
实现思路：
- 记录key，key一般都是最左边，目的就是为了把key排到正确的位置。
- prev记录begin的位置，cur记录begin+1的位置，cur一直递增的 ，如果cur处的值小于key的值，prev++，然后prev处的值和cur处的值交换（因为prev++后可能会相遇cur，这是原地交换没有意义，所以
prev++ !=cur才交换），直到cur越界就停止 - cur越界后，说明prev的位置就是key排好的位置，所以key和cur处的值交换后，key就排到正确的位置，开始keyi在最左边，需要更新keyi的位置
- 以排好的key开始左右分区，[begin, keyi - 1] keyi [keyi + 1, end]，进行分治递归
需要注意排序的思想两指针间隔，间隔的数都是大于key，当cur遇到小的数，prev++就会在间隔的地方（大于key的数位置），然后交换，就是大的数往后抛，小的数往前抛。
void QuickSort_pointer(int* a, int begin, int end)
{
if (begin >= end)
return;
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
// cur一直递增，碰到小于key的值并且prev++不等于自己，就交换
// prev++ == cur，会原地交换
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
// key交换到排好的位置，同时更新keyi的位置，原先在最左边
Swap(&a[keyi], &a[prev]);
keyi = prev;
// [begin, keyi-1] keyi [keyi+1, end]，进行分治
QuickSort_pointer(a, begin, keyi - 1);
QuickSort_pointer(a, keyi + 1, end);
}
五、快排的时间复杂度和优化
5.1 时间复杂度计算
快排的理想情况是每次取key排好大概是该序列的中间位置，因为每次递归分区时都能大概平分左右区间。
单趟排序时间复杂度是O(N)，每次就排好一个数，left和right相遇就排好了，在递归分区
可以看到递归结束，分区的过程就是一个满二叉树，现在左右分区一层的单趟排序也是O(N)，如：N/2，舍去常数，所以一共需要排logn层。
最后得出快排整体的时间复杂度 O ( N ∗ l o g N ) O(N*logN) O(N∗logN)
但是如果是数据的有序情况下进行快排，就是最坏的情况，我们来看看吧，到底时间复杂度是多少呢？
有序情况下就会出现下图中的极端情况，每次选key选是最小（最大）的数，就造成了每层只能排好一个数O(N)，需要排N层，很明显这是一个等差数列，通过公式得出最坏的情况时间复杂度是 O ( N 2 ) O(N^2) O(N2)
但是这并不是不能解决，有人就针对这个极端情况做出了优化，确保每次在分区都不会取到最小或最大的数，三数取中很好解决了该问题.
5.2 三数取中优化
该优化是针对快排的最坏情况（有序情况），确保在每次在分区里选key的时候，能保证在分区内不会取最或最大的数。
三数取中：最左边和最右边以及中间的数，取这三个数中，值的大小是中间的（不是三个数里最大或最小），比如在有序的情况下中间的值真好能二分区间。
代码如下：
// 三数取中
int GetMidIndex(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 right;
else
return left;
}
else
{ // a[left] >= a[mid]
if (a[mid] > a[right])
return mid;
else if (a[right] < a[left])
return right;
else
return left;
}
}
注意三数取中需要返回下标，不返回下标的话，左边的值就无法交换到中间值的位置。如swap（a[left]，mid），因为mid是数据，无法找到在数据中的下标。
为什么交换是左边的值和中间值的位置交换呢?
为了保持key还是取的区间最左边位置的值，但是这个最左边的值是中间值交换过来的，这样就能保证我们的单趟的逻辑不改变
如有序状态：1,2,3,4,5，交换后3,2,1,4,5，此时我们取的最左边的就是区间的中间值。
只需在单趟基础加增加一些代码，就能解决快排的最坏情况，所以快排不看最坏情况。
int midIndex = GetMidIndex(a, begin, end);
Swap(&a[midIndex], &a[begin]);
5.3 小区间优化
众所周知，与递归相关的算法，递归的过程类似与二叉树结构，高度是h，一共有 2 h − 1 2^h-1 2h−1个节点，调用就有 2 h − 1 2^h-1 2h−1次，递归到最后几层数据已经接近有序并且调用次数占了大部分（最后一层节点有 2 h − 1 2^{h-1} 2h−1个，每一节点都需要调用，这将近占用一半的调用次数）。所以小区间优化的目的是减少递归调用的次数。
以100w个数为例，最后几层的调用次数占了总调用次数的80%左右，所以我们就把他消除掉，我这里设小于10的数，就不在调用了，转用为插入排序，因为最后10个数，经过上面不断递归，几乎接近有序了，插入排序针对与接近有序的情况，时间复杂度是O(N)
挖坑法加上三数取中和小区间优化代码如下：
void QuickSort_pivot(int* a, int begin, int end)
{
if (begin >= end)
return;
// begin和end是闭区间，如[0,9]，一共10个数，所以+1，10个数以下就小区间优化
if (end - begin + 1 > 10)
{
// 三数取中优化
int midIndex = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[midIndex]);
int left = begin, right = end;
int key = a[left];
int pivot = left;
// 挖坑法
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[pivot] = a[right];
pivot = right;
while (left < right && a[left] <= key)
{
left++;
}
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
else
{
// 小区间优化
InsertSort(a + begin, end - begin + 1);
}
}
六、快排非递归版
递归有一个致命的缺陷，不能调用很多次，因为递归是在内存中栈区中建立空间，栈区不像堆区容量大，一般默认是8M，所以调用很多次，没能及时销毁，栈就会溢出（Stack Overflow）。
如图，我们通过递归阶乘，求10000！的结果，从调试得出栈就溢出了，因为需要10000层栈帧，递归深度太深，不能及时销毁，导致栈溢出。
递归改成非递归一般分两种情况
- 直接改成循环
- 借助数据结构的栈或队列，模拟递归在建栈帧的过程
改非递归先看是否能直接改成循环，如果递归过程比较复杂就需要借助数据结构的栈或队列来模拟递归调用过程，递归每次都会创建临时变量，而数据结构栈和队列的只能使用特定位置的数据，想要使用其他位置就必须出掉之前数据，类似销毁栈帧，所以很契合。
我们直接借助的是数据结构的栈来实现，因为数据结构的栈和操作系统内存的栈区，特性都是“后进先出”，所以
模拟过程能更相似递归调用。
递归和非递归的时间复杂度可能会有所不同，就像斐波那契数列，因此在进行转换时需要仔细分析算法的时间复杂度，并确保转换后的非递归的时间复杂度与原来的递归函数相同或更优。此外，非递归函数可能会占用更多的空间，因为需要使用栈或队列来存储中间结果。
思路：
- 先入右下标，在左下标，因为可以先取到左下标
- 取左右下标组成一个区间，单趟排好一个值（key），在利用key分成左区间[left，key-1]，右区间[key+1，right]。
- 检查左右区间数据个数，如果区间个数有二个以上，就需要在入栈排序
- 重复2,3步，直到栈为空，数据就都排好了，由于栈的特性，永远左区间先取出，所以先排好，右区间在排好，在过程上就和递归调用一样。
代码如下：
// 快排单趟前后指针法
int SingleQuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}
void TestQuickSortNonR(int* a, int n)
{
Stack st;
StackInit(&st);
// 先入右，再入左，为了先取左
StackPush(&st, n - 1);
StackPush(&st, 0);
// 栈为空，排序就完成
while (!StackEmpty(&st))
{
int left = StackTop(&st);
StackPop(&st);
int right = StackTop(&st);
StackPop(&st);
// 快排单趟，排好一个值key，分割左右区间
int keyi = SingleQuickSort(a, left, right);
// [left, keyi - 1] keyi [ keyi + 1, right]
// key+1小于right，说明至少右区间还有两个数据，还需要入栈排序
if (keyi + 1 < right)
{
//先入右，再入左
StackPush(&st, right);
StackPush(&st, keyi + 1);
}
// left小于keyi - 1，说明至少左区间还有两个数据，还需要入栈排序
if (left < keyi - 1)
{
//先入右，再入左，组成左区间
StackPush(&st, keyi - 1);
StackPush(&st, left);
}
}
StackDestroy(&st);
}
总结
快排的时间复杂度是 O ( n ∗ l o g n ) O(n*logn) O(n∗logn)
递归版本有缺陷，就是在建立太多栈帧情况，不能及时返回就会栈溢出。
非递归就能解决该问题，效率上二者差不多。
快排的三种实现方法（hoare版（左右指针法），挖坑法，前后指针法）和两种优化（三数取中、小区间优化），非递归都详细的说明了，请大家还是要多多画图和调试，走读代码才能更加牢固的掌握。