快速排序详解：分治思想、优化技巧与高频面试题实战

1. 为什么集训第08天非快速排序莫属说实话如果让我从基础算法里挑一个最像魔术的排序我会选快速排序。它代码短得出奇思想却深到能写一本书它平均性能是O(n log n)可一个不小心就能退化到O(n²)让你在面试官面前原地社死它被无数教科书当作分治思想的典范但真正能把分区操作讲明白、把边界条件写对的人我面试过的候选人里恐怕不到三成。这次基础算法集训走到第08天前面已经依次过掉了选择排序、插入排序、冒泡排序、归并排序这些基础款。到快速排序这天集训群里明显活跃了不少。原因很简单这几乎是所有排序算法里看起来最简单、写起来最容易错的一个。你随便搜快速排序代码网上能翻出几十种写法Lomuto分区、Hoare分区、三路快排、随机主元……版本之间各有各的坑。今天这篇集训笔记我就把快速排序从思想到实现、从复杂度到优化、从笔试题到工程应用一次性讲透。如果你正在准备算法笔试或者刚开始刷LeetCode必刷基础算法题这篇文章可以直接当你的复习提纲。我会尽量用最直白的话解释清楚它为什么快、怎么写才对、遇到退化怎么救。2. 分治思想一句话概括快排的野蛮与优雅2.1 快排的核心动作不是排序而是分区很多人学快速排序时第一反应是去看那几行递归代码然后背下来。这其实是最低效的学习方式。快速排序真正的灵魂是四个字分区Partition。排序只是分区之后水到渠成的结果。拿一个生活场景类比假设你要把一堆参差不齐的积木按从矮到高摆好。归并排序的做法是先把积木两两分组排好再不断合并而快速排序的做法是——随便抽一根积木当标杆主元pivot然后让所有比标杆矮的站到左边比标杆高的站到右边。注意此时左右两边内部还是乱的但整个序列已经呈现出左边 标杆 右边的格局。这个动作完成之后标杆的最终位置就确定了——它不会再移动了。接下来要做的就是对左半边和右半边分别重复同样的过程。随着递归一层层展开每一轮都至少有一个元素被放到它最终该待的位置。当所有子区间都只剩一个元素时排序自然完成。这就是分治Divide and Conquer的精髓不是先解决小问题再合并而是先排定一个元素把大问题拆成两个彼此独立的小问题。因为两个子问题互不影响所以递归之后不需要额外的合并步骤这是它和归并排序最本质的区别。2.2 为什么快期望复杂度从何而来如果每次分区都能把序列对半切开那么整个递归树的高度是O(log n)每一层所有分区加起来处理的元素总数是O(n)总复杂度自然是O(n log n)。这个推导和归并排序的递归式一模一样T(n) 2T(n/2) O(n)但快速排序的特殊之处在于分区操作的质量完全取决于主元选得好不好。如果你每次都能选中位数递归树就是平衡的如果每次恰好选到最小或最大元素那左半边或右半边就有一个为空递归树退化成一条链每一层只能确定一个元素的位置总复杂度退化为O(n²)。这一点放在第4章详细讲这里先记住结论快排的快是有条件的条件是主元选得好。2.3 原地排序快排最珍贵的工程属性很多人忽略了一个关键点快速排序是**原地排序in-place**的额外空间开销只有递归调用栈的O(log n)而归并排序通常需要O(n)的辅助数组。这个差异在内存敏感的老嵌入式系统、或者对大数据量做排序时非常重要。原地是怎么做到的靠的是分区函数里那一次次交换。整个过程不申请新数组只是在一个数组内部把元素搬来搬去。这也意味着实现快速排序的核心挑战就是写好这个搬来搬去的分区逻辑。3. 两种经典分区实现Lomuto与Hoare到底差在哪3.1 Lomuto分区最好理解也最容易写错Lomuto分区的思路非常直白。它的做法是选定最后一个元素作为主元也可以选其他的看实现维护一个指针 i表示小于主元的区间的末尾从左到右扫描数组每当发现当前元素小于主元就把 i 往前移一格然后交换 a[i] 和 a[j]扫描结束后把主元换到 i1 的位置。看代码public int lomutoPartition(int[] a, int low, int high) { int pivot a[high]; // 选最后一个元素作主元 int i low - 1; // 小于主元的区间右边界 for (int j low; j high; j) { if (a[j] pivot) { i; swap(a, i, j); } } swap(a, i 1, high); // 主元归位 return i 1; // 返回主元最终下标 } public void quickSort(int[] a, int low, int high) { if (low high) { int p lomutoPartition(a, low, high); quickSort(a, low, p - 1); quickSort(a, p 1, high); } }很多人在这个代码上犯的经典错误包括循环里写if (a[j] pivot)小于还是小于等于后面详细说、递归边界写low high、分区返回的位置忘了减一。我见过最多的bug是最后那个swap(a, i 1, high)写成swap(a, i, high)导致主元根本没有放到正确位置排序结果全乱。Lomuto分区的特点是代码紧凑、思路直观但它有一个明显的性能短板当数组里大量元素等于主元时它会做很多无谓的交换。而且Lomuto分区对近似有序的数组表现得非常差如果主元总是选到极端值退化成O(n²)的概率很高。3.2 Hoare分区更快但边界条件更烧脑Hoare分区是快速排序发明者霍尔C. A. R. Hoare的原版写法。它的思路是双向扫描选任意一个值作主元通常是区间内某个值比如中点位置的元素值左指针 i 从左往右找第一个不小于主元的元素右指针 j 从右往左找第一个不大于主元的元素如果 i j 就停止否则交换 i 和 j 位置的元素继续扫描。代码public 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分区的返回值和Lomuto有个关键区别返回的 j 并不保证是主元最终的位置它只是把数组分成了[low, j]和[j1, high]两段这两段之间满足左边所有元素都不大于右边所有元素。因此递归调用时要写public void quickSortHoare(int[] a, int low, int high) { if (low high) { int p hoarePartition(a, low, high); quickSortHoare(a, low, p); quickSortHoare(a, p 1, high); } }注意边界左边是low到p不是p - 1。这里写错的人非常多原因就在于Hoare分区不返回主元的最终位置而是返回一个分割点。我的经验是第一次写Hoare分区的人十个里面有八个会在quickSortHoare(a, low, p)和quickSortHoare(a, low, p - 1)之间犹豫然后写错。3.3 两者的性能差异实测不是一点半点从交换次数来看Hoare分区通常比Lomuto做更少的交换因为它每次交换都把一对错位的元素一次性归位而Lomuto是逐个挪动。在元素重复较多的数组上Hoare的常数优势更明显。Java标准库里的Arrays.sort()对基本类型数组使用的DualPivotQuickSort思路也和Hoare同源。但如果从竞赛稳妥性角度选我更推荐新手先把Lomuto写对、写熟。原因是它边界逻辑简单不容易在高压面试场上犯错。先把简单版本跑通再去挑战Hoare循序渐进不丢人。4. 从O(n²)到O(n log n)主元选择与退化危机4.1 经典的必死案例对有序数组排序快速排序最尴尬的场景是什么恰恰是对一个已经排好序的数组排序。如果你每次都用第一个元素或最后一个元素当主元数组已经有序时每次分区都会得到一个空区间和一个 n-1 长度的区间递归深度变成 n总比较次数变成 n (n-1) (n-2) ... 1 O(n²)。这个场景不是理论模型而是日常开发里极常见的输入。比如数据库给出一份已经按时间排序的记录业务层又调用了一遍排序接口比如你测试时用了一个本来就有序的数组。如果主元策略不讲究程序就会毫无征兆地慢一个数量级。4.2 随机化主元用概率消灭最坏情况最经典的解决方案是随机化。每次分区前从[low, high]中随机选一个位置和区间首元素或尾元素交换再执行原来的分区逻辑。Random rand new Random(); int pivotIndex low rand.nextInt(high - low 1); swap(a, pivotIndex, high); // 换到Lomuto分区期望的位置这样做之后最坏情况理论上仍然存在但概率低到可以忽略。任何固定输入都无法稳定地触发最坏情况因为主元位置是运行时随机决定的。简单来说随机化不是消除最坏情况而是让对手或命运无法精准命中你的最坏情况。4.3 三数取中工程上更常用的伪随机随机化需要依赖随机数发生器在部分嵌入式环境里并不方便。工程上更常见的折中方案是三数取中median-of-three取区间的首元素、中间元素、尾元素把三个值中位数当作主元。int mid low (high - low) / 2; if (a[mid] a[low]) swap(a, mid, low); if (a[high] a[low]) swap(a, high, low); if (a[high] a[mid]) swap(a, high, mid); // 此时 a[mid] 是三者的中位数 swap(a, mid, high); // 放到Lomuto分区期望的位置三数取中对近似有序数组非常有效因为有序数组的首、中、尾三个值中位数恰好落在中间每次分区都能接近对半切分。这个策略在工程排序中几乎是标配很多标准库的实现都包含这个步骤。4.4 递归深度与栈溢出一个容易被忽略的隐患快速排序递归调用栈的深度在理想情况下是O(log n)但在退化情况下能达到O(n)。如果数组长度是十万、百万级别且主元选择策略不佳递归深度可能是十万以上直接触发StackOverflowError。Java虚拟机的默认栈空间通常只有几百KB到几MB深度超过几千到一万就可能撑不住。解决办法有两个随机化/三数取中从源头上保证递归深度期望为O(log n)使用尾递归优化只对短的那一半递归调用长的那一半用循环继续处理把递归深度牢牢限制在O(log n)以内。很多教科书不提尾递归优化但笔试面试中问如何把快排的最坏栈深度控制在O(log n)时答案就是这个技巧。代码大致长这样public void quickSortTail(int[] a, int low, int high) { while (low high) { int p lomutoPartition(a, low, high); if (p - low high - p) { quickSortTail(a, low, p - 1); // 先递归短的左半 low p 1; // 循环处理长的右半 } else { quickSortTail(a, p 1, high); // 先递归短的右半 high p - 1; // 循环处理长的左半 } } }这个写法精妙之处在于每次递归处理的是较短的子区间那么剩余待处理的长度至少减半因此递归深度不会超过 O(log n)。这是我个人在写底层排序组件时非常喜欢用的手段。5. 快排的工程优化从教科书代码到工业级实现5.1 小数组切换到插入排序教科书上的快速排序递归到区间长度为1或0就停止。但工程实现里几乎都会设置一个阈值当区间长度小于某个值常见是10到20时改用插入排序。原因很简单递归是有开销的函数调用、参数压栈、循环分支这些常数成本在小数组上往往超过插入排序那点O(k²)的代价。而且插入排序对接近有序的数组非常友好正好适合承接分区后的小块残局。我自己实测过阈值设在16左右整体排序耗时能减少10%到20%。不同语言、不同数据规模下最优阈值略有区别但10到20这个区间基本不会出错。5.2 三路快排处理大量重复元素的利器如果数组里有大量相等的元素比如一亿个取值范围在[0,100]的整数普通快排会怎么做所有等于主元的元素会被分到某一侧然后反复参与比较白白浪费大量O(n log n)的运算。三路快排3-Way QuickSort把分区结果变成三段小于主元、等于主元、大于主元。等于主元的区间直接在这一次分区中全部归位不再参与后续递归。对于重复元素多的数据三路快排的时间复杂度可以从O(n log n)降到接近O(n)。public void quickSort3Way(int[] a, int low, int high) { if (high low) return; int lt low, i low 1, gt high; int pivot a[low]; while (i gt) { if (a[i] pivot) { swap(a, lt, i); } else if (a[i] pivot) { swap(a, i, gt--); } else { i; } } quickSort3Way(a, low, lt - 1); quickSort3Way(a, gt 1, high); }这段代码里lt指向等于区间的左边界gt指向等于区间的右边界。扫描中不断把小于主元的元素扔到左边、大于主元的元素扔到右边等于的就直接跳过。等扫描结束[lt, gt]这段全部等于主元安稳躺在最终位置。5.3 双轴快排Java标准库的选择Java的Arrays.sort(int[])在JDK 7之后使用的就是Dual-Pivot QuickSort。它一次选两个主元把区间分成三段小于pivot1、pivot1和pivot2之间、大于pivot2。双轴快排的好处是每个分区步骤的信息利用更充分常数因子更低。虽然复杂度依然是O(n log n)但实测速度比经典单轴快排快不少。有兴趣的读者可以去翻OpenJDK源码里DualPivotQuicksort.java的实现里面还有针对小数组的插入排序切换、针对byte/short的计数排序特判堪称工程排序的集大成教科书。5.4 对比Java的Arrays.sort与Collections.sort这里补充一个高频面试点。Arrays.sort(int[])用的是双轴快排而Arrays.sort(Object[])和Collections.sort()用的是TimSort——也就是归并排序的优化版本。为什么要这样区分因为对象排序必须保证稳定性相等元素的相对位置不变而基本类型排序不需要稳定。快排不是稳定排序所以不能用于对象数组TimSort在最好情况下O(n)、最坏情况下O(n log n)且稳定是引用类型排序的理想选择。6. 笔试题中的快排从裸写代码到进阶变形6.1 闭着眼睛都要会的裸写快排无论你用什么语言至少在纸上完成一次无报错的快速排序是基本功。下面给一个我推荐的Java模板兼顾正确性和简洁性public void quickSort(int[] a, int low, int high) { if (low high) return; int pivot a[low (high - low) / 2]; int left low, right high; while (left right) { while (a[left] pivot) left; while (a[right] pivot) right--; if (left right) { int tmp a[left]; a[left] a[right]; a[right] tmp; left; right--; } } quickSort(a, low, right); quickSort(a, left, high); }这个版本是Hoare分区的简化变体不需要额外处理主元归位边界条件也比较规整。面试时写上这个版本配合口头解释我在用双向扫描分区左边找比主元大的右边找比主元小的交换基本就过关了。注意主元选择用了low (high - low) / 2而不是(low high) / 2这样写可以防止low high溢出在一块细节上能体现出你踩过坑。6.2 高频变形题数组中的第K大元素快速排序最经典的应用变形是快速选择QuickSelect。它的思路是利用分区操作返回的主元位置 p如果 p 恰好等于目标位置 K那主元就是答案如果 K 在左边就只递归左边否则只递归右边。每次只处理一边期望复杂度O(n)最坏O(n²)。public int findKthLargest(int[] nums, int k) { int n nums.length; int target n - k; // 第K大转为第(n-k)小 int low 0, high n - 1; while (low high) { int p lomutoPartition(nums, low, high); if (p target) return nums[p]; else if (p target) low p 1; else high p - 1; } return -1; }LeetCode上的215题数组中的第K个最大元素就是这个经典场景。暴力解法是先排序再取下标O(n log n)用快速选择平均O(n)比排序快一个量级。需要提醒的是快速选择在极度糟糕的主元选择下依然可能退化O(n²)所以笔试里如果要求最坏情况保证应该改用堆或者BFPRT算法中位数的中位数算法。6.3 变体题颜色分类荷兰国旗问题LeetCode 75题颜色分类要求把只含0、1、2的数组排好序标准解法就是三路快排的一种特例。思想完全一样以1为主元把0放左边2放右边。这题不需要递归一次扫描就能完成是检验你三路快排理解程度的最佳练习题。练习的时候一定要想想如果数组只有0和1两种值这段代码还能不能正常工作边界条件是死循环的高发区。6.4 避坑经验笔试中反复踩到的三个雷第一个雷是死循环。在双向扫描分区里如果两个while循环没有加边界检查或者内层循环条件写成了而不是指针可能越过区间边界导致数组越界或无限循环。我的经验是对每个分区先写小样例手推一遍比如[3,1,4,2]这种长度4的数组完整走一遍流程能发现大多数边界错误。第二个雷是递归边界不统一。不同版本的分区函数对应不同的递归边界。Lomuto分区返回的p位置已经确定递归范围是[low, p-1]和[p1, high]Hoare分区返回的p只是分割点递归范围是[low, p]和[p1, high]。混用两者的记忆方式是写出看起来对、跑起来崩代码的头号原因。第三个雷是过度优化。我见过有同学在面试时炫技写个超复杂的双轴快排结果写一半忘了边界条件当场翻车。面试官通常更看重你能不能写一个正确的快排然后清晰地讲解复杂度和优化点。先把最简单版本写对再谈优化是稳妥的策略。7. 快排在真实业务中的样子不只是教科书玩具7.1 数据库与搜索引擎的排序场景你可能觉得快排只是个面试题但实际上它遍布底层系统。关系型数据库执行SQL中的ORDER BY时如果数据量能装进内存优化器常常选择快排或堆排序数据量大到需要外部排序时又会把快排作为归并段内部排序的手段。搜索引擎的倒排索引在合并多个有序列表时也用类似分治的思想。可以说任何需要快的排序场景背后几乎都有快排或其变体的影子。7.2 我自己的一次性能优化经历前几年做某个数据清洗组件遇到的场景是每天凌晨处理上亿条原始日志需要按用户ID排序后做去重聚合。最初实现直接调用了通用排序函数跑一次要四十多分钟。后来定位发现用户ID的分布有明显头部效应——大量重复ID。我把排序换成三路快排思路同时用随机化主元避免退化排序耗时直接从40分钟降到了12分钟左右。这个优化只用了一天就完成而收益是持续性的那次的体会是快排的每个优化细节不是学术炫技是真的能换算成服务器成本和等待时间的。7.3 什么时候不要用快排快排不是万能的。如果需要稳定排序比如对对象数组按多个字段逐级排序快排不合适应该用归并排序或TimSort如果数据量极大放不进内存快排的原地特性优势不再明显外部排序归并思想的延伸才是正解如果数据是近乎有序的流式数据插入排序甚至比快排更高效。学会判断用什么排序比会写快排更体现算法素养。8. 集训第08天的实战建议与作业8.1 今天的训练清单裸写Lomuto快排要求在10分钟内无错写出来并用[5,1,1,2,0,0]这类含重复元素的数组测试裸写Hoare快排和Lomuto版本对照重点体会两者递归边界的不同实现快速选择解决LeetCode 215题对比运行时间和直接排序再取值的差异实现三路快排解决LeetCode 75题颜色分类然后回头比较三路快排和普通快排对大量重复元素的耗时思考题如果输入是1亿个取值范围在[0,10]的整数还有比三路快排更快的方法吗提示计数排序O(n)8.2 一些过来人的体会我在集训群里的习惯是要求每个学员把自己写的快排跑一遍有序数组、逆序数组、全部相同元素、随机数组四组测试。前三种情况能立刻暴露主元选择的问题。很多学员跑完才发现自己背的模板在随机数组上跑得飞快一到逆序数组就慢如蜗牛。这个过程比光看复杂度分析印象深刻得多。还有一个小技巧用断点单步调试一个长度为4或5的数组把每次交换后的数组状态打出来。这一步能让你彻底看清分区过程。我在带新人时经常说能把排序过程手写画出来的人写代码时几乎不会犯边界错误。8.3 关于背模板与理解原理的一点看法基础算法集训走到第8天该不该背模板我的态度是在面试高压环境下一个肌肉记忆级别的模板能给你兜底但模板只是起点你必须能解释清楚模板每一步为什么这样写。快速排序的考点远不止写出来它背后牵涉分治思想、随机化算法、复杂度分析、工程优化、甚至稳定性与内存模型用这一道题就能串起大半个算法基础体系。这也是为什么各大厂和LeetCode必刷基础算法题清单里快排永远是常客。如果你能把这篇笔记里的代码都亲手敲一遍把每个为什么都想明白那么快速排序对你来说就不再是一个需要背诵的代码而是一个可以随手修改、灵活运用的工具。这才是集训第08天的真正目的。