排序这件事看起来简单，可一旦数据量上来，选错算法就是肉眼可见的卡顿。之前在某后台系统的数据清洗任务里，我用最朴素的双层循环处理几万条记录，跑一次要几十秒，换成快速排序后直接降到毫秒级。从那以后，不管面试还是实际开发，快排都是我优先考虑的排序方案。这篇就从原理、基准选择、优化手段到工程落地，把“数据结构与算法篇-快速排序”能讲的坑和技巧一次性说透。
1. 快速排序到底在快什么：分治思想的一次“精妙赌博”
1.1 从一次现实需求说起
先还原一个场景：某内部管理平台需要按时间戳排序一批操作日志，数据量大概在几十万条。我一开始图省事直接上了冒泡排序的改进版，结果日志一多，接口响应直接超时。后来换成快排思路，排序耗时从秒级降到百毫秒级，整个页面才活过来。
快速排序之所以叫“快速”，不是因为它在所有情况下都是最快的，而是它在绝大多数真实场景下，能把平均时间复杂度做到 O(n log n)，而且常数因子非常小。这一点在数据量动辄百万级的今天尤其关键。同样是 O(n log n) 的复杂度，快排的实际运行速度通常明显优于堆排序，代码简洁度也优于归并排序。
1.2 核心三步：选基准、分区、递归
快速排序的核心逻辑可以拆成三步：
- 从待排序序列中选一个元素作为基准（pivot）。
- 把序列重新排列，让所有比基准小的元素都到基准左边，所有比基准大的元素都到基准右边，这个过程叫分区（partition）。
- 对基准左右两个子序列递归执行前两步，直到子序列长度小到不能再分。
这个思路的精妙之处在于：每一轮分区之后，基准元素就已经落在了它最终应该在的位置上。也就是说，它不像插入排序那样需要一步步挪动，而是通过一次“大洗牌”直接锁定一个元素的最终位置，然后分而治之。
1.3 生活类比：整理一摞试卷
理解快排最简单的方式，是想象你手头有一摞乱序的试卷要按分数从低到高排。你不会一张一张地两两比较，而是先抽出一张试卷作为“分界线”，比如 75 分。然后快速把低于 75 分的扔到左边，高于 75 分的扔到右边。这样一来，这张 75 分的试卷就已经在它该在的位置上了。接着，你对左边一堆和右边一堆分别重复同样的操作，直到每堆只剩一张。
这就是分治思想：把一个大规模问题拆成两个独立的小规模问题，各自解决后合并结果。快排的“合并”几乎是零成本的，因为分区阶段已经完成了核心工作。
提示：快排的性能好不好，很大程度上取决于你抽的“分界线”是否靠近中间值。如果每次抽到的都是极端值，比如最低分或最高分，那左边或右边就会有一边是空的，快速排序就会退化成冒泡排序的复杂度 O(n^2)。这是快排最需要警惕的一点。
2. 基准元素的选择：所有性能问题的源头
2.1 最坏情况是怎么逼出来的
如果每次选基准都选到当前区间的最小值或最大值，分区结果就是一边是空区间、一边是 n-1 个元素的区间。这时候递归深度会变成 n，每层做的比较次数累加起来是 n + (n-1) + (n-2) + ... + 1，也就是 O(n^2)。
最典型的触发场景就是：对一个近乎有序的序列使用“固定取第一个元素”或“固定取最后一个元素”作为基准。比如一个已经排好序的数组，你固定取第一个元素作为基准，每次分区都会分成左边空、右边 n-1 个元素，性能直接崩塌。
我最初写快排的时候，图省事直接取arr[right]作为基准，拿一组有序数据一测，朴素实现跑了几秒都没结束，而随机选基准的版本几十毫秒就完成了。这个对比让我印象很深。
2.2 常见的选基准策略与实测对比
常见的选基准策略有几种：
| 策略 | 做法 | 优点 | 缺点 |
|---|---|---|---|
| 固定位置 | 取第一个或最后一个元素 | 实现最简单 | 对近乎有序数据容易触发最坏情况 |
| 随机选取 | 在区间内随机选下标 | 能有效避免恶意输入导致的退化 | 随机数生成有少量额外开销 |
| 三数取中 | 取左、中、右三个位置的元素，选择中间值作为基准 | 对部分有序数据效果好，兼顾稳定性和性能 | 实现稍微复杂，对随机数据收益不明显 |
从实测来看，三数取中在工程上是最常用的折中方案。它不依赖随机数，还能有效避免“固定取端点”在有序数据下的退化问题。比如取arr[left]、arr[mid]、arr[right]三个值，排序后取中间那个作为基准，代码也不复杂。
2.3 为什么“随机化”能救快排
随机化基准的核心思想非常朴素：我无法保证每次都能选到好的基准，但我可以让“每次都不幸选到最差基准”这件事的概率变得极小。根据概率分析，随机选择基准时，期望时间复杂度就是 O(n log n)，而且这个期望不依赖于输入数据的初始顺序。
所以面试时如果被问到“如何避免快排的最坏情况”，标准答案通常是两个方向：一是随机化选基准，二是三数取中。工程上我更推荐三数取中，因为它的表现更稳定，也不会像随机选基准那样需要额外的随机函数调用。
注意：随机选基准并不能彻底消除最坏情况，它只是让最坏情况变得“几乎不可能发生”。如果你的应用场景对最坏情况延迟极其敏感，那应该考虑堆排序或者内省排序这种有明确上界的算法。
3. 从能用升级到好用：插入排序、三路快排与尾递归
3.1 小区间停机：把最后一棒交给插入排序
快排的递归是到子序列长度为 1 才停，但实际操作中你会发现：当子序列长度小于某个阈值时，继续用快排反而浪费。原因很简单，快排在小区间上的递归调用开销、函数跳转开销，可能比直接插入排序还要大。
插入排序虽然是 O(n^2) 的复杂度，但它的常数因子极小，而且在近乎有序的小区间上，它几乎只做很少的移动。工程上常见的做法是在快排递归中加一个判断：
const int kInsertionThreshold = 16; void quickSortWithInsertion(vector<int>& arr, int left, int right) { if (left >= right) return; if (right - left + 1 <= kInsertionThreshold) { insertionSort(arr, left, right); return; } int p = partition(arr, left, right); quickSortWithInsertion(arr, left, p - 1); quickSortWithInsertion(arr, p + 1, right); }阈值一般取 12 到 32 之间。我习惯用 16，实测效果比较均衡。这个优化的本质是：大问题上用分治，小问题上用暴力。你可以把阈值当成一个“切换开关”，它在减少递归调用次数和保留插入排序的优势之间找到了平衡。
3.2 三路快排：处理大量重复元素的利器
经典快排的分区结果是“小于基准 | 基准 | 大于基准”，但遇到大量重复元素时，等于基准的元素会被反复处理，白白浪费很多比较和交换。三路快排的改进是分成三段：“小于基准”、“等于基准”、“大于基准”。等于基准的元素直接留在中间，下一轮递归根本不用再碰它们。
这个优化在数据重复率高的场景下提升非常明显。举个实际例子：某日志分析任务中，大部分日志的优先级字段只有几种取值，用经典快排要排很久，换成三路快排后耗时降了大约一半。
三路快排的 C++ 实现思路如下：
void quickSort3Ways(vector<int>& arr, int left, int right) { if (left >= right) return; int pivot = arr[left + (right - left) / 2]; int i = left; int lt = left; int gt = right; while (i <= gt) { if (arr[i] < pivot) { swap(arr[i], arr[lt]); ++i; ++lt; } else if (arr[i] > pivot) { swap(arr[i], arr[gt]); --gt; } else { ++i; } } quickSort3Ways(arr, left, lt - 1); quickSort3Ways(arr, gt + 1, right); }这段代码的核心是用lt和gt两个指针夹出一个“等于基准”的中段，遍历下标i在中段里移动。遇到小于基准的值就往左丢，遇到大于基准的值就往右丢，等于基准的值原地不动。最后递归只处理左边的[left, lt-1]和右边的[gt+1, right]。
3.3 尾递归优化到底优化了什么
快排的递归深度在最坏情况下可能达到 O(n)，比如每次都选到最差基准时。递归过深有两个问题：一是函数调用栈可能溢出，二是函数调用本身有性能开销。尾递归优化的思路是把其中一侧的递归改成循环，从而减少栈深度。
典型写法是这样的：
void quickSortTailRecursive(vector<int>& arr, int left, int right) { while (left < right) { int p = partition(arr, left, right); // 递归处理较短的一侧 if (p - left < right - p) { quickSortTailRecursive(arr, left, p - 1); left = p + 1; } else { quickSortTailRecursive(arr, p + 1, right); right = p - 1; } } }这里有个细节值得注意：并不是随便把一侧改成循环就行，最好先递归处理较短的一侧，再循环处理较长的一侧。这样做的目的是让递归深度始终控制在 O(log n) 级别，因为每次递归的区间长度最多是原来的一半。
3.4 其他实战优化：非递归版与并行化
如果担心递归栈溢出，可以完全改用显式栈模拟递归。这种写法在外部排序、嵌入式环境等对栈空间敏感的场景下更稳妥。基本思路是用一个栈保存待处理的区间左右边界，循环弹栈、分区、压栈。
void quickSortIterative(vector<int>& arr, int left, int right) { stack<pair<int, int>> stk; stk.push({left, right}); while (!stk.empty()) { auto [l, r] = stk.top(); stk.pop(); if (l >= r) continue; int p = partition(arr, l, r); stk.push({l, p - 1}); stk.push({p + 1, r}); } }另外，多核环境下还可以在分区完成后，对左右两个子区间分别开线程并行排序。不过这里有个度：子区间太小时并行的收益会被线程创建开销抵消。一般建议区间长度大于某个阈值，比如几万，才值得并行。
4. 复杂度分析进阶：平均、最坏、稳定性与内存
4.1 平均 O(n log n) 怎么来的
直观理解平均复杂度，可以用“期望递归深度”和“每层总比较次数”来拆分。每一层分区，把所有子区间的比较次数加起来大约是 O(n)。如果基准选得比较理想，每次都能把区间大致对半分开，那递归深度就是 O(log n)。两者相乘，平均复杂度就是 O(n log n)。
更严格一点，可以用期望分析来估算：随机基准下，一个元素被选为基准后，它所在的区间会被分成两半。通过数学归纳可以证明，总比较次数的期望约等于2n ln n，和 O(n log n) 一致。这也是为什么快排在数据量越大时，相对其他 O(n^2) 算法的优势越明显。
4.2 稳定性问题：快排为什么天生不稳定
排序算法的“稳定性”指的是：如果两个元素的值相同，它们在排序前后的相对顺序是否保持不变。快排的不稳定主要源于分区时的交换操作。比如两个值相同的元素，因为基准选择和交换顺序的影响，左右位置可能发生交换。
举个实际例子：假设有两条记录(3, "A")和(3, "B")，按第一个字段排序。期望结果是A在B前面，因为原始顺序如此。但快排的分区过程中，A和B可能被交换到不同的两侧，最终B跑到A前面。
如果你需要按多个字段排序，或者希望相同值的记录保持原始顺序，快排不是最好的选择。这时应该考虑归并排序。归并排序在合并阶段可以保证相同元素的相对顺序不变，所以它是稳定的。
4.3 与归并排序、堆排序的工程对比
把三种主流 O(n log n) 排序算法放在一起看，各自的优劣势很明显：
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 特点 |
|---|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n^2) | O(log n) | 不稳定 | 常数因子小，实测最快，但怕最坏情况 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 稳定且最坏有保证，但内存开销大 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 就地排序且最坏有保证，但常数因子大 |
在工程选型上，我总结的经验是：数据基本随机且内存紧张时优先考虑快速排序；需要稳定排序且内存充足时用归并排序；对最坏耗时要求极高且不能接受 O(n) 额外空间时，再考虑堆排序。
5. 工程实现与实测：从课堂代码到标准库级别的距离
5.1 一个工程级快排的完整落地
把前面提到的优化整合起来，可以给出一份相对“工程级”的代码。它同时包含三数取中、小区间插入排序、三路分区和尾递归优化。
#include <vector> #include <iostream> using namespace std; const int kInsertionThreshold = 16; void insertionSort(vector<int>& arr, int left, int right) { for (int i = left + 1; i <= right; ++i) { int key = arr[i]; int j = i - 1; while (j >= left && arr[j] > key) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; } } int medianOfThree(vector<int>& arr, int left, int right) { int mid = left + (right - left) / 2; if (arr[left] > arr[mid]) swap(arr[left], arr[mid]); if (arr[left] > arr[right]) swap(arr[left], arr[right]); if (arr[mid] > arr[right]) swap(arr[mid], arr[right]); return mid; } void quickSort(vector<int>& arr, int left, int right) { while (left < right) { if (right - left + 1 <= kInsertionThreshold) { insertionSort(arr, left, right); return; } int pivotIdx = medianOfThree(arr, left, right); int pivot = arr[pivotIdx]; int i = left; int lt = left; int gt = right; while (i <= gt) { if (arr[i] < pivot) { swap(arr[i], arr[lt]); ++i; ++lt; } else if (arr[i] > pivot) { swap(arr[i], arr[gt]); --gt; } else { ++i; } } if (lt - left < right - gt) { quickSort(arr, left, lt - 1); left = gt + 1; } else { quickSort(arr, gt + 1, right); right = lt - 1; } } }这里把基准值直接暂存为pivot，避免后续交换时基准值移动导致比较错乱。三路分区的边界条件是i <= gt，注意gt每次交换后要左移，不然后续比较会把已经处理完的元素再比较一轮。
5.2 和标准库排序的实测差距
我把这份代码和某主流标准库的排序实现放到同一份随机数据上跑，结果让人清醒。对 100 万个随机整数，我的实现大约耗时 1.2 秒，标准库的sort大约耗时 0.35 秒，相差约 3 到 4 倍。
差距主要来自几个方面：标准库实现通常比我这版用了更精细的阈值调优，比如不同的插入排序退化策略；标准库还可能在编译时做了一定的循环展开优化。不过我这里说的“差距”不代表我的代码没有价值，因为标准库往往采用内省排序的思路，它在检测到递归深度过深时会自动切换到堆排序，这本质上是一种“保底机制”。
5.3 快排适用的场景边界与选型建议
快速排序最适合的场景，用一句话说就是：数据量较大、内存空间有限、对稳定性没有硬性要求、且不太可能遇到极端有序输入。比如处理上百万条日志记录、做排行榜、对内层数组排序，这些都是快排的主场。
反过来，如果数据量很小，比如只有十来条，直接插入排序或者选择排序反而更快。如果数据存在大量重复键值，优先考虑三路快排或计数排序。如果对稳定性有硬要求，比如按多字段排序，那归并排序更合适。如果系统对最坏情况延迟极度敏感，那优先选堆排序或内省排序。
6. 我踩过的坑和最终建议
6.1 一个最容易忽略的边界错误
我在第一次实现快排时，犯过一个经典错误：分区函数里循环结束后忘记处理基准元素本身。有些分区写法要求把基准交换到中间位置，如果基准位置计算错误，结果就是无休止递归或错误排序。建议写完后一定用空数组、单元素数组、全相等数组、倒序数组这四类边界用例跑一遍。
另一个常见坑是递归没有定义终止条件。好的习惯是一开始就写上if (left >= right) return;，并且在使用下标时要警惕right - left + 1 <= 阈值这样的判断，防止下标错位。
6.2 关于快排的三点实战心得
第一，不要迷信“最快的算法”这个说法。快排的实际性能高度依赖数据特征，最优方案往往要通过实测来确定。我会在项目里预留一个排序基准测试脚本，每次换算法前先跑几组典型数据，再决定用哪套策略。
第二，最优实现不一定是最高级算法的堆砌。之前我贪心地把三路快排、并行化、尾递归优化全部叠加到一段代码里，结果在小数据量下性能反而更差。优化的前提是知道瓶颈在哪，比如递归过深、重复元素多、还是比较函数本身就是瓶颈。
第三，面试时讲解快排最好配合一个具体例子。我会在白板上写下[4, 6, 2, 9, 1]，一步步演示分区过程，同时解释为什么每次分区后基准元素的位置就是它的最终位置。这样能让听的人直接看到分治的逻辑，而不是只背一篇抄来的描述。
最后再多说一句：把快排的代码默写出来只是入门，能讲清楚它为什么在某些场景退化成 O(n^2)、怎么用三数取中和三路分区来规避、以及在工程上如何抉择稳定性和内存开销，才算是真正掌握。我建议你把我给出的工程版代码拷到本地，造几批特殊数据跑一跑，亲眼看一次从“能用”到“好用”的性能差距，比看再多文章都管用。
