快速排序是每个程序员都绕不开的坎。原理简单三句话能讲完代码想写得又快又稳却要实打实踩过几年坑。大学教材里的朴素快排放到 LeetCode 这类 OJ 上一测就露馅几万个逆序数据卡出秒级耗时十万个重复元素直接栈溢出。我把这几年在快排优化上的折腾整理成了第 199 期算法笔记这期内容很干8 个经过实测验证的优化技巧从基准选取、分区策略到递归结构和工程微调全部拆开讲透。这篇不是理论堆砌每个技巧都给了能直接跑的代码、适用场景和我的实测感受。不管你是刷题准备面试还是想自己写一个工业级排序函数把这 8 个技巧组合起来效果能直逼主流标准库里的排序实现。如果你连最基础的 Lomuto 分区都没吃透建议先回去把朴素快排写顺如果你已经能轻松写出朴素快排但一遇到重复元素、逆序数据就头大这篇就是专门给你准备的。1. 动手前先想清楚快排优化到底在优化什么1.1 朴素快排的四个致命弱点先说痛点。课堂上的快排一般长这样每次取最后一个元素当基准用一个单向扫描分区Lomuto 分区把小于基准的往左挪大于等于的往右扔然后递归两侧。这个写法教学演示没问题一到真实数据就原形毕露。第一基准选择太僵硬。固定取第一个或最后一个元素遇到已经有序、逆序的数据分区必然严重不平衡每层只排掉一个元素复杂度直接退化成 O(n²)。十万个逆序数字朴素快排跑起来比朴素冒泡还难受因为递归栈还要跟着遭殃。第二递归深度失控。平衡分区时递归深度是 O(log n)一旦分区不平衡递归深度就能到 O(n)。程序调用栈大小是有限的几万个元素就能把栈压爆报出递归错误。对刷题党来说这个问题在 OJ 上比性能退化更致命因为直接 Run Error。第三大量重复元素会触发隐藏退化。Lomuto 分区在处理所有元素都相等的数组时每趟只会划走一个元素复杂度稳定趋向 O(n²)。我见过不少人在 LeetCode 排序题上 TLE数据并不是很大就是全重复数组在作祟。第四常数开销被无视。函数调用、边界判断、交换操作这些单看都不起眼但快排是分治算法规模越大层级越多这些开销累加起来能把理论优势吃干净。很多人对比快排和归并排序总觉得归并更慢实际工程里快排那点常数优势就是这么被挥霍掉的。1.2 优化落点的三个层次把问题想清楚优化方向就出来了。我习惯把快排优化分成三个层次后面 8 个技巧分别落在不同层上。第一个层次是降低比较次数。核心是让基准逼近中位数让每次分区尽量均衡并且针对重复元素做特殊处理避免无意义的比较和交换。第二个层次是控制递归结构和内存占用。包括递归深度上限、尾递归改循环、显式栈替代系统调用栈这些解决的是算法不会爆栈和空间可控的问题。第三个层次是压缩常数因子。比如小区间切换到插入排序、减少内循环边界判断、利用缓存局部性、避免无谓的函数调用。这些优化不会改变复杂度量级但能把常数系数压到很低工程价值和刷题价值都很大。三个层次可以按序推进也可以按场景组合。下表是我给这 8 个技巧做的落点定位先有个整体框架后面逐个展开。优化层次对应技巧核心解决什么降比较次数三数取中、随机化基准、Hoare 双向扫描、三路快排避免最坏分区压制 O(n²) 退化控递归结构小半区优先、尾递归消除、显式栈迭代根治栈溢出空间稳定在 O(log n)压常数因子插入排序兜底、内省排序保险、九数取中、内循环微优化减少函数调用、边界判断和无效交换2. 技巧一至四从基准和分区入手把 O(n²) 扼杀在摇篮里2.1 技巧一三数取中加随机化基准先让最坏情况不出现最容易做也最见效的一个优化。朴素快排取最后一个元素当基准数据有序或逆序时必死。三数取中的思路是从区间的左端、中间、右端三个位置取元素把这三个数排序把中间值当作基准。这样无论输入是有序、逆序还是部分有序基准都不会是当前区间的极值分区质量立刻上一个台阶。def median_of_three(arr, lo, hi): mid (lo hi) 1 if arr[mid] arr[lo]: arr[mid], arr[lo] arr[lo], arr[mid] if arr[hi] arr[lo]: arr[hi], arr[lo] arr[lo], arr[hi] if arr[hi] arr[mid]: arr[hi], arr[mid] arr[mid], arr[hi] # 此时 arr[lo] arr[mid] arr[hi] arr[mid], arr[hi] arr[hi], arr[mid] return arr[hi]这段代码做了三组比较和交换代价极小换来的是分区均衡性的巨大提升。如果配合随机化效果更好在分区前随机挑一个位置当 mid 参与三数取中。随机化的意义在于恶意构造的输入无法预知你会选哪个基准刻意构造最坏情况的攻击路径就被堵死了。OJ 不针对你个人但生产环境里恶意输入是真实存在的随机化是一种廉价的防御。这里有个细节很多人会忽略三数取中之后我特意把基准换到了 hi 位置。这是因为后面用 Lomuto 或三路分区时基准放在区间端点最方便扫描。你也可以把基准放在 lo 端逻辑一样但代码要相应调整别混着用。2.2 技巧二用 Hoare 双向扫描替换 Lomuto交换次数锐减Lomuto 分区的内循环是单向的从左到右遍历凡小于基准就往前挪。这写法直观但交换次数偏多而且面对重复元素特别吃亏。Hoare 分区是快排最初的分区方式两个指针从两端向中间扫描左边找到小于基准的、右边找到大于基准的然后成对交换。同样的数据规模Hoare 的交换次数通常只有 Lomuto 的一半左右。def hoare_partition(arr, lo, hi): pivot arr[(lo hi) 1] i, j lo - 1, hi 1 while True: i 1 while arr[i] pivot: i 1 j - 1 while arr[j] pivot: j - 1 if i j: return j arr[i], arr[j] arr[j], arr[i]注意Hoare 分区返回的 j 不是基准的最终位置这是和 Lomuto 最大的区别。分区结束后左边区间是 [lo, j]右边区间是 [j1, hi]递归时边界千万别搞错。我见过无数人在这一步写出无限递归左区间写成 [lo, j-1]右区间写成 [j, hi]或者反过来一跑就死循环。从内循环角度讲Hoare 还有一个隐藏优势pivot 值本身会拦住扫描。因为基准位置在区间中部i 扫描到基准所在位置时arr[i] pivot 不成立i 自动停下j 同理。所以这两个内层 while 循环不需要额外写越界判断这为后面的技巧八埋了个好伏笔。对比项Lomuto 分区Hoare 分区扫描方向单向从左到右左右指针相向交换次数偏多约等于逆序对数较少更贴近实际需要的移动次数重复元素处理全等数组退化成 O(n²)全等数组仍能近似二分返回值含义基准最终下标分割点 j左区间含 j递归边界风险低高必须写对 [lo, j] 和 [j1, hi]2.3 技巧三三路快排重复元素的终结者前面提到 Lomuto 分区遇到全等数组会退化。根因是它把所有小于等于基准的元素都堆到一侧重复元素越多左右两侧越不平衡。三路快排解决这个问题最彻底一趟分区把数组切成三块小于基准的、等于基准的、大于基准的等于基准的一大块直接不再参与递归。def three_way_partition(arr, lo, hi, pivot_idx): pivot arr[pivot_idx] arr[pivot_idx], arr[lo] arr[lo], arr[pivot_idx] lt, i, gt lo, lo 1, hi while i gt: if arr[i] pivot: arr[i], arr[lt] arr[lt], arr[i] i 1 lt 1 elif arr[i] pivot: arr[i], arr[gt] arr[gt], arr[i] gt - 1 else: i 1 return lt, gt # [lt, gt] 这一段全部等于 pivot三个指针 lt、i、gt 的语义要记死lt 左边是小于区gt 右边是大于区i 是当前扫描位置。遇到小于基准的和 lt 交换i 前进lt 前进遇到大于基准的和 gt 交换gt 后退但 i 不前进因为换过来的元素还没看过等于基准的i 直接前进。递归时只处理 [lo, lt-1] 和 [gt1, hi] 两块。这套逻辑写起来不难但指针不前进的条件特别容易写错。刷题时有个土办法验证构造一个全等数组跑一遍如果能在接近线性的时间内完成基本就对了。三路快排对随机无重复数据也几乎不损失性能所以它是工程实现里非常受宠的底层方案。2.4 技巧四递归策略重构根治栈溢出分区质量再高也防不住某些极端输入把递归深度拉满。我的习惯是快排代码里永远不裸递归两半而是只递归小区间大区间用循环继续处理。这样无论分区多不平衡递归深度也被限制在 O(log n)因为每次递归下去的都是更短的那一半。def quicksort(arr, lo, hi): while lo hi: p partition(arr, lo, hi) # 任意分区实现 if p - lo hi - p: quicksort(arr, lo, p - 1) lo p 1 else: quicksort(arr, p 1, hi) hi p - 1如果连 log n 深度的递归调用都不想要就彻底去掉递归用显式栈模拟def quicksort_iterative(arr, lo, hi): stack [] while True: while lo hi: p partition(arr, lo, hi) if p - lo hi - p: stack.append((p 1, hi)) hi p - 1 else: stack.append((lo, p - 1)) lo p 1 if not stack: return lo, hi stack.pop()显式栈版本的逻辑是把较大的区间压栈暂存先把较小的区间处理完。这样栈里面存的全是比较大的区间而它们每一层都在缩小栈深度自然被压住。在 Python 里尤其推荐这个版本因为 Python 默认递归深度也就一千层真刷到十万级数据sys.setrecursionlimit只是延迟爆炸不如直接上显式栈来得干净。3. 技巧五至八面向工程实战的深度优化3.1 技巧五小区间插入排序外加一键收尾大招快排递归到子区间很小的时候分治优势已经没了剩下的全是函数调用和分区开销。这时候插入排序反而更快因为它常数极小对近似的序列几乎就是线性扫描。业界通用的做法是设一个阈值区间长度小于等于阈值就直接返回不再继续细分区。常见阈值在 8 到 32 之间我用 16。太小没效果太大会让插入排序背负重活。关键是一键收尾这个技巧不是在每个小区间立刻调用插入排序而是让快排递归到区间小于阈值就整体暂停最后对整个数组跑一遍插入排序。THRESHOLD 16 def quicksort(arr, lo, hi): if hi - lo THRESHOLD: return p partition(arr, lo, hi) quicksort(arr, lo, p - 1) quicksort(arr, p 1, hi) def insertion_sort(arr, lo, hi): for i in range(lo 1, hi 1): key arr[i] j i - 1 while j lo and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key def sort(arr): quicksort(arr, 0, len(arr) - 1) insertion_sort(arr, 0, len(arr) - 1)为什么能这样收尾快排分治到每个区间不超过 16 个元素时整个数组已经接近有序任意一个元素离它的最终位置最多不超过 16 个索引。这一遍全局插入排序的代价是 O(16n)等于 O(n)比在每个叶子区间反复调用插入排序少了大量函数调用和边界判断。这个技巧我第一次在工程代码里看到时挺震撼后来自己实测确实是能省一截时间的。3.2 技巧六内省排序给快排上一道保险就算三数取中、三路分区全上理论最坏情况依然存在。C 标准库的std::sort之所以能承诺稳定 O(n log n)靠的就是内省排序快排为主但实时监控递归深度一旦深度超过上限就把当前区间切换成堆排序兜底。堆排序最坏也是 O(n log n)而且原地排序不需要额外空间是最理想的保险丝。def introsort(arr, lo, hi, depth): if hi - lo THRESHOLD: return if depth 0: heapsort(arr, lo, hi) return p partition(arr, lo, hi) introsort(arr, lo, p - 1, depth - 1) introsort(arr, p 1, hi, depth - 1) def sort(arr): n len(arr) depth_limit 2 * n.bit_length() introsort(arr, 0, n - 1, depth_limit) insertion_sort(arr, 0, n - 1)深度上限取2 * n.bit_length()。对长度为 n 的数组平衡快排深度上限是 log2(n)取两倍作为警戒线是给不平衡分区留了余量又不会让堆排序兜底来得太迟。堆排序只需要实现一个标准最大堆代码不短但在整个排序链路里只是个备用角色思路是深度告警立刻切入。3.3 技巧七九数取中把基准质量再提一个档次三数取中适合中小区间和一般数据但三个采样点可能恰好聚在数据的某个低值区间选出来的基准仍然偏离真实中位数。九数取中采样点更多更接近真实中位数。它在数组里均匀取 9 个位置分成三组每组取中位数三个中位数再取一次中位数这就是经典的 Tukeys ninther 思路。def median3(arr, a, b, c): if arr[b] arr[a]: arr[a], arr[b] arr[b], arr[a] if arr[c] arr[a]: arr[a], arr[c] arr[c], arr[a] if arr[c] arr[b]: arr[b], arr[c] arr[c], arr[b] return b def ninther_pivot(arr, lo, hi): if hi - lo 40: return median3(arr, lo, (lo hi) 1, hi) step (hi - lo) // 8 a median3(arr, lo, lo step, lo (step 1)) b median3(arr, lo (step * 3), lo (step 2), lo (step * 5)) c median3(arr, lo (step * 6), lo (step * 7), hi) return median3(arr, a, b, c)九数取中多花了十几次比较但对大数组来说一个更接近真实中位数的基准能显著减少后续分区的不均衡总比较次数反而下降。要注意的是区间本身小于 40 个元素时九点采样铺不开直接用三数取中就行。这个技巧在 JDK 对基本类型排序的实现里也有类似思想。3.4 技巧八内循环微优化把常数压到最狠前面几个技巧改变的是算法骨架技巧八处理的都是细节但细节叠加起来非常可观。第一基准先挪到端点。不管用什么分区先把基准交换到 lo 或 hi 端让扫描过程不用反复判断当前位置是不是基准。这个操作只付出一次交换却让内循环干净很多。第二利用 Hoare 分区的哨兵特性。前面技巧二提到的双指针扫描pivot 自己就会挡住两边指针越界内层 while 循环不必写 i hi、j lo。不要小看这两条判断分区内循环每趟都要执行去掉之后内层代码少了一半开销。第三减少交换操作。交换一次要动三个变量能只用赋值就用赋值能少动一次数组引用就少动一次。在低层语言里还可以把分区函数标记为内联避免函数调用。Python 里则可以把数组绑定到局部变量减少逐层名字查找。第四缓存友好。递归优先处理更小的一半本质是为了让当前处理的数据尽量聚在更小的内存范围内命中缓存的概率更高。另外排序对象尽量用连续内存的数组少用指针链式的结构这在处理上百万条数据时差距会被放大到肉眼可见。第五对近乎有序数据做快速通道。如果你知道自己要处理的数据经常是基本有序的可以在排序前先扫一遍发现绝对有序就直接返回。插入排序天然利用有序性这也是技巧五那么有效的底层原因。4. 完整优化版实现可直接抄作业的组合方案4.1 各技巧怎么组合参数怎么定8 个技巧不是都要一起上组合策略看场景。我给出一套我自己刷题和写工程代码都在用的组合九数取中负责基准质量三路分区负责重复元素小区间暂停负责压递归开销内省深度负责兜底最坏情况最后全局插入排序收尾。这套组合基本覆盖了我能想到的所有输入形态。阈值参数我固定用 16深度上限用2 * n.bit_length()。这两个参数没必要过度调优跑过几次测试就能确定16 是一个非常稳的甜点深度上限留两倍余量足够防护大部分异常递归。4.2 完整代码一份下面这份代码把技巧五、六、七都嵌进去了复制就能跑配合任意一套能跑的 heapsort 即可。def median3(arr, a, b, c): if arr[b] arr[a]: arr[a], arr[b] arr[b], arr[a] if arr[c] arr[a]: arr[a], arr[c] arr[c], arr[a] if arr[c] arr[b]: arr[b], arr[c] arr[c], arr[b] return b def ninther_pivot(arr, lo, hi): if hi - lo 40: return median3(arr, lo, (lo hi) 1, hi) step (hi - lo) // 8 a median3(arr, lo, lo step, lo (step 1)) b median3(arr, lo (step * 3), lo (step 2), lo (step * 5)) c median3(arr, lo (step * 6), lo (step * 7), hi) return median3(arr, a, b, c) def three_way_partition(arr, lo, hi, pivot_idx): pivot arr[pivot_idx] arr[pivot_idx], arr[lo] arr[lo], arr[pivot_idx] lt, i, gt lo, lo 1, hi while i gt: if arr[i] pivot: arr[i], arr[lt] arr[lt], arr[i] i 1 lt 1 elif arr[i] pivot: arr[i], arr[gt] arr[gt], arr[i] gt - 1 else: i 1 return lt, gt def heapsort(arr, lo, hi): def sift_down(root, size): while root * 2 1 size: child root * 2 1 if child 1 size and arr[lo child 1] arr[lo child]: child 1 if arr[lo child] arr[lo root]: arr[lo root], arr[lo child] arr[lo child], arr[lo root] root child else: break n hi - lo 1 for i in range((n - 2) // 2, -1, -1): sift_down(i, n) for end in range(n - 1, 0, -1): arr[lo], arr[lo end] arr[lo end], arr[lo] sift_down(0, end) THRESHOLD 16 def introsort(arr, lo, hi, depth): if hi - lo THRESHOLD: return if depth 0: heapsort(arr, lo, hi) return p ninther_pivot(arr, lo, hi) lt, gt three_way_partition(arr, lo, hi, p) introsort(arr, lo, lt - 1, depth - 1) introsort(arr, gt 1, hi, depth - 1) def insertion_sort(arr, lo, hi): for i in range(lo 1, hi 1): key arr[i] j i - 1 while j lo and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key def quick_sort(arr): n len(arr) if n 1: return arr introsort(arr, 0, n - 1, 2 * n.bit_length()) insertion_sort(arr, 0, n - 1) return arr我特别想提醒一句这份代码里的median3会直接改数组里三个位置的相对顺序这在原地排序中是允许的但如果你要拿它去复刻某些严格的算法演示要注意这个副作用对排序正确性没有影响因为后面三路分区会把所有元素重新扫一遍。另外heapsort 只负责兜底几乎不会触发但写出来就要保证它能独立正确排序别让它变成最后一个隐藏炸弹。4.3 效能观察和使用建议我自己本地测过用 Python 对十万随机整数排序朴素 Lomuto 快排大约要零点几秒上面这版组合优化大约能快三到五成。对十万个全重复元素朴素版直接跑到怀疑人生这版几乎是线性速度。当然具体数字受语言、机器、数据分布影响很大我这里只说趋势不标榜精确基准。技术选型上我的建议是分场景刷题阶段技巧一加技巧二加技巧四就足够应付绝大多数排序题面对明显有大量重复数据的题立刻补上技巧三准备生产级代码再上齐技巧五到八。没必要一上来就把 8 个全堆上先理解每个技巧到底在解决什么问题组合才不会是四不像。5. 踩坑实录与排查技巧5.1 常见问题速查表症状根因解决思路逆序数组栈溢出固定基准导致最坏分区三数取中/随机基准 小半区优先递归全重复数组 TLELomuto 分区重复元素堆单侧三路快排Hoare 分区无限递归区间边界写错左右区间重叠左区间写 [lo, j]右区间写 [j1, hi]插入排序收尾反而变慢THRESHOLD 设太大调回 8 到 24 之间我常用 16introsort 兜底没触发深度上限给得太大用 2 倍 bit_length别拍脑袋取 1024小数据排序性能倒挂优化层数太多光初始化就在浪费数组长度小于几百时直接用插入排序最简单5.2 我在 OJ 和本地环境踩过的几个坑分区边界是最容易翻车的点。我调试 Hoare 分区时发生过一次诡异死循环排查了很久才发现是递归时把右区间起点写成了 j 而不是 j1。两个区间接缝处重叠了一个元素导致某个元素永远在两个区间之间来回倒手。从那以后我给自己立了个规矩每写完一个分区版本先用随机小数组跑一轮然后用断言检查排序结果跑满几十组再上大数据。第二个坑是盲目迷信三路快排。有一阵子我只要写快排就无脑三路结果处理随机无重复的大数组反而比普通 Hoare 慢了一些。不是三路错是数据形态不匹配。三路快排最擅长重复元素多的场景对纯随机数据反而多了一些无意义的比较。优化永远跟着数据走不是跟着潮流走。第三个坑是递归深度延误处理。在 Python 里我一开始遇到递归错误就加sys.setrecursionlimit加到一百万后确实不报错了但程序变得非常慢后来才反应过来深递归本身就是在慢性消耗资源治本的办法是把递归改成显式栈版本。提不提高递归上限只是个止血贴真正要做的是让递归深度根本不涨上去。5.3 这些年折腾快排的一点心得技巧学了几年代码改了一版又一版我最大的体会是快排优化不是技巧堆砌而是对数据形态的理解。面试官问你快排最坏情况怎么避免你要能说出三数取中和随机化的区别线上系统排序突然卡顿你要能判断是重复元素太多还是递归过深。这些判断力比背代码有价值得多。顺手分享一个我一直保留的验证习惯排序算法写完别急着上大数据先用三种小数组测一遍。第一种是随机数组验证基本正确性第二种是有序数组验证会不会退化第三种是全等数组验证重复元素下的表现。三组过了再拿十万级数据上压力测试。这套流程花不了两分钟却能拦住绝大部分低级错误。快排不难写难的是每次写出来都是那个又快又稳的版本。