快速排序在标准库里几乎是标配，但自己写的时候，不少细节都会影响性能。这是我整理快排实现时的一些笔记，从最基本的版本开始，逐步加上三数取中、小数组切换策略，最后用显式栈替代递归，避免爆栈。
最简单的快排
算法思想是分治：选一个 pivot，把数组分成左右两部分，左边都比 pivot 小，右边都比它大。pivot 的位置就确定了，然后递归处理左右。但怎么分区呢？常见的做法是 Hoare 的左右指针法。
void QuickSort1(int* a, int left, int right) {
if (left >= right) {
return;
}
int key = left; // 确定 key 的值，为第一个元素
int L = left;
int R = right; // 记录原始左右下标
while (left < right) {
// 右小人向左走，直到找到比 key 小的值
while (left < right && a[right] >= a[key]) {
right--;
}
// 左小人向右走，直到找到比 key 大的值
while (left < right && a[left] <= a[key]) {
left++;
}
Swap(&a[left], &a[right]); // 交换大的值和小的值
}
Swap(&a[right], &a[key]); // 最后交换 key 和相遇点对应的值
key = right; // key 的下标也要改变
QuickSort1(a, L, key - 1); // 递归 key 的左区间
QuickSort1(a, key + 1, R); // 递归 key 的右区间
}
这个版本固定选第一个元素为 pivot。如果数组已经有序，那每次分区就极其不平衡，一边为空，另一边是 n-1 个元素，递归深度变成 O(n)，时间复杂度退化到 O(n²)。所以需要改进 pivot 的选择。
三数取中：避开最坏情况
一个简单且有效的优化是'三数取中'：从第一个、中间、最后一个元素里挑一个值在中间的，换到第一位当 pivot。这样能大幅降低在常见有序或接近有序数组上退化的概率。
int FindKey(int* a, int left, int right) {
int mid = (left + right) / 2;
if (a[left] > a[right]) {
if (a[right] > a[mid]) {
return right;
} else if (a[mid] > a[left]) {
return left;
} else {
return mid;
}
} else {
if (a[left] > a[mid]) {
return left;
} else if (a[mid] > a[right]) {
return right;
} else {
return mid;
}
}
}
然后快排函数改成：
void QuickSort1(int* a, int left, int right) {
if (left >= right) {
return;
}
int L = left;
int R = right;
int key = FindKey(a, left, right);
Swap(&a[key], &a[left]); // 将选定的 key 换到首项
key = left;
while (left < right) {
while (left < right && a[right] >= a[key]) {
right--;
}
while (left < right && a[left] <= a[key]) {
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[right], &a[key]);
key = right;
QuickSort1(a, L, key - 1);
QuickSort1(a, key + 1, R);
}
这样基本解决了有序数组退化的痛点，但递归深度仍然可能很大。
小数组的递归开销
当子数组长度很小的时候（比如10个以下），继续用快排递归并不划算——递归调用和栈开销比实际排序还大。这时不如直接上插入排序或堆排序。我习惯用堆排序，因为它不会退化，实现也简单。
先看插入排序的代码：
void InsertSort(int* a, int n) {
for (int i = 0; i < n - 1; i++) {
int end = i;
int tmp = a[end + 1];
while (end >= 0) {
if (tmp < a[end]) {
a[end + 1] = a[end];
--end;
} else {
break;
}
}
a[end + 1] = tmp;
}
}
堆排序相关的调整函数：
void AdJustDown(int* a, int parent, int size) {
int child = 2 * parent + 1;
while (child <= size - 1) {
if (child + 1 <= size - 1 && a[child + 1] > a[child]) {
child++;
}
if (a[child] > a[parent]) {
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
void HeapSort(int* a, int sz) {
int i;
for (i = (sz - 1 - 1) / 2; i >= 0; i--) {
AdJustDown(a, i, sz);
}
for (i = sz - 1; i > 0; i--) {
Swap(&a[0], &a[i]);
AdJustDown(a, 0, i);
}
}
分区函数 PartSort1 就是前面三数取中的分区逻辑，封装一下：
int PartSort1(int* a, int left, int right) {
int key = FindKey(a, left, right);
Swap(&a[key], &a[left]);
key = left;
while (left < right) {
while (left < right && a[right] >= a[key]) {
right--;
}
while (left < right && a[left] <= a[key]) {
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[right], &a[key]);
return right;
}
最终的递归快排这样写：如果区间长度小于10，调用堆排序；否则正常分区然后递归。
void QuickSort1(int* a, int left, int right) {
if (left >= right) {
return;
}
int g = right - left + 1;
if (g < 10) {
// 小区间使用堆排序优化
HeapSort(a + left, g);
} else {
int key = PartSort1(a, left, right);
QuickSort1(a, left, key - 1);
QuickSort1(a, key + 1, right);
}
}
用栈代替递归
递归版本的快排依赖系统栈，数据量一大就可能栈溢出。我们可以用显式的栈模拟递归过程，避免这个风险。思路很简单：用一个栈保存待处理的区间左右边界，每次从栈中取一个区间进行分区，如果左右子区间长度大于1（或大于阈值），就压栈。当栈为空时排序完成。
栈的实现（这里用动态数组，不赘述）：
typedef int STDataType;
typedef struct Stack {
STDataType* a;
int size;
int capacity;
} Stack;
void StackInit(Stack* ps);
void StackPush(Stack* ps, STDataType data);
void StackPop(Stack* ps);
STDataType StackTop(Stack* ps);
int StackSize(Stack* ps);
int StackEmpty(Stack* ps);
void StackDestroy(Stack* ps);
void StackInit(Stack* ps) {
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->size = 0;
}
void StackPush(Stack* ps, STDataType data) {
assert(ps);
if (ps->size == ps->capacity) {
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (tmp == NULL) {
perror("realloc");
return;
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->size] = data;
ps->size++;
}
void StackPop(Stack* ps) {
assert(ps && ps->size > 0);
ps->size--;
}
STDataType StackTop(Stack* ps) {
assert(ps && ps->size > 0);
return ps->a[ps->size - 1];
}
int StackSize(Stack* ps) {
assert(ps);
return ps->size;
}
int StackEmpty(Stack* ps) {
assert(ps);
return ps->size == 0;
}
void StackDestroy(Stack* ps) {
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->size = 0;
}
非递归快排主体：
void QuickSortNonR(int* a, int left, int right) {
Stack S;
StackInit(&S);
StackPush(&S, right);
StackPush(&S, left);
while (!StackEmpty(&S)) {
int L = StackTop(&S);
StackPop(&S);
int R = StackTop(&S);
StackPop(&S);
if (L >= R) {
continue;
}
int g = R - L + 1;
if (g < 10) {
HeapSort(a + L, g);
} else {
int key = PartSort1(a, L, R);
if (R - key - 1 > 1) {
StackPush(&S, R);
StackPush(&S, key + 1);
}
if (key - 1 - L > 1) {
StackPush(&S, key - 1);
StackPush(&S, L);
}
}
}
StackDestroy(&S);
}
快排的平均效率很高，三数取中避开了最坏情况，小区间优化减少了递归开销，非递归版本在数据量大时更可靠。这些组合起来，就是标准库里快排的典型实现思路。
