快速排序（QuickSort）完全指南 —— 从原理到工业级优化
博客：TomGo
本文涵盖：基础原理、双指针法、前后指针法、三数取中、小区间优化、非递归版本、易错点、面试高频考点
目录
一、快排是什么？大白话说原理
二、基础版快排（教学版）
三、双指针分区详解（易错重点！）
[3.1 整体流程](#3.1 整体流程)
[3.2 易错点一：比较符号必须带等号](#3.2 易错点一：比较符号必须带等号)
[3.3 易错点二：end 必须先走](#3.3 易错点二：end 必须先走)
[3.4 易错点三：循环条件用 begin < end，不是 left < right](#3.4 易错点三：循环条件用 begin < end，不是 left < right)
[3.5 易错点四：终止条件用 >= 不是 >](#3.5 易错点四：终止条件用 >= 不是 >)
四、前后指针分区法（另一种写法）
[4.1 为什么 ++prev 不能放在 swap 里？](#4.1 为什么 ++prev 不能放在 swap 里？)
[4.2 为什么条件是 < 不是 <=（不带等号）](#4.2 为什么条件是 < 不是 <=（不带等号）)
[4.3 相遇时为什么不用 swap？](#4.3 相遇时为什么不用 swap？)
五、工业级优化版（完整代码）
[5.1 三数取中为什么能避免退化？](#5.1 三数取中为什么能避免退化？)
[5.2 InsertSort 参数易错点](#5.2 InsertSort 参数易错点)
[5.3 GetMidi 后必须先 Swap 再记 keyi](#5.3 GetMidi 后必须先 Swap 再记 keyi)
六、非递归版本（用栈模拟）
[6.1 非递归易错点](#6.1 非递归易错点)
七、三种分区方法对比
八、复杂度分析
九、面试高频考点
十、总结：写代码时的核查清单
一、快排是什么？大白话说原理
快排的核心思想只有一句话：
选一个基准值（pivot），把比它小的全放左边，比它大的全放右边，然后递归处理左右两侧。
每次分区之后，pivot 就永远待在它正确的位置上了，不需要再动。
举个例子，数组 [5, 3, 8, 1, 6, 2, 7, 4]，选 pivot = 5：
复制代码
分区后：[3, 1, 2, 4] | 5 | [8, 6, 7]
↑
pivot归位
然后递归排左边的 [3,1,2,4] 和右边的 [8,6,7]，每次都把一个元素永久归位，直到全部有序。
二、基础版快排（教学版）
最简单的版本，直接看懂原理：
cpp
复制代码
// 分区函数，返回pivot归位后的下标
int Partition(int* a, int left, int right)
{
int keyi = left; // pivot放在最左边
int begin = left;
int end = right;
while (begin < end)
{
// end从右向左找小于pivot的值（右边找小）
while (begin < end && a[end] >= a[keyi])
end--;
// begin从左向右找大于pivot的值（左边找大）
while (begin < end && a[begin] <= a[keyi])
begin++;
Swap(&a[begin], &a[end]);
}
// begin和end相遇，把pivot换到中间
Swap(&a[keyi], &a[begin]);
return begin;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = Partition(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
三、双指针分区详解（易错重点！）
3.1 整体流程
复制代码
初始：[ pivot | ......begin......end...... ]
↑ ↑
keyi=left right
end从右找小 → begin从左找大 → swap → 重复
begin==end时 → swap(pivot, begin) → pivot归位
3.2 易错点一：比较符号必须带等号
内层循环条件必须是 >= 和 <=，不能是 > 和 <。
原因： 不带等号时，遇到和 pivot 相等的元素，两个指针都会停下来，反复 swap 同一对位置，形成死循环。
复制代码
// 错误写法（遇到重复元素死循环）
while (begin < end && a[end] > a[keyi]) // 少了=
end--;
while (begin < end && a[begin] < a[keyi]) // 少了=
begin++;
// 正确写法
while (begin < end && a[end] >= a[keyi])
end--;
while (begin < end && a[begin] <= a[keyi])
begin++;
3.3 易错点二：end 必须先走
pivot 放在 a[left]，end 必须先走（从右找小），begin 再走（从左找大）。
原因： 最后 Swap(&a[keyi], &a[begin]) 时，要保证 a[begin] 的值 <= pivot，pivot 换过去才正确。end 先走能保证 begin 最终停在一个 <= pivot 的位置。如果 begin 先走，相遇位置可能是 > pivot 的值，swap 后 pivot 跑到错误位置。
3.4 易错点三：循环条件用 begin < end，不是 left < right
cpp
复制代码
// 错误：left和right从来不变，死循环！
while (left < right)
{
while (left < right && a[end] >= a[keyi]) // 内层也是left end--; } // 正确：用begin和end控制 while (begin < end) { while (begin < end && a[end] >= a[keyi]) end--; while (begin < end && a[begin] <= a[keyi]) begin++; Swap(&a[begin], &a[end]); } 3.5 易错点四：终止条件用 >= 不是 > // 错误：left==right时（单个元素）会继续执行**，可能越界** if (left > right) return; // 正确 if (left >= right) return; 四、前后指针分区法（另一种写法） prev 始终指向"小于 pivot 区域"的最右边界，cur 向右扫描。 复制代码 int PartitionPP(int* a, int left, int right) { int keyi = left; int prev = left; int cur = prev + 1; while (cur <= right) { // a[cur] < pivot 才收进小区域 // ++prev != cur：防止自己和自己swap（优化） if (a[cur] < a[keyi] && ++prev != cur) Swap(&a[prev], &a[cur]); cur++; } Swap(&a[prev], &a[keyi]); // pivot归位 return prev; } 4.1 为什么 ++prev 不能放在 swap 里？ 复制代码 // 错误写法 if (a[cur] < a[keyi] && prev + 1 != cur) Swap(&a[++prev], &a[cur]); 当 a[cur] < pivot 成立，但 prev+1 == cur（cur紧挨着prev）时： 正确行为：小区域扩张一格（++prev），cur就地并入，不需要swap 错误写法：整个if不执行，prev没有自增，小区域边界丢了 正确写法： cpp 复制代码 if (a[cur] < a[keyi]) { ++prev; if (prev != cur) Swap(&a[prev], &a[cur]); } 或者原版的 ++prev != cur 放在条件里，无论是否swap，prev 都已经自增。 4.2 为什么条件是 < 不是 <=（不带等号） prev 管的是"严格小于 pivot"的区域，等于 pivot 的元素不属于这个区域，语义上就不应该收进来。等于 pivot 的元素自然留在右边，pivot 归位后： 复制代码 左边：< pivot | pivot | 右边：>= pivot 边界清晰，不会混淆。 4.3 相遇时为什么不用 swap？ ++prev == cur 时，两个指针指的是同一个位置，Swap(&a[prev], &a[cur]) 等于自己和自己换，结果不变，跳过只是省掉多余操作。 五、工业级优化版（完整代码） 基础快排有两个致命缺陷： 有序数组退化：每次选最左元素为 pivot，有序数组每次分区极度不均，O(n²) 小区间递归开销大：区间只有 3~5 个元素时，递归压栈弹栈的开销比直接排序还大 解决方案：三数取中 + 小区间切换插入排序 cpp 复制代码 // 插入排序（用于小区间） void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int end = i; int temp = a[end + 1]; while (end >= 0) { if (a[end] > temp) { a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = temp; } } // 三数取中：取 left、mid、right 三个位置中值的下标 int GetMidi(int* a, int left, int right) { int mid = left + (right - left) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) return mid; else if (a[left] < a[right]) return right; else return left; } else // a[left] >= a[mid] { if (a[mid] > a[right]) return mid; else if (a[left] > a[right]) return right; else return left; } } void QuickSort(int* a, int left, int right) { if (left >= right) return; // 优化一：小区间切换插入排序 if ((right - left + 1) <= 10) { InsertSort(a + left, right - left + 1); // 注意：a+left 是偏移后的起始地址，right-left+1 是长度 // 不能写 InsertSort(a, right-left+1)，那样会从数组开头排 } else { // 优化二：三数取中选pivot，避免有序数组退化 int midi = GetMidi(a, left, right); Swap(&a[left], &a[midi]); // 先swap再记keyi，此时a[left]才是中间值 // 顺序：GetMidi → Swap → keyi=left，不能乱 int keyi = left; int begin = left; int end = right; while (begin < end) { while (begin < end && a[end] >= a[keyi]) end--; while (begin < end && a[begin] <= a[keyi]) begin++; Swap(&a[begin], &a[end]); } Swap(&a[keyi], &a[begin]); keyi = begin; QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } } 5.1 三数取中为什么能避免退化？ 有序数组 [1,2,3,4,5,6,7,8]： 朴素快排：每次取 a[left]=1 为 pivot，分区后左边空，右边全部，递归深度 n，退化 O(n²) 三数取中：取 left=1、mid=4、right=8，中间值是 4，分区均匀，递归深度 log n，保持 O(n log n) 5.2 InsertSort 参数易错点 注意： 传的是数组要开始改的元素的地址 复制代码 // 错误 InsertSort(a, right - left + 1); // 从数组开头排，范围不对 InsertSort(a + left, right - left); // 长度少算了一个 // 正确 InsertSort(a + left, right - left + 1); // a+left：偏移到子数组起始位置 // right-left+1：子数组长度（闭区间，两端都算） 5.3 GetMidi 后必须先 Swap 再记 keyi 复制代码 // 错误：忘记swap，pivot根本不是中间值，三数取中白做了 int keyi = left; int midi = GetMidi(a, left, right); // 直接开始分区... // 正确：顺序固定 int midi = GetMidi(a, left, right); // 1. 找中间值下标 Swap(&a[left], &a[midi]); // 2. 换到a[left] int keyi = left; // 3. 记住pivot位置 六、非递归版本（用栈模拟） 递归版在数据量极大时可能栈溢出，非递归用手动栈解决。 思路：把区间 [left, right] 压栈，循环弹出处理，分区后把左右子区间再压栈。 cpp 复制代码 // 数组模拟栈 #define MAXSIZE 10000 typedef struct Stack { int data[MAXSIZE]; int top; } Stack; void STInit(Stack* st) { st->top = -1; } void STPush(Stack* st, int val) { st->data[++(st->top)] = val; } int STPop(Stack* st) { return st->data[(st->top)--]; } int STEmpty(Stack* st) { return st->top == -1; } void STDestroy(Stack* st) { /* 数组无需释放 */ } // 分区函数（把分区逻辑单独抽出来） int Partition(int* a, int left, int right) { int midi = GetMidi(a, left, right); Swap(&a[left], &a[midi]); int keyi = left; int begin = left, end = right; while (begin < end) { while (begin < end && a[end] >= a[keyi]) end--; while (begin < end && a[begin] <= a[keyi]) begin++; Swap(&a[begin], &a[end]); } Swap(&a[keyi], &a[begin]); return begin; } void QuickSortNonR(int* a, int left, int right) { Stack st; STInit(&st); // 压栈顺序：right先压，left后压 // 因为栈后进先出，left要先弹出 STPush(&st, right); STPush(&st, left); while (!STEmpty(&st)) { int l = STPop(&st); int r = STPop(&st); if (l >= r) // 无效区间跳过，用continue不用return continue; int keyi = Partition(a, l, r); // 压右子区间：right先压，keyi+1后压 STPush(&st, r); STPush(&st, keyi + 1); // 压左子区间：keyi-1先压，l后压 STPush(&st, keyi - 1); STPush(&st, l); } STDestroy(&st); // 记得销毁，避免内存泄漏 } 6.1 非递归易错点 易错点 说明 无效区间用 continue l >= r 时用 continue 跳过，不能用 return（会退出整个函数） 压栈顺序 right 先压，left 后压，保证 left 先弹出 忘记 STDestroy 动态分配的栈要释放，数组模拟的栈无需释放但要有好习惯 while 条件写错 !STEmpty(&st)，栈不为空就继续 七、三种分区方法对比 方法 代码复杂度 适合场景 双指针（Hoare） 中等 通用，理解最重要 前后指针 较简单 逻辑清晰，适合手写 非递归 较复杂 数据量极大，防栈溢出 八、复杂度分析 情况 时间复杂度 说明 平均 O(n log n) 每次分区均匀，递归深度 log n 最好 O(n log n) 每次 pivot 恰好在中间 最坏 O(n²) 有序数组 + 朴素快排，三数取中可避免 空间 O(log n) 递归调用栈深度 稳定性：不稳定（swap 会改变相等元素的相对顺序） 九、面试高频考点 Q1：快排最坏情况是什么？怎么避免？ 最坏情况是有序或逆序数组，朴素快排每次 pivot 都选到最值，分区极度不均，退化 O(n²)。避免方法：三数取中选 pivot，或者随机选 pivot。 Q2：快排是稳定排序吗？ 不稳定。swap 操作会改变相同值元素的相对位置。 Q3：快排和归并排序哪个快？ 平均情况快排更快，因为常数系数小、缓存友好。但归并是稳定排序，最坏情况也是 O(n log n)，快排最坏 O(n²)。实际工程中 STL 的 std::sort 用的是 Introsort（快排 + 堆排 + 插入排序的组合）。 Q4：小区间为什么切换插入排序？阈值为什么是10？ 递归到小区间时，函数调用压栈弹栈的开销占比很高，插入排序在小数据量时实际性能更好（常数系数极小）。阈值 10 是工程经验值，不是理论推导，STL 各实现普遍用 8~16。 Q5：非递归快排有什么意义？ 递归版依赖系统调用栈，数据量极大时（递归深度超过系统栈限制）会栈溢出。非递归用堆上的手动栈，不受系统栈大小限制。 Q6：三数取中的 mid 下标怎么算？ 复制代码 int mid = left + (right - left) / 2; // 不能写 (left + right) / 2，left+right可能整数溢出 Q7：为什么最后是和 begin 换而不是和 end 换？ begin == end 时两者是同一位置，换谁都一样。但逻辑上 pivot 在 left，begin 是小区域右边界，和 begin 换语义更清晰。关键是要保证相遇位置的值 <= pivot，end 先走能保证这一点。 十、总结：写代码时的核查清单 写完快排之后，对照检查： if (left >= right) return; ------ 终止条件用 >=，不是 > 否则会过度访问 内层循环用 begin < end 控制，不是 left < right end 先走，begin 后走 比较符号带等号：a[end] >= a[keyi]，a[begin] <= a[keyi] 最后 Swap(&a[keyi], &a[begin]) 把 pivot 归位，不能漏 InsertSort(a + left, right - left + 1) 两个参数都不能写错 GetMidi → Swap → keyi = left，顺序不能乱 非递归版：无效区间用 continue，记得 STDestroy
