快速排序简介
快速排序（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; // 递归终止条件
int mid = QuickSortPart(a, left, right);
QuickSort(a, left, mid - 1); // 递归排序左半部分
QuickSort(a, mid + 1, right); // 递归排序右半部分
}
此外还有挖坑法和前后指针法，Hoare 版本因性能优异常被标准库采用。
快速排序的优化
三数取中法选择基准值
如果基准值总是接近最小或最大值，会导致性能退化。三数取中法选取首、尾、中间三个数的中位数作为基准，使基准更接近真实中点。
int GetMidIndex(int* a, int left, int right) {
int mid = left + (right - left) / 2;
if (a[mid] > a[left]) {
if (a[mid] < a[right]) return mid;
else if (a[left] < a[right]) return right;
else return left;
} else {
if (a[left] < a[right]) return left;
else if (a[mid] < a[right]) return right;
else return mid;
}
}
小区间转插入排序
数据量较小时，递归开销反而大于收益。当区间长度小于阈值（如 10）时，改用插入排序效率更高。
void QuickSortOptimized(int* a, int left, int right) {
if (left >= right) return;
if (right - left + 1 <= 10) {
InsertSort(a + left, right - left + 1);
return;
}
int mid = QuickSortPart(a, left, right);
QuickSortOptimized(a, left, mid - 1);
QuickSortOptimized(a, mid + 1, right);
}
其他优化
- 三路划分：针对大量重复元素，将数组分为
<key、=key、>key三部分。 - 自省排序：当递归过深时切换为堆排序，防止最坏情况。
非递归实现
递归依赖系统栈，非递归则使用显式栈模拟。每次将待处理的 left 和 right 压栈，出栈后划分，再将新区间入栈。
void QuickSortNonR(int* a, int left, int right) {
Stack st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (!StackEmpty(&st)) {
right = StackTop(&st); StackPop(&st);
left = StackTop(&st); StackPop(&st);
if (left >= right) continue;
int mid = QuickSortPart(a, left, right);
StackPush(&st, mid + 1);
StackPush(&st, right);
StackPush(&st, left);
StackPush(&st, mid - 1);
}
StackDestroy(&st);
}
性能分析
时间复杂度
- 平均：O(N log N)，假设基准值每次都能平分区间。
- 最坏：O(N²)，当数组完全有序且基准值选择不当时发生，但可通过优化避免。
空间复杂度
- 递归：O(log N)，取决于递归树深度。
- 非递归：同样为 O(log N)，取决于栈的大小。
稳定性
- 不稳定：相同元素的相对顺序在交换过程中可能改变。
总结
快速排序通过'选基准、分区间、递归处理'的分治思想，实现了高效排序。其核心优势在于平均时间复杂度接近 O(N log N) 且额外空间开销小，因此广泛应用于标准库中。虽然存在最坏情况和不稳定的缺点，但通过三数取中、小区间插排、三路划分等优化手段，在实际场景中表现依然出色。递归与非递归两种实现各有适用场景，前者直观，后者更适合对栈溢出敏感的工程环境。
