快速排序简介
快速排序（Quick Sort）由 Tony Hoare 在 1962 年提出，凭借分治思想与高效的平均性能，成为众多编程语言和标准库中的默认排序算法。它先选出一个基准值（key），再通过一趟划分，把比基准小的元素放在左边，比基准大的元素放在右边，然后递归处理子区间，直到整个序列有序。
1.1 快排的提出与背景
- 1962 年，Tony Hoare 提出快速排序，并凭借这一成果获得了图灵奖。
- 快速排序利用 分治思想，通过'划分—递归'的方式实现排序。
1.2 基本思想
- 在数组中选择一个基准值（key）；
- 将数组划分为两部分：左边比 key 小，右边比 key 大；
- 递归排序左右两部分；
- 最终合并得到有序序列。
快速排序的实现
在这里，最重要的就是将数组划分为两部分：左边比 key 小，右边比 key 大。
对于将数组划分为两部分的方法有三种，本质思想都是一样的，但实现的方法却有点不同。
三种划分方式
以下面一组数据为例，我们假设 key 的值是最左边的值。
Hoare 版本
它是定义了两个下标（L 与 R），分别从两侧开始找，R 先走，找到比 key 小的值，停下来；L 开始走，找到比 key 大的值，停下来，交换对应的值即可，然后继续重复，直到两者相遇，交换相遇点与 key 的值即可。
为什么两者相遇，交换相遇点与 key 的值？
两者会以什么方式相遇，简单，要么 L 在移动的时候遇到了 R，要么 R 在移动的时候遇到了 L。
- L 在移动的时候遇到了 R 的情况：由于是R 先走的缘故，所以 R 此时指向的是比 key 小的值，此时 L 遇到了 R，相遇点即为比 key 小的值。
- R 在移动的时候遇到了 L 的情况：此时 L 停留在上次交换的位置，上次交换的是比 key 小的值，即相遇点为比 key 小的值，也有可能 L 停留在 key 的位置。结果都是一样。
为什么 R 先走？
如果 L 先走的话，可以把 key 设在右边。
int QuickSortPartition(int* a, int left, int right) {
int key = left; // 选择最左边为基准
while (left < right) {
while (left < right && a[right] >= a[key]) right--;
while (left < right && a[left] <= a[key]) left++;
Swap(&a[right], &a[left]);
}
Swap(&a[left], &a[key]); // 将基准值放到正确位置
return left;
}
