快速排序简介
快速排序（Quick Sort）是算法界的经典之作，由 Tony Hoare 在 1962 年提出。凭借分治思想与高效的平均性能，它成为众多编程语言标准库中的默认排序算法。
相比于冒泡、选择等基础排序，快排更像一位策略型指挥官：先选出一个基准值（key），通过一趟划分将比基准小的元素放左边，大的放右边，再递归处理子区间。得益于这种思路，它在大多数情况下能以 O(N log N) 的时间复杂度完成任务，且空间开销较小。当然，快排并非完美，极端情况下可能退化为 O(N²)，且不是稳定排序。
基本思想
- 在数组中选择一个基准值（key）；
- 将数组划分为两部分：左边比 key 小，右边比 key 大；
- 递归排序左右两部分；
- 最终得到有序序列。
快速排序的实现
划分的核心在于将数组分为小于和大于基准的两部分。常见的划分方式有三种，本质一致但实现细节不同。
Hoare 版本
以数组最左边的值为基准。定义两个下标 L 与 R，分别从两侧开始查找。R 先走，找到比 key 小的值停下；L 接着走，找到比 key 大的值停下，交换两者位置。重复直到相遇，最后交换相遇点与 key 的值。
为什么 R 先走？ 如果 L 先走，当 L 停在比 key 大的位置时，若此时 R 还没动或停在比 key 大的位置，交换后可能导致基准值被换到错误的一侧。R 先走能保证相遇点一定指向比 key 小（或等于）的位置，确保基准值归位正确。
int QuickSortPart(int* a, int left, int right) {
int key = left; // 选择最左边为基准索引
while (left < right) {
// R 先走，找比 key 小的值
while (left < right && a[right] >= a[key]) right--;
// L 后走，找比 key 大的值
while (left < right && a[left] <= a[key]) left++;
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]); // 将基准值放到正确位置
return left; // 返回基准值最终位置
}
单次划分完成后，递归处理左右区间即可。
void QuickSort(int* a, int left, int right) {
if (left >= right) return; // 递归终止条件
mid = (a, left, right);
(a, left, mid - );
(a, mid + , right);
}
