1. 为什么换工作面试总爱问快速排序换过几次工作的朋友大概都有体会面试官让你手写排序十有八九点的是快速排序。不是冒泡、不是归并偏偏是它。原因其实不复杂——快排是少数几个能同时考察“递归思维、数组原地操作、边界处理、复杂度分析”的算法一道题能问出四五个维度性价比极高。更关键的是它写起来短但写对很难面试官一眼就能看出你是背模板还是真理解。我自己第一次被问快排是在一次社招终面面试官给了张白纸说“写个快排不用跑我看着就行”。我当时凭记忆默了个 Hoare 分区版本结果指针边界写反了递归区间也切错面试官没说话拿笔在纸上画了两条线我当场就明白自己错在哪。那次之后我把快排从头到尾重新啃了一遍总结出一套“三部曲”的解法思路——分区、递归、边界三步各自独立、又能串成一条线。这套思路后来帮我扛过了好几次面试也让我在真实项目里改排序逻辑时不再心虚。这篇内容就是把这套三部曲拆开讲透。它适合正在准备面试的开发者、刚学完递归想找个练手题的初学者也适合工作几年但一直靠Arrays.sort()混日子、想补回基本功的老手。我不会只给你一段能跑的代码就完事而是把每一步“为什么这么写”“换个写法会怎样”“哪里最容易翻车”都摊开讲。看完你至少能做到白纸上手写快排不卡壳面试官追问优化和边界时能接得住。2. 三部曲之一分区到底在分什么2.1 分区的本质是“一次扫描定一个位置”很多人背快排背的是“选基准、左右指针往中间靠、交换”。但如果你问自己一句分区结束之后数组到底处于什么状态能答清楚的人不多。分区的本质其实只有一句话经过一次分区基准元素被放到了它在最终有序数组里应该在的位置并且它左边的都不大于它右边的都不小于它。这句话是理解快排的钥匙。注意“最终位置”四个字——分区不是把数组排好它只保证基准这一个元素归位。剩下的左右两段还是乱的交给递归去处理。所以快排是“分而治之”里最典型的“先分后治”分区负责分递归负责治。我用一个具体例子走一遍。假设数组是[3, 7, 1, 9, 4, 6, 2]选最后一个元素2作为基准。分区过程用一个i指针记录“小于等于基准区域”的右边界从头扫到尾遇到3比2大跳过遇到7跳过遇到1比2小i右移一位把1换到前面遇到9、4、6都比2大跳过扫描结束把基准2和i1位置的元素交换。最终2落在下标 1 的位置左边是[1]右边是[7, 9, 4, 6, 3]。你看2归位了左边全比它小右边全比它大。这就是分区干的事。2.2 两种主流分区写法选哪个有讲究快排的分区至少有三种写法面试里最常见的是 Lomuto 分区和 Hoare 分区。它们不是“哪个更高级”的问题而是各有适用场景。分区方式基准选择扫描方向交换次数特点Lomuto通常取末尾单向从左到右较多代码短、好理解、边界清晰Hoare通常取开头双向向中间靠较少效率略高、边界易错三路分区取基准值单向分三段视重复元素而定重复元素多时优势明显Lomuto 的优点是逻辑线性、不容易写错缺点是当数组里重复元素多或者已经接近有序时交换次数偏多。Hoare 的双向扫描在平均情况下交换更少但指针移动的边界条件非常容易写崩——我见过太多人 Hoare 版本写出来死循环或者数组越界。我的建议是面试手写优先 Lomuto。原因很实在——面试官看的是你的思路是否清晰不是看你炫技。Lomuto 你能一次写对比 Hoare 写得花哨但边界错了好得多。等你把 Lomuto 写熟了再去啃 Hoare 和三路分区那是进阶的事。2.3 基准选择直接决定你会不会退化成 O(n²)快排最坏情况是 O(n²)什么时候发生当每次选的基准都是当前区间里的最大或最小值时。最典型的场景就是对一个已经有序的数组做快排而你每次都取末尾元素当基准。这时候每次分区只能分出一个元素递归深度变成 n复杂度直接退化。所以基准选择不是随便选的。常见策略有三种固定选末尾/开头实现最简单但对有序数组不友好随机选用随机数挑一个位置和末尾交换再按 Lomuto 走。期望复杂度 O(n log n)能有效规避人为构造的最坏输入三数取中取头、中、尾三个元素的中位数当基准。工程实现里很常见因为开销小、效果稳。我实测下来随机化版本在面试里是性价比最高的——加两行代码就能把“有序数组退化”这个坑填上面试官问起来你还能顺势聊期望复杂度加分。// 随机化基准把随机位置的元素换到末尾再走标准 Lomuto int randomIndex left (int)(Math.random() * (right - left 1)); swap(arr, randomIndex, right); int pivot arr[right];注意随机化用的是Math.random()范围要算准。right - left 1是区间长度别写成right - left否则最后一个元素永远选不到虽然不影响正确性但随机性打了折扣。3. 三部曲之二递归怎么切区间才不出错3.1 递归的“治”就是把左右两段各自排好分区做完基准归位接下来就是递归处理左右两段。这一步逻辑上简单得不能再简单对[left, pivotIndex-1]和[pivotIndex1, right]分别再调用快排。但恰恰是这个“简单”的区间切分是手写快排翻车率最高的地方。我总结下来区间切分出错基本逃不出三种把基准自己也递归进去了写成[left, pivotIndex]导致基准反复参与分区轻则效率下降重则死循环边界差一写成[left, pivotIndex-2]或[pivotIndex2, right]漏掉元素排序结果不对递归终止条件写错left right写成left right当区间只剩一个元素时还继续递归栈溢出。正确的切分永远是左区间[left, pivotIndex - 1]右区间[pivotIndex 1, right]基准pivotIndex不参与后续递归。因为它在分区那一步已经归位了再动它纯属多余。3.2 终止条件为什么是 left right递归的终止条件我建议你记成“区间里元素少于两个就停”。left right正好表达这个意思left right时区间只有一个元素天然有序left right时区间为空也没什么可排的。很多人纠结left right和left right的区别其实你只要想清楚“一个元素的区间需不需要排序”就行——不需要。所以当left right时就应该返回条件写成if (left right) return;最稳妥。这里有个我踩过的坑早期我写递归时喜欢用if (left right) { ... }把递归体包起来而不是提前 return。两种写法等价但嵌套一层之后代码缩进变深边界判断和递归调用混在一起读起来累改起来也容易漏。后来我统一改成提前 return 的写法逻辑层次立刻清爽了。3.3 递归深度和栈溢出一个容易被忽略的现实问题理论上快排的递归深度是 O(log n)但那是平均情况。最坏情况下递归深度是 O(n)。对一个百万元素的数组如果退化递归深度上百万JVM 的栈大概率撑不住直接StackOverflowError。那怎么办两个思路随机化基准从源头降低退化的概率这是最省事的尾递归优化 / 先递归短的一边每次递归时先处理较短的那一半较长的那一半用循环迭代处理。这样递归深度被压到 O(log n)即使最坏情况也不会爆栈。while (left right) { int pivotIndex partition(arr, left, right); // 先递归短的一边长的一边继续循环 if (pivotIndex - left right - pivotIndex) { quickSort(arr, left, pivotIndex - 1); left pivotIndex 1; } else { quickSort(arr, pivotIndex 1, right); right pivotIndex - 1; } }这段“先短后长”的写法面试里如果你能主动提出来是很加分的。它说明你不只是会背模板还考虑过工程上的健壮性。4. 三部曲之三边界处理才是真正的分水岭4.1 指针移动的“先加还是先减”陷阱分区里指针怎么动是快排最细的细节。以 Lomuto 为例i初始化为left - 1j从left扫到right - 1。注意是right - 1不是right——因为right位置放的是基准不参与扫描。int i left - 1; for (int j left; j right; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } swap(arr, i 1, right); return i 1;这里有两个极易出错的点i初始是left - 1不是left。因为i表示“已确认小于等于基准区域的最后一个位置”初始时这个区域为空所以是left - 1循环条件是j right不是j right。基准在right位置不能拿它和自己比。我见过有人把i初始化成left结果第一个比基准小的元素被换到了错误位置整个分区全乱。这种错误很隐蔽因为代码能跑只是结果不对调试起来要命。4.2 相等元素怎么处理一个影响性能的隐藏开关判断条件写arr[j] pivot还是arr[j] pivot看起来只是差一个等号实际影响很大。用等于基准的元素会被划到左边分区相对均衡用等于基准的元素全被划到右边当数组里有大量重复元素时分区会严重倾斜退化成 O(n²)。举个极端例子数组全是同一个值比如[5,5,5,5,5]。如果用每次分区基准归位在最左边右边是剩下所有元素递归深度 n复杂度 O(n²)。用虽然也会倾斜都归到左边但至少不会比这更差。真正解决重复元素问题的是三路分区把数组分成“小于、等于、大于”三段等于基准的那一段直接跳过不参与递归。// 三路分区核心思路伪代码 // lt 指向小于区右边界gt 指向大于区左边界i 是当前扫描指针 while (i gt) { if (arr[i] pivot) swap(arr, lt, i); else if (arr[i] pivot) swap(arr, i, gt--); else i; }三路分区在处理“大量重复元素”的数组时能把复杂度从 O(n²) 拉回 O(n log n)这是它最大的价值。面试里如果面试官问“快排有什么优化”三路分区是标准答案之一。4.3 小数组切换插入排序工程实现的常规操作真实工程里的快排实现几乎不会一路递归到底。当区间小到一定程度通常是 8 到 16 个元素会切换成插入排序。原因很实在小数组上递归调用的开销压栈、出栈、函数调用比插入排序本身的 O(n²) 还大切换之后整体更快。private static final int INSERTION_THRESHOLD 10; if (right - left 1 INSERTION_THRESHOLD) { insertionSort(arr, left, right); return; }这个阈值取多少不同实现有差异JDK 的DualPivotQuicksort里用的是 47 左右。面试里你不需要记具体数字但要知道“小数组切插入排序”这个优化点以及它背后的理由——减少递归开销。5. 完整代码与逐行拆解5.1 一份可以直接背下来的 Lomuto 版本把前面三部曲串起来就是下面这份代码。我特意写成最朴素的形式没有花哨的优化方便你面试时默写。public class QuickSort { public static void quickSort(int[] arr, int left, int right) { // 终止条件区间元素少于两个 if (left right) { return; } // 分区基准归位返回基准下标 int pivotIndex partition(arr, left, right); // 递归左右两段分别排序基准不参与 quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 1, right); } private static int partition(int[] arr, int left, int right) { int pivot arr[right]; // 取末尾元素为基准 int i left - 1; // 小于等于区的右边界 for (int j left; j right; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } swap(arr, i 1, right); // 基准归位 return i 1; } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } }这份代码大概二十行但每一行都有讲究。left right是终止条件i left - 1是边界初始化j right是扫描范围swap(arr, i1, right)是基准归位pivotIndex - 1和pivotIndex 1是递归切分。把这五处记牢快排基本不会写错。5.2 手动跑一遍验证每个下标光看代码不够我建议你拿个小数组手动跑一遍把每个变量的值写下来。比如[3, 7, 1, 9, 4]步骤jarr[j]与 pivot4 比较i数组状态初始----1[3,7,1,9,4]1034交换0[3,7,1,9,4]2174跳过0[3,7,1,9,4]3214交换1[3,1,7,9,4]4394跳过1[3,1,7,9,4]结束--基准归位-[3,1,4,9,7]最后基准4落在下标 2左边[3,1]都小于它右边[9,7]都大于它。手动跑一遍的价值在于你能亲眼看到i是怎么一步步右移的比死记代码强得多。5.3 复杂度分析面试必问的收尾写完代码面试官大概率会问复杂度。标准回答是平均时间复杂度 O(n log n)每次分区大致均分递归深度 log n每层扫描 n 个元素最坏时间复杂度 O(n²)每次分区极不均衡递归深度 n空间复杂度 O(log n)递归栈的深度平均 log n最坏 n稳定性不稳定。分区时的交换会打乱相等元素的相对顺序。这里有个加分点主动提“快排是不稳定排序”。很多人只记得复杂度忘了稳定性。如果面试官追问“那什么排序稳定”你可以接“归并排序稳定但需要 O(n) 额外空间”一来一回就把话题引到你熟悉的领域了。6. 面试现场的几个真实翻车点6.1 白纸上写代码先写框架再填肉面试手写代码和 IDE 里写完全是两回事。IDE 有补全、有报错、能调试白纸什么都没有。我的经验是先写方法签名和递归框架再填分区细节。框架就三行——终止条件、分区调用、两次递归。这三行写出来面试官就知道你思路是对的剩下的分区即使有小瑕疵也容易补救。反过来如果你一上来就抠分区细节写到一半发现指针乱了整段划掉重写观感很差。先框架后细节是手写代码的基本策略。6.2 被追问“为什么基准不参与递归”怎么答这个问题看着简单答不好会暴露理解深度。标准答案是分区结束时基准已经在最终位置上了它左边都不大于它右边都不小于它所以它不需要再参与任何排序。如果你答“因为递归进去会死循环”那只说对了一半——死循环是现象归位才是本质。6.3 数组越界和死循环的排查思路如果你写的快排跑起来报ArrayIndexOutOfBoundsException八成是i 1越界或者j的范围写错。排查顺序建议是先看partition里j的循环上界是不是right而不是right - 1再看swap(arr, i 1, right)里的i 1有没有可能超过right最后看递归调用里pivotIndex - 1和pivotIndex 1有没有越界。如果是死循环基本就是递归区间没排除基准或者while循环里指针没动。把这两处检查一遍问题一般都能定位。7. 从快排延伸出去的学习路径快排写熟之后我建议顺着它往下走两步。第一步是归并排序它和快排是“分治”的两面快排先分后治归并先治后分快排不稳定、原地归并稳定、需要额外空间。把这两个对比着学分治思想就通透了。第二步是堆排序它不走递归用完全二叉树的性质做原地排序最坏也是 O(n log n)是快排最坏情况的一个兜底方案。再往深了走可以看看 JDK 里Arrays.sort()对基本类型的实现——DualPivotQuicksort双轴快排加插入排序加计数排序的混合策略。那个实现里能看到很多工程上的取舍比如小数组切插入排序、重复元素多时切三路分区。看懂它你对“算法怎么落地成工业级代码”会有全新的认识。我自己是把快排当成一个“算法锚点”来用的每次学新算法都拿它和快排比一比——时间复杂度、空间、稳定性、适用场景。比着比着脑子里就有一张排序算法的全景图了。面试被问到任何一个都能快速定位到它的位置和特点。最后分享一个我个人的小习惯每次换工作前我会把快排、归并、二分查找这三个手写一遍不看任何资料。这三个是面试的“基本功三件套”能白纸写对说明基本功没丢。快排尤其值得反复写因为它的边界细节多隔一段时间不写就容易手生。写的时候别求快求每一行都说得清为什么这样面试官怎么追问你都不慌。