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和i+1位置的元素交换。
最终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]和[pivotIndex+1, right]分别再调用快排。但恰恰是这个“简单”的区间切分，是手写快排翻车率最高的地方。
我总结下来，区间切分出错基本逃不出三种：
- 把基准自己也递归进去了：写成
[left, pivotIndex]，导致基准反复参与分区，轻则效率下降，重则死循环； - 边界差一：写成
[left, pivotIndex-2]或[pivotIndex+2, 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 - 1，j从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, i+1, right)是基准归位，pivotIndex - 1和pivotIndex + 1是递归切分。把这五处记牢，快排基本不会写错。
5.2 手动跑一遍，验证每个下标
光看代码不够，我建议你拿个小数组手动跑一遍，把每个变量的值写下来。比如[3, 7, 1, 9, 4]：
| 步骤 | j | arr[j] | 与 pivot=4 比较 | i | 数组状态 |
|---|---|---|---|---|---|
| 初始 | - | - | - | -1 | [3,7,1,9,4] |
| 1 | 0 | 3 | <=4，交换 | 0 | [3,7,1,9,4] |
| 2 | 1 | 7 | >4，跳过 | 0 | [3,7,1,9,4] |
| 3 | 2 | 1 | <=4，交换 | 1 | [3,1,7,9,4] |
| 4 | 3 | 9 | >4，跳过 | 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，双轴快排加插入排序加计数排序的混合策略。那个实现里能看到很多工程上的取舍，比如小数组切插入排序、重复元素多时切三路分区。看懂它，你对“算法怎么落地成工业级代码”会有全新的认识。
我自己是把快排当成一个“算法锚点”来用的：每次学新算法，都拿它和快排比一比——时间复杂度、空间、稳定性、适用场景。比着比着，脑子里就有一张排序算法的全景图了。面试被问到任何一个，都能快速定位到它的位置和特点。
最后分享一个我个人的小习惯：每次换工作前，我会把快排、归并、二分查找这三个手写一遍，不看任何资料。这三个是面试的“基本功三件套”，能白纸写对，说明基本功没丢。快排尤其值得反复写，因为它的边界细节多，隔一段时间不写就容易手生。写的时候别求快，求每一行都说得清为什么，这样面试官怎么追问你都不慌。
