排序算法里，快速排序绝对是个常青树。1962 年 Tony Hoare 提出它的时候，大概没想到几十年后它仍被广泛使用，还因此得了图灵奖。快排的核心是分治：选一个基准值（key），把数组切成两段，左边全是小于 key 的，右边全是大于 key 的，然后对左右两段递归做同样的事。思路直白，但实现起来有些细节值得琢磨，尤其是一趟划分到底怎么划。
一趟划分：Hoare 的方法
实现划分的方法有好几种，Hoare 最初提出的版本用两个下标 L 和 R，从数组两端往中间扫描。通常取最左边元素做 key，然后 R 先向左走，找到比 key 小的值停下；接着 L 向右走，找到比 key 大的值停下；交换两者的值。反复这个过程，直到 L 和 R 相遇。最后将 key 与相遇点的值交换，一趟划分就结束了。
这里常有人纠结：相遇点万一比 key 大，交换后不就乱了吗？其实不会。因为 R 先走，所以 R 停下的位置一定是小于 key 的（或 R 一直走到 L，而 L 上次交换的位置是小于 key 的）。如果 L 先走，就可能把大于 key 的值换到左边——所以 Hoare 法要求 R 先动，或者 key 选在右边时 L 先动。这是个小巧思，也是面试中常见的坑。
代码直接写出：
int _QuickSort(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; // 返回基准值最终位置
}
这本是单趟划分，要完成整个排序需要递归调用：
void QuickSort(int* a, int left, int right) {
if (left >= right) // 递归终止条件：区间只有一个元素或为空
return;
int mid = _QuickSort(a, left, right); // 划分操作，返回基准值的最终位置
QuickSort(a, left, mid - );
QuickSort(a, mid + , right);
}
