1. 面试官让你手写快排，其实在考三件事
1.1 第一层考查：你的partition是否真的"分对了"
很多候选人把快排背得很熟：选基准、左右扫、递归，一气呵成。但面试官真正看的不是你能不能写出来，而是你写出来的partition是不是一个正确的partition。我见过不少人的快排代码一眼看上去没毛病，跑起来却死循环或栈溢出，问题几乎都出在分区逻辑上。
partition的核心职责只有一句话：以基准值为界，把数组划分成左小右大两部分，并返回基准值最终所在的位置。这个"返回位置"极其关键，因为后续递归全靠它来界定区间。如果返回的位置不对，递归范围就会错乱，要么漏排元素，要么无限递归。
常见错误我列几个：
- 左右指针的移动顺序搞反，导致基准值无法落在正确位置；
while (left < right)写成while (left <= right)，在特定输入下指针越界；- 递归时把
quickSort(left, pivotIndex - 1)和quickSort(pivotIndex + 1, right)写成包含pivotIndex本身的区间，于是基准值永远被反复排序。
这些错误在代码里藏得都不深，一旦面试官让你举一个例子手动跑一遍，立刻就会暴露。所以我的建议是：不要单纯背代码，要把partition的执行过程亲手推一块小数组，推通了再去写。
1.2 第二层考查：你能否讲清楚时间复杂度
手写快排只是及格线，能讲复杂度的才真正开始打分。快排的递归式是：
T(n) = T(k) + T(n-1-k) + O(n)其中k是每次partition后基准值左边元素的数量。不同输入对应的 k 不同，复杂度差异极大：
- 最好情况：每次都能把数组对半分，
T(n) = 2T(n/2) + O(n)，解得 O(n log n)； - 最坏情况：每次都分出
k=0，T(n) = T(n-1) + O(n)，求和之后是 O(n²)； - 平均情况：基于随机排列的期望，正规推导需要用到概率分析，结论仍然是 O(n log n)。
面试时如果只答出"平均O(n log n)、最坏O(n²)"，其实只拿了一半分。面试官大概率会追问一句："平均情况的O(n log n)是怎么来的？" 这时候你要能说出来"每一步partition的时间是O(n)，递归层数是期望O(log n)层"，而不是干背结论。更深一层，如果聊到有序数组会让快排退化成O(n²)，那就进入了本文第3章的话题。
1.3 第三层考查：代码规范性与边界防御
最后，面试官还在透过代码看你有没有工程意识。真正严谨的快排代码不是只写主流程，还包括：
- 对空数组、单元素数组的防御；
- 递归终止条件的清晰处理；
- 变量命名的可读性；
- 是否在partition里对指针做了安全校验。
我举个例子，很多人写的递归入口长这样：
public 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); }这段代码本身正确，但问题是：你没解释为什么left >= right就返回。面试时我建议主动补一句："left 等于 right 说明区间只有一个元素，天然有序；left 大于 right 说明上一个区间已经被分割完，不存在需要处理的子区间。" 这种主动解释，比等着面试官问要加分得多。
1.4 关于手写代码的"肌肉记忆"
顺便说一个很多人的误区：以为在纸上写代码和编辑器里一样，随手就能调。实际上，面试手写时没有编译器帮你检查，也没有报错提示，唯一能依赖的是对代码每个分支的明确理解。我见过候选人把代码写对了，但改了一个边界条件之后自己也说不清为什么，这种情况反而比写错更危险——它说明你没有真正掌握。
所以，去面试之前，我强烈建议你至少把快排的partition手动推导10遍以上，用不同的输入数组，确认每一步指针移动和交换都合理。这比背二十种模板都有用。
2. 快排的核心机制与"挖坑法"实现细节
2.1 为什么面试推荐"挖坑法"而不是"交换法"
快排的partition写法五花八门，最常见的两大流派是"挖坑法"和"交换法（指针交替交换）"。我在带人练题时发现，对绝大多数候选人来说，挖坑法的容错率更高。
挖坑法的核心思路是：先把基准值"拿出来"，在数组里留一个"坑"；然后从右往左找比基准小的元素来填坑，填完之后新位置又成为一个坑；再从左往右找比基准大的元素去填这个新坑……如此交替，最后将基准值放入最终的坑位。
交换法则是在左右指针相遇过程中不断交换不满足条件的元素，到最后再把基准值换到中间。它的问题是：交换次数多，而且很多人在指针移动的先后顺序上容易搞混，一乱就错。
挖坑法为什么更稳？因为它每一步的"状态"是清晰的——当前哪里是坑、应该谁去填、填完坑到了哪里，逻辑是一条直线。用手推一次就知道它不容易写错。
2.2 我用具体数组走一遍挖坑法
假设输入数组为：
[4, 7, 6, 5, 3, 2, 8, 1]选第一个元素4作为基准值，把它从数组中拿出来，此时位置0就是一个"坑"。
坑位: arr[0] = 4 已被拿出 左指针 left = 0，右指针 right = 7第一步，从右往左找小于4的元素。right=7是1，小于4，把1填入坑位arr[0]。此时数组变成：
[1, 7, 6, 5, 3, 2, 8, 坑(0)]右指针停在7的位置，它变成了新的坑位。
第二步，从左往右找大于4的元素。left=1是7，大于4，把7填入坑位arr[7]。数组变成：
[1, 坑(1), 6, 5, 3, 2, 8, 7]左指针停在1的位置，它变成了新的坑位。
第三步，从右往左找小于4的元素。right=6是8，不小于4，继续；right=5是2，小于4，把2填入arr[1]。数组变成：
[1, 2, 6, 5, 3, 坑(5), 8, 7]第四步，从左往右找大于4的元素。left=2是6，大于4，把6填入arr[5]。数组变成：
[1, 2, 坑(2), 5, 3, 6, 8, 7]第五步，从右往左找小于4的元素。right=4是3，小于4，把3填入arr[2]。数组变成：
[1, 2, 3, 5, 坑(4), 6, 8, 7]第六步，从左往右找大于4的元素。left=3是5，大于4，把5填入arr[4]。数组变成：
[1, 2, 3, 坑(3), 5, 6, 8, 7]此时right=3，left=3，循环结束。把基准值4放入这个坑位：
[1, 2, 3, 4, 5, 6, 8, 7]基准值4的最终下标是3，左侧全是小于4的，右侧全是大于等于4的。这个例子能很直观地展示挖坑法的完整流程。
2.3 写出对应的Java代码
public static void quickSort(int[] arr, int left, int right) { if (left >= right) { return; } int pivot = arr[left]; int i = left; int j = right; while (i < j) { // 从右往左找小于 pivot 的元素 while (i < j && arr[j] >= pivot) { j--; } if (i < j) { arr[i] = arr[j]; i++; } // 从左往右找大于 pivot 的元素 while (i < j && arr[i] <= pivot) { i++; } if (i < j) { arr[j] = arr[i]; j--; } } // 循环结束时 i == j，这里是最终坑位 arr[i] = pivot; quickSort(arr, left, i - 1); quickSort(arr, i + 1, right); }注意这里我用的是>=和<=，意味着等于基准值的元素不会被移动。这样做的直接好处是：当数组里有大量重复元素时，不会因为指针反复跨过相同值而退化得太厉害。不过它并没有彻底解决重复元素问题，这一点第3章会展开讲。
2.4 两个容易踩的细节
第一个细节是：挖坑法里i++和j--的时机。很多人在arr[i] = arr[j]之后忘了移动指针，导致下一次循环又检查同一个位置，死循环。我刚才代码里用i++和j--来推进，就是防止这种情况。
第二个细节是：内层while必须保证i < j。假如不写这个条件，在反向扫描时可能越过对方指针，导致填坑填到错误位置。这是新手最爱犯的错，没有之一。
3. 最不稳定的环节：有序输入与重复元素
3.1 有序数组如何让快排退化到O(n²)
前面提到快排最坏情况是O(n²)，但我敢说一半以上的候选人无法立刻举出触发最坏情况的例子。其实最典型的输入就是已经有序的数组（升序或降序）。
假设输入是[1, 2, 3, 4, 5, 6, 7, 8]，仍然选第一个元素1作为基准。partition时，从右往左找小于1的元素，一路找到1自己都没有，最后基准值仍停在最左边。于是递归区间变成[2, 8]和空区间。再对[2, 8]做partition，又分出[3, 8]和空区间……递归树是一条单链，每一层partition的扫描长度是n、n-1、n-2……总比较次数就是n + (n-1) + ... + 2 + 1 = O(n²)。
数据量小的时候无感，但数据量一大就很明显。我自己在本地跑过一个1万元素的升序数组，用的就是这种"取第一个元素当基准"的写法，耗时和快排随机数组差了不止一个数量级。面试时如果被问到"快排在什么输入下会退化"，拿这个例子说，比背一句"有序时退化"要有说服力得多。
3.2 随机化pivot与三数取中
解决退化最直接的方法是：不要固定取第一个元素，而是随机选一个位置作为基准，选完再和arr[left]交换，后续逻辑不变。
int pivotIndex = left + (int) (Math.random() * (right - left + 1)); swap(arr, left, pivotIndex); int pivot = arr[left];这样一来，即使输入是一组升序数组，你选的基准也可能落在中间位置，偶然情况下最坏复杂度依然可能出现，但概率在随机化后变得微乎其微。这就是为什么工程上常说的"随机化快排的平均表现很好"。
除了随机化，还有一个常见优化叫三数取中（median-of-three）：比较arr[left]、arr[mid]、arr[right]三者，取中间值作为基准。好处是即使数组本来有序，选出来的基准也不会总是最小值或最大值，退化概率进一步降低。有些面试官会问"除了随机化你还有什么办法优化快排"，三数取中、插入排序兜底、三路快排都是很好的加分回答。
3.3 重复元素多的时候，经典快排会"偏科"
还有一个常被忽视的场景：大量重复元素。比如一个全是5的数组，经典快排会怎样？
选第一个5作为基准，arr[j] >= pivot一直成立，右指针会一直向左扫；arr[i] <= pivot一直成立，左指针会一直向右扫。两个指针在中点相遇，然后基准落位，递归分成两个相等的区间。这样看起来似乎没问题，但问题在于partition时要反复遍历很多相等的元素，递归深度和比较次数并不会因为你"跳过相等元素"而减少太多。在某些实现下，重复元素甚至会引发极端的指针移动，效率不如三路快排。
三路快排的思路是：把数组分成三块——小于基准区、等于基准区、大于基准区。partition结束后，等于基准的那一块已经在正确位置上，递归时只需要处理左右两块。
public static void quickSort3Way(int[] arr, int left, int right) { if (left >= right) { return; } int pivot = arr[left]; int lt = left; // arr[left+1 ... lt] < pivot int i = left + 1; // 扫描指针 int gt = right; // arr[gt ... right] > pivot while (i <= gt) { if (arr[i] < pivot) { swap(arr, lt, i); lt++; i++; } else if (arr[i] > pivot) { swap(arr, i, gt); gt--; } else { i++; } } quickSort3Way(arr, left, lt - 1); quickSort3Way(arr, gt + 1, right); }面试中能主动写出三路快排，属于明显的加分项。它尤其适合回答"如果数据重复率很高你会怎么做"这类问题。
4. 面试中的排序算法选型：快排、归并、堆排怎么回答
4.1 快排是不稳定的，你要能举出实例
排序算法的稳定性指：值相同的元素在排序前后相对顺序是否保持不变。快排显然不满足。我前面挖坑法里arr[j] >= pivot的写法，已经隐含了"相等元素不被交换"的处理，但这并不能保证全局稳定。只要partition过程中发生了跨越式的填坑，就可能改变相同元素的相对顺序。
我之前用[3, 3, 2, 1]这个例子在面试中演示过。取第一个3为基准，右指针找小于3的元素，把1填到坑位，再从左往右找大于3的元素……递归跑完之后，两个3的前后顺序已经对调。这个例子很短，面试官一听就明白。
那面试官为什么关心稳定性？因为他希望你理解不同业务的排序需求。比如按时间排序后还要按优先级排序，如果第二趟排序不稳定，第一趟的结果可能被破坏。工程里真正稳定的排序通常是归并排序。
4.2 什么情况下该说"归并排序更好"
数组快排、链表排序、外部排序这三个场景，归并排序都有自己的优势：
- 链表排序：快排在数组上靠的是O(1)随机访问交换，换到链表上，选基准、扫描指针都会变得非常别扭；归并排序天然适合链表，只需切断和合并节点，不需要额外数组也能做。
- 外部排序：当数据量大到内存放不下，必须分批读取磁盘时，归并排序是外部排序的基石。快排的原地特性在磁盘上没用，归并的"分而治之、逐步合并"反而非常适合多路归并。
- 稳定性需求：归并排序是稳定排序，如果题目明确要求稳定，直接选归并，别用快排。
面试中如果被问"为什么实际很多系统排序用快排而不是归并"，一个标准答法是：内存中数组排序，快排的常数因子小、原地排序省内存，虽然不稳定，但很多场景不要求稳定；归并排序需要额外O(n)空间，链式和外部场景才更划算。
4.3 堆排序呢？以及内省排序的思想
堆排序的最大优点是：最坏时间复杂度严格O(n log n)，而且原地排序。快排最坏会退化到O(n²)，这是面试官很喜欢用来"刁难"的一个点，所以很多候选人会答"用堆排序兜底"。
但堆排序也有明显的缺点：对缓存不友好。它的访问模式是跳来跳去的，数组相邻元素可能相隔很远，CPU缓存命中率远低于快排的线性扫描。所以在实际数据规模下，堆排序往往比快排慢，这就是为什么很多系统的sort函数不用纯堆排序。
更经典的做法是内省排序（introspective sort）：一开始用快排，但当递归深度超过某个阈值（通常是2 * log2(n)）时，改切到堆排序，从而保证最坏复杂度也是O(n log n)。这也是许多标准库的默认实现思路。你如果能把这个原理讲清楚，面试的深度立刻就不一样了。
4.4 给面试候选人的一个话术参考
如果面试官问"你怎么选排序算法"，可以按这个顺序组织回答：
- 先问清楚使用场景：数组还是链表、数据量多大、要不要稳定、有没有额外空间限制；
- 如果默认内存数组排序、无稳定性要求，首选快排，工程实现普遍快且省内存，可以用随机化或三数取中避免退化；
- 如果要求稳定，选归并；
- 如果要求最坏时间复杂度严格O(n log n)且没有额外空间，选堆排序；
- 如果数据重复率高，三路快排可能是最好的选择。
这套回答涵盖了绝大多数面试场景，而且能展现出"我不是背模板，而是会做选型分析"。
5. 高频延伸题：快选算法与TopK问题
5.1 从"变异快排"到QuickSelect
很多面试官在快排之后，会立刻抛出一道进阶题："给你一个无序数组，找出第k大的元素，要求O(n)"。这道题的最优解就是基于快排partition思想改出来的QuickSelect（快选）。
QuickSelect的思路很简单：做一次partition，拿到基准值的位置index，然后比较index和k的关系：
- 如果
index == k，说明基准值就是第k大的元素（或者按第k小处理，具体看题面定义）； - 如果
index < k，说明目标值在右半段，只递归右侧； - 如果
index > k，说明目标值在左半段，只递归左侧。
关键区别在于：快排需要递归两侧，QuickSelect只递归一侧，因此时间复杂度期望是T(n) = T(n/2) + O(n)，也就是O(n)，而不是O(n log n)。
public static int quickSelect(int[] arr, int left, int right, int k) { if (left == right) { return arr[left]; } int pivotIndex = partition(arr, left, right); if (k == pivotIndex) { return arr[k]; } else if (k < pivotIndex) { return quickSelect(arr, left, pivotIndex - 1, k); } else { return quickSelect(arr, pivotIndex + 1, right, k); } }注意这里k是数组下标语义，实际调用前要把"第k大"换算成对应的下标位置。如果题目说"第k大"，可以先做下标换算，或直接在partition时把比较符号反向，两种都行。
5.2 TopK问题的面试完整回答链路
候选人最容易犯的错是：一看到TopK就用堆排序方案，却忽略了面试官考察的其实是QuickSelect思想。完整回答链路应该是：
- 先抛出两个方案分情况讨论：
- 海量数据、内存放不下：用大小为K的最小堆，维护当前最大的K个元素，时间复杂度O(n log K)，K很小的情况下优势巨大；
- 数据都在内存、只需要一次查询：用QuickSelect，期望O(n)，但最坏O(n²)，可以用随机化pivot缓解；
- 对比两种方案的差别：堆排序适合动态插入、可增可减的场景；QuickSelect适合静态数组一次性求TopK，且返回结果是无序的；
- 编码时先把边界想清楚：
k的取值范围、空数组、越界检查； - 跑测试时用示例验证，比如
[3,2,1,5,6,4]求第三大，先手动推结果再跑代码。
这套链路下来，基本能覆盖面试官的所有追问。
5.3 手写快排的避坑清单与个人经验
这一节算是给即将面试的人一份"考前检查表"。我根据自己以前踩过的坑和带新人时的观察，整理了下面几条：
第一，一定先用几个特殊输入自测。我建议至少准备四组用例：空数组、单元素数组、逆序数组、全相同元素数组。很多人代码写出来，普通输入跑得好好的，一遇到全相同元素就崩，就是因为没有这层防御。
第二，手动在纸上推一遍执行过程。纸上推演能暴露的问题比编译器多得多：指针没动、越界、栈溢出，都藏不住。推的时候把left、right、基准值、坑位每一步都写出来，看起来慢，其实很值。
第三，现场写代码时，先说明你的设计选择。比如你选了"取第一个元素为基准、挖坑法、递归实现"，不妨跟面试官说一句"我准备这么写，好处是逻辑直观，坏处是重复元素多时会退化，也可以补充三路快排优化"。这会让面试官觉得你是一个有工程判断力的人，而不只是会默写代码。
第四，注意递归深度带来的栈溢出风险。快排递归实现的最坏递归深度是O(n)，如果面试官让你处理极端输入，你可以主动提迭代栈版本，或者提内省排序。不用真的写，说出来就是加分。
第五，如果面试官让你优化，别瞎改。最常见的正确优化顺序是：随机化pivot → 三数取中 → 小区间插入排序兜底 → 三路快排。按这个顺序讲，理由一条比一条清楚。怕的是有人上来就说"用堆排序"，没考虑原地和常数的限制，反而显得对算法选型理解不深。
5.4 一个有意思的练习：自己加日志跑一遍快选
最后分享一个我常用的练习方法：写代码时临时加上指针移动的打印语句，跑几个不同用例，观察left、right、pivotIndex的变化。比如对[6, 3, 8, 1, 9, 2, 7]，每次partition后打印数组和基准位置，你会发现快选和快排的分区过程其实就藏在那些打印信息里。看多了，边界条件变成肌肉记忆，面试手写就不慌了。
我最初自己练习快排时，也是先打印每一步，然后逐步删掉日志，直到能一次性写出无debug版本。这个过程大概花了一周，之后面到的排序题基本都能一遍过。
