前言
排序作用的重要性是不言而喻的，例如成绩的排名、预约时间的先后顺序、不同路程的消耗与利润等。快排可以实现O(n * logn)的时间复杂度，O(logn)的空间复杂度来实现排序【虽然结果是不稳定的】。
算法思想
快速排序实际上是采用分治的思想，每次迭代在当前区间中选取一个数作为哨兵，通过一系列的交换操作将当前区间分为左区间和右区间【使得左区间的值全部小于等于哨兵，右区间的值全部大于等于哨兵】。然后再对左区间、右区间执行这种划分区间的策略操作，当区间的长度为1时停止。等到所有分治的区间长度都为1时，此时的原数组就已经是一个排好序的数组了。
具体步骤
假设数组名称为q，具体步骤如下：
- 如果区间长度小于等于1了，则结束循环。否则执行下一步。
- 先从本区间中取出第一个数作为哨兵
mid，即令mid等于本区间最左端元素的值。执行下一步。 - 令
i等于本区间最左端元素在原数组中的下标，j等于本区间最右端元素在原数组中的下标。执行下一步。 - 判断
i < j是否成立，如果满足，则执行下一步。否则跳转到第9点。 - 判断
q[j] >= mid && i < j是否成立，如果满足，则j向左移动一位【j--】，再次执行本轮【即本次步骤是循环】。否则执行下一步。 - 令
q[i] = q[j]。执行下一步。【目的：进行元素移动，保证右区间的值都是大于等于哨兵的值，此时j右侧的值都不小于哨兵的值，且一定会有下一步来使得q[j]的值大于等于哨兵的值】 - 判断
q[i] <= mid && i < j是否成立，如果满足，则i向右移动一位【i++】，再次执行本轮【即本次步骤是循环】。否则执行下一步 - 令
q[j] = q[i]。跳转到第4点。【目的：进行元素移动，保证左区间的值都是小于等于哨兵的值，此时i左侧的值都不大于哨兵的值，且一定会有下一步来使得q[i]的值小于等于哨兵的值】【第4点~第8点是一轮大循环】 - 令
q[i] = mid。执行下一步。【循环结束后，i的位置即是哨兵的位置，此时令q[i] = mid即可。这一步操作保证了第6、8点担忧的地方，即这里一定可以使得最终的q[i]、q[j]等于哨兵的值。】 - 划分两个区间【
本区间左端点，i - 1】，【i + 1， 本区间右端点】，将这两个区间再次执行第一步的操作。【整个步骤是快排的分治操作的循环】
图表演示
假设我们拥有一个数组：a，长度为：5，内容为：3 1 2 4 5，需要对其进行从小到大排序。则流程为：
第一次递归：
此时数组为：3 1 2 4 5
基础数据：
l = 0：本轮区间左边界在数组中的下标r = 4：本轮区间右边界在数组中的下标mid = a[l] = 3：哨兵的值i = l = 0：左指针j = r = 4：右指针
初始化数据：
- 此时
q[j] = 5 > 哨兵，满足右指针移动条件，右指针左移。
- 此时
q[j] = 4 < 哨兵，满足右指针移动条件，右指针左移。
- 此时
q[j] = 2 > 哨兵，不满足右指针移动条件，进行元素移动【保证j右侧的值都大于哨兵的值】，接下来进行左指针移动
此时q[l]的值不见了，但是！！！我们的哨兵存的就是q[l]的值，在最后q[l]的值会回到数组中，故一个元素的值都不会少。
- 此时
q[i] = 2 < 哨兵，满足左指针移动条件，左指针右移。【第一次交换左右指针移动时左指针条件一定满足，因为此时q[i]的值是刚才q[j]的值，而刚才的q[j]是一定小于哨兵的值】
- 此时
i = j，循环条件结束，此时左右指针都不会再移动了，则执行q[i] = q[j]和q[j] = q[i]是没有意义的，因为此时i = j。
- 此时循环结束，令
q[i] = mid。
即此时q[l]的值回到数组中了，故数组中的一个元素的值都没有少。
- 划分两个新的区间
l, i - 1、i + 1, r。对这两个新区间进行递归处理。
第二轮递归
本轮的数组为：2 1【上一轮递归处理后得到的左区间】
基础数据：
l = 0：本轮区间左边界在数组中的下标r = 1：本轮区间右边界在数组中的下标mid = a[l] = 2：哨兵的值i = l = 0：左指针j = r = 1：右指针
初始化数据：
- 此时
q[j] = 1 < 哨兵，不满足右指针移动条件，进行元素移动【保证j右侧的值都大于哨兵的值】，接下来进行左指针移动。
- 此时
q[i] = 1 < 哨兵，满足左指针移动条件，左指针右移。【第一次交换左右指针移动时左指针条件一定满足，因为此时q[i]的值是刚才q[j]的值，而刚才的q[j]是一定小于哨兵的值】
- 此时
i = j，循环条件结束，此时左右指针都不会再移动了，则执行q[i] = q[j]和q[j] = q[i]是没有意义的，因为此时i = j。
- 此时循环结束，令
q[i] = mid。
- 划分两个新的区间
l, i - 1、i + 1, r。对这两个新区间进行递归处理。
接下来迭代的流程同上，不再演示。
实现代码：
#include<stdio.h>
#define N 100007
int a[N];
void quickSort(int q[], int l, int r)
{
if (l >= r) return;
int mid = q[l];
int i = l, j = r;
while (i < j)
{
while (q[j] >= mid && i < j) j--;
q[i] = q[j];
while (q[i] <= mid && i < j) i++;
q[j] = q[i];
}
q[i] = mid;
quickSort(q, l, i - 1);
quickSort(q, i + 1, r);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
quickSort(a, 0, n - 1);
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}
总结分析：
- 为什么是先移动
j，而不是先移动i：因为哨兵等于q[i]，那么先移动i，则此时q[r]的数据是没人保存的，如果发生交换了q[j] = q[i]之后，实际上q[r]的值就不见了。但如果先移动j，由于哨兵的值是mid，那么就算发生了交换q[i] = q[j]，而q[l]的值还是存在的，即哨兵的值。 - 记住：哨兵存的数组中的值，而不是下标，他并不是一个抽象的内容，他实际上就是
q[某个下标],而这个元素也会发生移动。即最开始哨兵的位置是在q[l],而最后哨兵已经被移动到q[i]了。 - 下一次迭代选中区间
l, i - 1，i + 1, r。不包含 i 是因为 i 这个位置已经是哨兵了，不需要再进行排序了，他的位置一定是这个地方。 - 初级版【或者说通用版本】的快速排序大部分情况下是可以使用的，但是效率并不能达到快速排序的预期值，比如该链接中的的题目是不能通过：活动 - AcWing 。需要将排序的步骤进行优化，才能达到真正快速排序的预期。【可参考下一篇链接】
