排序这件事看起来简单可一旦数据量上来选错算法就是肉眼可见的卡顿。之前在某后台系统的数据清洗任务里我用最朴素的双层循环处理几万条记录跑一次要几十秒换成快速排序后直接降到毫秒级。从那以后不管面试还是实际开发快排都是我优先考虑的排序方案。这篇就从原理、基准选择、优化手段到工程落地把“数据结构与算法篇-快速排序”能讲的坑和技巧一次性说透。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(vectorint 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(vectorint 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]和右边的[gt1, right]。3.3 尾递归优化到底优化了什么快排的递归深度在最坏情况下可能达到 O(n)比如每次都选到最差基准时。递归过深有两个问题一是函数调用栈可能溢出二是函数调用本身有性能开销。尾递归优化的思路是把其中一侧的递归改成循环从而减少栈深度。典型写法是这样的void quickSortTailRecursive(vectorint 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(vectorint arr, int left, int right) { stackpairint, 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(vectorint 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(vectorint 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(vectorint 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)、怎么用三数取中和三路分区来规避、以及在工程上如何抉择稳定性和内存开销才算是真正掌握。我建议你把我给出的工程版代码拷到本地造几批特殊数据跑一跑亲眼看一次从“能用”到“好用”的性能差距比看再多文章都管用。