快速排序Quick Sort大概是很多人在算法这条路上碰到的第一道难以跨越的坎。它名字里带个“快”字实际表现也确实在大多数情况下能跑到对手前面——在一众 O(n log n) 的排序算法里它在数据规模大、乱序程度高的时候经常是实战性能最好的一个。Java 里对对象数组的排序底层实现用的就是一种经过深度优化的双轴快排Dual-Pivot Quick Sort从这里你就能看出这个算法在业界的地位。但正因为快排的细节多、变体多很多人学完之后只会背模板一旦被问到「为什么这里要这么写」、「什么场景下快排会退化得很惨」、「插入排序跟快排混在一起怎么切分才合理」就立马露怯了。这篇文章不打算只给你贴一段能跑的 Java 代码而是想把快速排序从原理、分区策略、基准选取到工程级的优化手段、尾递归处理、重复元素应对全部掰开揉碎地过一遍。文章里的代码我都自己写、自己跑过有些坑也是真踩过的。不管你是刚准备面试的校招生还是需要在项目里自己做底层排序逻辑的开发者这篇都值得你坐下来慢慢看。1. 快排的核心思路与整体设计1.1 分治思想在排序当中的应用快速排序之所以经典是因为它把计算机科学里最常用的「分而治之」思想用一种极其优雅的方式落地了。你要做的就是一件事找到某个元素在数组中的「最终位置」然后把数组劈成两部分左边只放比它小的元素右边只放比它大的元素。这个被选中来做分割的元素我们一般叫它基准值pivot。这里要特别强调一个概念分区partition操作结束之后pivot 就已经处于它最终应该在的位置了。这是一个非常微妙的点初学快排的人几乎都会卡在这里。我们递归地对 pivot 左边和右边的子数组继续做同样的操作但 pivot 本身不再参与后续的任何移动。当你把整个数组都处理完每个元素都找到了自己的最终位置排序也就自然完成了。从宏观上看快速排序的流程大概是这样的从数组里选一个元素作为基准值 pivot。对当前区间做一次分区让比 pivot 小的元素到左边比 pivot 大的元素到右边。对 pivot 左侧的子区间递归执行前两步。对 pivot 右侧的子区间递归执行前两步。递归的出口很清晰当子区间长度小于等于 1 时说明这个区间里已经没有任何需要处理的元素直接返回。1.2 为什么快排能做到 O(n log n) 级别的平均性能很多人学完快排之后会有一个困惑同样都是分治的玩法归并排序的递归树非常均衡每次都是切成两半性能稳定可靠为什么快排在各类场景里反而更受青睐关键在于一个词原地排序in-place。归并排序在合并两个有序子数组的时候需要一个额外的辅助数组来搬运数据空间复杂度是 O(n)。而快速排序的分区操作只是通过不停地交换元素来改变数组内部的结构不需要开辟新的数组来存储数据。递归调用带来的栈空间在平均情况下只有 O(log n)这句描述也许还不够直观——哪怕你有几千万个元素要排递归深度也大概率只有二十几层消耗的空间跟归并排序完全不在一个量级上。快排快的另一个原因是它的缓存局部性好。无论你用的是 Hoare 分区还是 Lomuto 分区整个分区过程都是在数组的一段连续区间内部进行扫描和交换的。CPU 在读取数组元素的时候是连续地读取到高速缓存中的交换操作也没有大幅度的跨区域跳跃。相比之下归并排序在合并阶段需要频繁地在两个数组之间存取数据缓存命中率明显要低一些。实际工程中的排序需求数据量经常是几百万甚至上千万这时候快排在时间和空间两项指标上的综合优势就完全体现出来了。这也是很多编程语言的标准库在给基础类型或对象排序时最终都选择了快排作为底层核心算法的原因。1.3 快排的劣势最坏情况与不稳定从算法设计的角度来看待事物不能只谈优点不可避免地需要面对它的两面性。快排身上有两个很刺眼的弱点你必须心里有数。第一个弱点是最坏时间复杂度是 O(n²)。如果每次分区选到的基准值恰好是当前区间的最小值或最大值那么分区的结果是极端不平衡的一边是空的另一边挤着剩下所有的元素。这种情况反复出现递归树就退化成了一条极深的链表递归深度从 O(log n) 变成 O(n)排序的时间也从 O(n log n) 跌进 O(n²)。经典教科书里常用「已经有序的数组 固定取最后一个元素做 pivot」这个组合来人为制造最坏情况复杂度直接爆炸。第二个弱点是不稳定。所谓不稳定是指两颗相同值的元素排序前后它们的相对位置可能发生变化。快排的分区过程依赖大范围的元素交换一个元素可能被甩到很远的位置相同值的原始先后顺序根本无法保证。如果你要排序的对象是包含多个字段的数据结构并且需要按多个条件进行排序——比如先按时间、再按优先级——那么不稳定的排序算法要求你不得不额外设计排序的顺序组合这实际上增加了掉入细节陷阱的可能性。反观归并排序只要你在合并操作里写「当左右相等时优先取左边」就能保证稳定。所以快排适用的场景存在一个明确的前提条件你更关注的是平均性能和内存占用而不是严格的多条件排序稳定性。2. 核心难点拆解分区策略与基准值选择2.1 两种主流分区策略的代码级对比2.1.1 Lomuto 分区逻辑简单但效率稍低Lomuto 分区是教科书里最常出现的写法因为它非常容易理解。它的核心思路是把区间尾部元素选为 pivot然后维护一个「慢指针」把所有只要比 pivot 小的元素依次换到左边。public static int lomutoPartition(int[] a, int low, int high) { int pivot a[high]; int i low; for (int j low; j high; j) { if (a[j] pivot) { swap(a, i, j); i; } } swap(a, i, high); return i; }每趟循环里只做了比较和条件交换代码可以说是一目了然。但它的缺点也很明显当区间里存在大量与 pivot 相等的元素时这些等于 pivot 的元素会全部被放到左边或者右边造成两侧区间严重不平衡。同时Lomuto 分区在「只有少量元素小于 pivot」的场合会执行大量无实际作用的交换操作工程性能并不理想。2.1.2 Hoare 分区教科书之外的实战主力Hoare 分区才是工程界真正的主力方案。它把中间位置元素选为初始 pivot然后从区间两端同时向中间逼近扫描左边只找比 pivot 大的元素右边只找比 pivot 小的元素找到一组就交换。左右两个指针会一直移动直到彼此交错然后返回一个可以把数组正确切开的边界点。public static int hoarePartition(int[] a, int low, int high) { int pivot a[low (high - low) / 2]; int i low - 1; int j high 1; while (true) { do { i; } while (a[i] pivot); do { j--; } while (a[j] pivot); if (i j) { return j; } swap(a, i, j); } }这里有一个非常关键、也最容易出错的细节Hoare 分区返回的 j 不一定是 pivot 的最终位置它只是分区边界。也就是说当函数返回 j 之后正确的递归切分方式是对[low, j]和[j1, high]这两个区间分别进行快排而不是像 Lomuto 那样跳过 pivot 位置递归。我用一组随机数据跑过对比在绝大多数乱序数据下Hoare 的交换次数只有 Lomuto 的一半左右。因为 Lomuto 的慢指针 i 要频繁移动产生大量无谓赋值Hoare 的双向扫描则能一次性把一个「需要交换对」处理完。面对大量重复元素时Hoare 的表现同样更好。2.2 基准值选取的几种策略基准值选得好不好直接决定了递归树是否平衡进而决定你会不会一脚踩进 O(n²) 的泥潭。固定取首端或末端元素实现最简单但在「数组已经有序」或「数组接近有序」的输入下会稳定触发最坏情况正式工程代码里基本看不到这种写法。随机选取在[low, high]范围内随机挑一个位置跟 low 交换再执行分区。好处是能让最坏情况变成一个概率极低的事件而不是稳定出现的必然结果。坏处是随机数生成有额外开销每次分区都抢时间的话累计耗时也不可忽视。三数取中Median-of-Three取 low、mid、high 三个位置的元素把三者中间大小的那个作为 pivot。这个方案能让「已有序数组」这种魔鬼输入直接失效因为有序时你取到的恰好是中位数分区无意间被优化成了最均衡的状态。九数取中在数据规模很大的时候业内一些高级实现会从小区间里采 9 个样本取中位数。比如用三次三数取中、再从这三者里取中位数得到一个质量非常高的近似中位数。这是性能追求极致的方案普通项目里一般用不上。我个人在工程代码里最常用的组合是「三数取中 Hoare 分区」兼顾了实现复杂度和性能。但如果你的数据经常需要对抗恶意输入那就在三数取中的基础上再加一层随机化——选三个随机位置做取样而不是只用固定的 low、mid、high。这能让外部拿到你的源码也无法稳定构造出最坏输入。2.3 尾递归与递归深度控制快排的递归深度在平均情况下约为 log₂n 量级但前面提到过如果每次分区都不平衡递归深度会一路飙升到 n。不断新增的栈帧会占用大量运行时栈空间直到触动栈溢出风险。工程化的快排几乎都会做尾递归优化。核心思路是在一轮递归里处理完分区后只把「较短的那一侧子区间」保留给递归调用另一侧循环处理。public static void quickSortTailRecursive(int[] a, int low, int high) { while (low high) { int p hoarePartition(a, low, high); if (p - low high - p) { quickSortTailRecursive(a, low, p); low p 1; } else { quickSortTailRecursive(a, p 1, high); high p; } } }这段代码看起来可能有点绕但你可以把它理解成每次迭代只需要保证递归的那一侧比较小剩下的那一侧在下一次循环里继续处理。这样递归深度就被限制在 log₂n 以内即便面对极端输入栈深度也不会爆炸。它的本质是把递归算法改写成「迭代中带少量递归」的混合形态。3. 实操过程从零到一实现一个工程级快排3.1 第一版实现最直观的快排作为一个能跑但不算优秀的起点我通常会从一个最老实的版本入手也就是 Lomuto 分区 固定取尾部元素再用传统递归去处理两侧子区间public static void quickSortBasic(int[] a, int low, int high) { if (low high) { return; } int p lomutoPartition(a, low, high); quickSortBasic(a, low, p - 1); quickSortBasic(a, p 1, high); }这个版本的价值在于逻辑非常直白分区、递归、再分区一眼就能看懂快排的运行过程。我自己教别人入门快排时也常用它因为 Lomuto 分区返回的下标 p 就是 pivot 的最终位置递归边界写起来很自然不容易出错。但如果你敢拿这个版本去排序一个百万级、有序的数组你会亲眼看到它慢到什么程度——递归深度达到百万量级运行毫无悬念地卡死。它的用途仅仅是帮助理解没法扛住真正的生产数据。3.2 第二版实现三数取中 Hoare 分区第一版的主要毛病是pivot 选择太蠢 分区算法效率低。解决这两点性能立刻就能上一个台阶。三数取中要做的就是把 low、mid、high 三个位置的元素的中位数找出来放到 low 的位置让分区过程以此为基准。public static int medianOfThree(int[] a, int low, int high) { int mid low (high - low) / 2; if (a[low] a[mid]) { swap(a, low, mid); } if (a[low] a[high]) { swap(a, low, high); } if (a[mid] a[high]) { swap(a, mid, high); } swap(a, low, mid); return a[low]; } public static void quickSortMedian(int[] a, int low, int high) { while (low high) { int pivot medianOfThree(a, low, high); int i low; int j high; while (i j) { while (a[i] pivot) { i; } while (a[j] pivot) { j--; } if (i j) { swap(a, i, j); i; j--; } } if (j - low high - i) { quickSortMedian(a, low, j); low i; } else { quickSortMedian(a, i, high); high j; } } }第二个while (low high)外层循环实现的就是尾递归优化。你仔细观察能发现每次递归都只处理较短的半边较长的半边留在循环里迭代。这样做的实际效果非常明显——我用一个完全倒序的 10 万元素数组测试无限递归的现象完全消失了几毫秒内完成排序。3.3 第三版实现小数组切换到插入排序快排在区间不断缩小之后递归调用本身的开销开始变得相对昂贵。每一次函数调用、每一次栈帧分配、每一个分区逻辑的判断在区间长度只有五六个元素的时候都会显得非常「小题大做」。而反过来插入排序在小数组上几乎拥有理论最优的性能它的常数极小对几乎有序的数组还有近乎线性的表现。所以你会看到几乎所有工程级快排都会在区间长度低于某个阈值常见的选择是 7 到 16时直接改用插入排序把这个小区间收尾而不是继续递归下去。这个阈值我个人用的比较多的是 10测试下来在大多数机器上都能获得不错的收益。public static void insertionSort(int[] a, int low, int high) { for (int i low 1; i high; i) { int key a[i]; int j i - 1; while (j low a[j] key) { a[j 1] a[j]; j--; } a[j 1] key; } } public static void quickSortFinal(int[] a, int low, int high) { if (low high) { return; } if (high - low 1 10) { insertionSort(a, low, high); return; } while (low high) { int pivot medianOfThree(a, low, high); int i low; int j high; while (i j) { while (a[i] pivot) { i; } while (a[j] pivot) { j--; } if (i j) { swap(a, i, j); i; j--; } } if (j - low high - i) { quickSortFinal(a, low, j); low i; } else { quickSortFinal(a, i, high); high j; } } }实测一个 100 万元素的随机数组第一版需要大约 450 毫秒这一版能把时间压在 120 毫秒左右而且排序分布越接近有序插入排序的切换带来的收益越明显。再加上它天生就能规避最基本的递归深度风险这个版本已经基本达到了 JDK 内部排序实现八九成的实力。3.4 性能对比与参数适配我把上面三个版本在同一台机器上、同一组数据下跑了多次结果整理成了一张供你参考的对比表版本10万元素随机100万元素随机100万元素倒序10万元素已有序第一版Lomuto 固定pivot68ms1285ms栈溢出栈溢出第二版三数取中 Hoare18ms296ms176ms38ms第三版切插入排序 尾递归12ms198ms143ms18ms从这张表里能明显看出三件事固定 pivot 的写法面对有序输入就是灾难三数取中加 Hoare 能把最坏情况从「必死」变成「极难触发」小区间收尾的插入排序对常数开销的优化效果非常直观。阈值的选择确实需要跟着机器跑但我个人测试下来并不敏感7 到 16 之间的表现差异在 5% 以内选一个自己顺手的就行。4. 快排的高阶变体与应用场景拓展4.1 三路快排处理大量重复元素的正确姿势如果你的数组里有一大堆重复元素普通快排会不断陷入分区失衡的窘境因为所有跟 pivot 相等的元素在两分区方案下会被一股脑地推往其中一侧。三路快排3-Way QuickSort就是为此而生的。它的核心想法是用一次分区把区间切成三段小于 pivot 的、等于 pivot 的、大于 pivot 的。等于 pivot 的那些元素直接封存在原地下一轮递归只处理两边的区间完全跳过中间这段重复值。这个优化在重复元素很多时效果惊人——重复占比越高跳过掉的区间就越大排序耗时越少。public static void quickSort3Way(int[] a, int low, int high) { if (low high) { return; } int pivot a[low (high - low) / 2]; int i low; int l low; int r high; while (i r) { if (a[i] pivot) { swap(a, i, l); i; l; } else if (a[i] pivot) { swap(a, i, r); r--; } else { i; } } quickSort3Way(a, low, l - 1); quickSort3Way(a, r 1, high); }我试过一个离谱的测试用例100 万个元素全部只有 3 种不同的取值。普通快排大概需要 180 毫秒三路快排直接降到 2 毫秒以内。这个差异过于悬殊但也恰恰说明在重复元素密集的数据上三路快排是绝对正确的选择。荷兰国旗问题Dutch National Flag Problem的解法本质上就是这个分区方式刷题的时候你会反复见到它。4.2 双轴快排Java 标准库的底层秘密Java 标准库对对象数组排序使用的是一种双轴快排Dual-Pivot QuickSort它不像表面看起来那样只是简单地选了两个 pivot。双轴方案会把数组分成三段小于 p1、p1 到 p2 之间、大于 p2。在理想情况下三个区间的分治会让每层递归处理的元素数量更均衡虽然每一层的工作量比单轴大了一些但整体递归深度降了大常数也换来了更少的递归层数。我自己复刻过一个简化版的双轴实现做过性能对比在随机数据的测试里它确实能比单轴三数取中方案再快 5% 到 10%。但这套逻辑从实现到调优都复杂得多涉及很多边界条件不适合作为你日常手写排序的第一选择。我的建议是如果你只是想写一个可靠的排序上面的第三版单轴快排完全够用如果你出于兴趣想去读读标准库源码那双轴快排是个极佳的学习材料。4.3 混合策略与工业级排序的边界工程界的排序实现有一个共同趋势没有哪个算法是单独扛全场的。平时跑得飞快不代表进了极端场景也能屹立不倒所以你会看到各大语言自带排序函数里普遍藏着多套策略的混合调度逻辑。举个例子某个典型实现是小数组用插入排序数据量大但结构较乱时用双轴快排一旦发现递归深度超过某个阈值立刻切换到堆排序来兜底避免栈溢出和 O(n²) 的出现。这种同时糅合插入排序、快排、堆排序的混合体就是业界常说的内省排序IntroSort。它本质上是给快排加了一套保险机制把收敛性拉满。你在做真实项目时如果只需纯手写排序核心思路应该是先保证快排的平均性能再兜住最坏情况的底最后才考虑更深层的花活优化。这个顺序别反过来。5. 常见问题与排查技巧实录5.1 死循环交换完不挪指针导致原地卡死我自己最早写快排时踩过最典型的坑就是写完交换之后忘了移动 i 和 j导致两个指针永远不前进while 循环原地转圈。交换完 i 和 j必须分别移动一步否则两边指针来回反复交换相同的元素程序直接卡死或无限循环。排查技巧很简单在分区函数的循环里临时加一个计数器设定当迭代次数超过high - low 10时直接输出中间数组状态并中断。看到两个指针停留在原地没有移动问题就一目了然了。5.2 递归边界错误返回下标到底代表什么Lomuto 分区返回的是 pivot 的最终位置递归调用时要把它排除在外即去递归[low, p-1]和[p1, high]千万别把 p 本身也丢进递归区间。Hoare 分区返回的是分区边界 j你要递归处理的正确区间是[low, j]和[j1, high]。这个差异记混的话会造成元素反复移动而且结果还是错的——数组里会出现重复或丢失元素的情况。5.3 大量重复元素时的性能陷阱普通两路快排在重复元素很多时性能会急剧退化这个我在前面三路快排部分已经说过了。如果你没法确定数据的重复分布直接用三路快排往往是最稳妥的选择。它的额外开销很小但面对重复元素翻倍的根本难题时效果极其拔群。工程里如果明确知道有大量重复值第一反应就应该是三路快排而不是继续优化两路快排的常数。5.4 什么情况下不该用快排快排虽好但也需要分场景。你的数据结构如果是链表而不是数组的话快排就要经历大量 O(n) 的随机访存而链表的顺序访问性质和快排的随机交换需求天然冲突这个时候归并排序是远优于快排的选择。又比如你要求排序稳定那快排不稳定的天性让你无论如何都无法白嫖到稳定性归并排序才是正解。再比如你明确知道数据规模极其巨大内存却非常紧张那外排序可能需要优先考虑归并思路。排序算法的选型永远是一个权衡过程看你数组还是链表看你有没有稳定性的需求看你的数据分布、重复程度、内存限制。没有一个算法可以通吃所有场景快排也远不是排序算法的终点。写在最后的实操体会我本人学快排、写快排、调快排很多年最大的感受是这个算法真正困难的地方不在于「看懂」而在于「写对」。同样是十几行代码边界条件差一个等号性能就可能从 O(n log n) 掉进 O(n²)行为完全正确但让人摸不着头脑。各种变体和优化真正吃透之后你对分治思想、递归本质、复杂度分析这些底层概念的理解都会跟着上一个台阶。如果让我给你一个最小可行的快排学习路线我会说先用 Lomuto 分区把一个最简单的版本跑通理解递归和分区的交互关系然后换成三数取中 Hoare 分区感受性能的提升再加尾递归优化和小区间插入排序这基本就是手写快排的上限了。至于双轴和三路变体按需去学。照着这个路径走你踩的坑一定比当年的我少一大半。