快速排序面试必考：首元素枢轴的Lomuto与Hoare分区详解

面试手写排序算法时，快速排序几乎是必考项。但很多人写出来的代码，在小数组或已经有序时能跑，一上强度就翻车。今天要聊的这个版本——以第一个元素为枢轴的快速排序——正是最常见也最容易写错的一个变体。之所以拿它开刀，是因为枢轴选在哪个位置，直接影响分区的写法、递归边界和性能表现，把这些细节想清楚，其他任何快排变体基本都能一眼看懂。

这篇文章会把两种主流的原地分区思路都拆开讲，配上能直接跑的代码和踩坑记录，用实际推演帮你理解每一步交换到底在干什么。适合正在刷算法题、准备面试，或者工作中需要手写排序逻辑的同学参考。

1. 快速排序为什么值得再写一遍，以及"第一个元素当枢轴"到底意味着什么

1.1 一个快速排序的完整流程是什么样子

快速排序干的事可以概括成三步：

1. 选一个枢轴元素。
2. 分区：把小于枢轴和大于枢轴的元素，大致分到两边。
3. 递归对左右两边的区间重复执行。

用整理扑克牌打比方：你从中间抽出一张牌当基准，剩余牌里比它小的放左边，比它大的放右边，然后再把左边和右边各自重复这套操作，直到每个区间只剩一张牌。

这里有两个关键点需要记住。

第一，分区完成后，枢轴落到了“左小右大”的分界线上，所以它的最终位置已经确定，后面不再参与排序。

第二，递归处理的是“左侧区间”和“右侧区间”，不包括已经归位的枢轴。

“大致分到两边”这几个字很值得琢磨。分区并不要求两边完全有序，只保证大小关系正确。快排之所以快，靠的是每轮分区都能把问题规模大致砍半，递归深度保持在 log n 左右。

那为什么非要讨论“第一个元素当枢轴”呢？因为快排的变体和坑，大多出在枢轴的选择上。换一个枢轴位置，分区的实现逻辑就会跟着变化。以第一个元素为枢轴，是从经典模板里最容易改出一个隐蔽 Bug 的写法，这也是它值得单独讲的原因。

1.2 枢轴选第一个元素：看似最省事，其实坑最多

选第一个元素当枢轴的好处非常直观：代码简单，不需要生成随机数，也不需要额外判断位置。对完全无序的数据来说，它和随机选枢轴在平均性能上没有本质区别。

但它的致命弱点是数据有序性。如果数组本身已经排好序（升序），每次取到第一个元素作为枢轴，它恰好是当前区间的最小值。分区后枢轴落在最左侧，等于只排除掉一个元素。下一轮右边的子区间几乎是原来的长度，递归树变成一根斜线，时间复杂度从 O(n log n) 滑到 O(n²)。

有人可能会说，那先随机打乱数组不就行了？这正是问题的另一面。既然枢轴选择会直接影响复杂度，为什么不干脆用随机枢轴或三数取中？原因是教科书和很多入门教程为了把“分区”这个核心思想讲透，刻意选最简单的首元素枢轴，先保证逻辑正确，再谈性能优化。这本身没有错，但如果你带着这个模板直接去生产环境处理大体量数据，就会踩到上面说的退化坑。

更现实的情况是，很多排序场景中数据并非完全无序。比如日志里的时间戳、数据库导出表按某列排好序，这时首元素枢轴的退化不是理论上的担忧，而是实际会发生的事故。因此在面试或代码评审里，能主动说出“这个变体的最坏情况是什么、为什么产生、怎么缓解”，比背出一个无 Bug 的实现更打动人。

2. 两种最主流的原地分区实现：Lomuto 变体与 Hoare 分区

2.1 先建立直觉：最容易理解的非原地版本

几乎所有教科书在解释快排后，都会让你先写出这个版本：

function quicksortSimple(arr) { if (arr.length <= 1) return arr; const pivot = arr[0]; const left = []; const right = []; for (let i = 1; i < arr.length; i++) { if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return [...quicksortSimple(left), pivot, ...quicksortSimple(right)]; }

它确实很直观：拿第一个元素当枢轴，把剩下的元素按大小塞进两个新数组，然后递归拼接。但注意，它有两个缺点，正是接下来原地版本要解决的问题。

缺点一是额外空间。每层递归都创建两个新数组，空间复杂度是 O(n log n) 级别，加上递归栈，内存开销不小。缺点二是它没有在同一个数组上操作，如果要实现真正的 in-place 排序，这个版本没法用。

不过它有一个很大的优点：逻辑极其清晰，适合在一分钟内讲清楚快排的分治思想，也适合写单元测试时作为对照参照。把它当作理解快排的起点，很值得。

2.2 Lomuto 变体：第一版能跑的原地实现

原地快排要在同一个数组上做交换，最经典的写法是 Lomuto 分区，网上流传的“快速排序模板”大多基于它。

标准 Lomuto 习惯拿最后一个元素当枢轴，但题目要求第一个元素，所以需要做一个小改造：

function partitionLomuto(arr, low, high) { const pivot = arr[low]; let v = low; for (let j = low + 1; j <= high; j++) { if (arr[j] < pivot) { v++; if (v !== j) { [arr[v], arr[j]] = [arr[j], arr[v]]; } } } if (v !== low) { [arr[low], arr[v]] = [arr[v], arr[low]]; } return v; }

思路可以这样理解：v 维护着“已经确认小于枢轴的元素的右边界”，j 是当前扫描位置。每遇到一个比枢轴小的元素，就把右边界向右扩一格，并把新发现的元素交换到边界处。扫描结束后，所有小于枢轴的元素都被集中到了区间左侧，此时把枢轴从 low 换到 v 的位置，枢轴就落到了它最终该在的位置。

这里的两个细节值得注意。

第一，最后一步交换是必须的。否则枢轴还待在 low 位置，整个分区就没有把枢轴放到位，后续递归无法正确处理它。

第二，如果 v 正好等于 low，说明所有元素都不小于枢轴，交换自己是多余的，这个判断可以省掉一次操作。

Lomuto 变体有一个小小的性能问题：它每轮要扫描整个区间，且交换次数相对较多。但它在理解难度上是最低的，所以作为第一版实现非常合适。

2.3 Hoare 分区：更快，但边界条件更容易翻车

Hoare 分区是另一种更快的原地分区方式。它的思路不是维护一个“小于区域的边界”，而是用两个指针从两侧相向扫描，分别跳过已经符合大小的元素，直到两个指针交错。

function partitionHoare(arr, low, high) { const pivot = arr[low]; let i = low - 1; let j = high + 1; while (true) { do { i++; } while (arr[i] < pivot); do { j--; } while (arr[j] > pivot); if (i >= j) { return j; } [arr[i], arr[j]] = [arr[j], arr[i]]; } }

指针 i 向右找“不该在左侧”的元素，指针 j 向左找“不该在右侧”的元素，找到后两个都停下，就交换它们。直到 i 与 j 交错，说明整个区间已经完成大小分离。

Hoare 分区最令人困惑的地方在于返回值。它返回的 j 并不是“枢轴现在所在的位置”，而是“左右两个子区间的分界线”。所以递归调用时范围要写成：

quicksortHoare(arr, low, j); quicksortHoare(arr, j + 1, high);

注意左侧递归是包含 j 的，右侧从 j + 1 开始。如果你习惯性地沿用 Lomuto 的j - 1与j + 1写法，就会漏掉 arr[j] 这个元素，严重时会导致死循环。这个问题后面我会单独讲。

两种方式选哪个？Lomuto 实现简单、可读性好，但在某些情况下交换次数多；Hoare 交换少、性能更好，但指针和递归边界都比较绕。我给一个对比表：

实际工程里，很多人会混合使用：主体排序用 Hoare 分区，遇到小规模子数组切到插入排序。但对于学习或面试口述，我更建议先把 Lomuto 写扎实，再掌握 Hoare 作为进阶。

3. 完整实现与关键细节打磨

3.1 递归版完整代码与手动推演

以 Lomuto 变体为例，我给出一段可以直接运行的完整代码：

function quicksort(arr, low = 0, high = arr.length - 1) { if (low >= high) return arr; const pivotIndex = partitionLomuto(arr, low, high); quicksort(arr, low, pivotIndex - 1); quicksort(arr, pivotIndex + 1, high); return arr; } function partitionLomuto(arr, low, high) { const pivot = arr[low]; let v = low; for (let j = low + 1; j <= high; j++) { if (arr[j] < pivot) { v++; if (v !== j) { [arr[v], arr[j]] = [arr[j], arr[v]]; } } } if (v !== low) { [arr[low], arr[v]] = [arr[v], arr[low]]; } return v; }

调用方式很简单：

const data = [7, 2, 1, 8, 5, 3, 6, 4]; quicksort(data); console.log(data); // [1, 2, 3, 4, 5, 6, 7, 8]

我手动推演一遍首个分区，帮你看清 v 和 j 是怎么跑的。初始数组是[7, 2, 1, 8, 5, 3, 6, 4]，low=0、high=7，pivot=7，v=0：

• j=1，arr[1]=2<7，成立：v=1，此刻 v 与 j 相等，不需要交换，数组不变。
• j=2，arr[2]=1<7，成立：v=2，v 与 j 相等，不需要交换，数组不变。
• j=3，arr[3]=8<7，不成立。
• j=4，arr[4]=5<7，成立：v=3，交换 arr[3] 和 arr[4]，数组变为[7,2,1,5,8,3,6,4]。
• j=5，arr[5]=3<7，成立：v=4，交换 arr[4] 和 arr[5]，数组变为[7,2,1,5,3,8,6,4]。
• j=6，arr[6]=6<7，成立：v=5，交换 arr[5] 和 arr[6]，数组变为[7,2,1,5,3,6,8,4]。
• j=7，arr[7]=4<7，成立：v=6，交换 arr[6] 和 arr[7]，数组变为[7,2,1,5,3,6,4,8]。
• 循环结束，交换 arr[0] 和 arr[6]，得到[4,2,1,5,3,6,7,8]，返回 v=6。

此时 7 已经落到索引 6，它的左边全小于它，右边全大于它。接下来递归处理[0, 5]和[7, 7]，右侧只有一个元素，直接返回；左侧继续重复同样的过程。

手动推演的意义在于，当你调试时对某一轮交换结果有疑问，心里有一套“v 维护左边界，j 负责扫描”的心智模型，而不是死记硬背代码。

3.2 几个容易被忽略的细节

细节一：空数组和单元素数组。默认参数high = arr.length - 1在空数组时得到 -1，low=0 与 high=-1 满足low >= high，直接返回，所以空数组是安全的。单元素数组同理，low 与 high 相等，不会进入分区。

细节二：递归边界。Lomuto 的递归必须写pivotIndex - 1和pivotIndex + 1，因为枢轴已经归位，不应该再参与排序。如果写成pivotIndex，左侧递归会把枢轴再次包含进去，可能造成无限循环。

细节三：数组交换。我用了 ES6 的解构赋值写法[arr[i], arr[j]] = [arr[j], arr[i]]，可读性好。如果对极端性能敏感，可以用临时变量：

const tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;

逻辑不变，解构写法在绝大多数现代环境下不会有明显性能问题。

细节四：比较符号。Lomuto 模板里判断用的是arr[j] < pivot，而不是<=。用<=会把大量等于枢轴的元素统一放到左侧，遇到重复较多的数组时，分区会明显失衡。用严格小于时，等于枢轴的元素默认留在右侧，配合整体递归逻辑，正确性没有问题。

3.3 非递归版本：用显式栈替代递归

递归版本在数据量很大且枢轴选择不幸时，可能存在栈溢出的风险。用显式栈模拟递归是一个不错的备选方案，也让面试官看到你对调用栈的理解：

function quicksortIterative(arr) { const stack = [[0, arr.length - 1]]; while (stack.length) { const [low, high] = stack.pop(); if (low >= high) continue; const pivotIndex = partitionLomuto(arr, low, high); stack.push([low, pivotIndex - 1]); stack.push([pivotIndex + 1, high]); } return arr; }

核心逻辑没变，只是把递归调用换成了入栈。这里要注意顺序：先处理哪个区间并不影响最终结果，但如果你希望栈能有序地模拟原递归行为，可以按照“先入后出”的原则控制入栈顺序。普通场景下，先入右区间再入左区间，就能保证先处理左区间，和递归版本的执行顺序一致。

这个版本还有一个额外的控制力：你可以随时调整子区间的入栈条件，比如小于 16 个元素就不再入栈，转用插入排序，为后续优化留了口子。我建议初学阶段至少手写一遍这个非递归版本，写完之后对递归范围的理解会更深一层。

4. 实测过程中踩过的坑与排查思路

4.1 已排序数组把快排变成冒泡：O(n²) 退化

用首元素当枢轴，最经典的反例就是已排好序的数组。我实际测过，在有序数组长度达到一定量级后，递归版本会明显卡顿甚至栈溢出，而随机数组同样长度很快就能排完。

原因在于，每次分区拿到的枢轴都是当前区间的最小值，分区之后左侧为空、右侧长度只减一。递归树从二叉树退化成链表，时间开销从 O(n log n) 涨到 O(n²)，递归深度也跟着到 O(n)。

如何确认是不是触发了退化？两种办法。

一是加一个计数器，在 partition 内部每扫描一个元素就累加，最后看总扫描次数。如果接近n(n-1)/2级别，基本可以断定退化了。

二是打印每次分区返回的索引。如果返回值始终是 low，说明每次只排除一个元素，问题就暴露了。

生产环境里如果对输入没有掌控力，不要直接沿用这个模板。可以先做一次随机洗牌，或者改用随机枢轴，两个方案后面都会提。

4.2 全等元素数组的性能陷阱与边界

全等元素数组是另一个隐蔽的坑。比如[5,5,5,5,5]，用 Lomuto 的arr[j] < pivot逻辑，每个元素都不小于枢轴，分区返回 low，右侧区间只少一个元素。表面上看正确性没问题，但每一层递归都在做差不多的扫描，总体时间依然会退化到 O(n²)。

如果把比较符改成<=，等于枢轴的元素全部跑到左侧，情况会反过来：每轮左侧越来越大，但同样只排除一个枢轴，还是 O(n²)。根因在于，单一的分区逻辑里，等于枢轴的元素没有被平衡地分到两侧。

这个问题更彻底的解法是三向切分（三路快排）：把区间分成“小于枢轴”、“等于枢轴”、“大于枢轴”三段，等于枢轴的部分不参与后续递归。这已经超出首元素枢轴的基础实现范围，但值得知道方向。日常开发中如果数据里重复值很多，再配合首元素枢轴，性能问题会很明显。

4.3 把 Hoare 的递归边界写成 Lomuto 的

我在第一次用 Hoare 分区时，犯了很常见的错误：递归调用写成了(low, j - 1)和(j + 1, high)，导致结果要么漏排元素，要么直接死循环。

原因前面已经提过：Hoare 返回的 j 是左右分区的交界，不是枢轴的最终位置。arr[j] 大概率还在左侧区间里，必须让它继续参与左侧递归。如果你把它排除掉，就会漏排；如果同时又把右侧起点保持 j 不变，区间重叠就会引起栈溢出或死循环。

排查这类问题，我的习惯是在递归入口打印三个参数：low、high、分区返回值。一旦发现某次调用里 low 和 high 始终不变，或者 high 已经小于 low 却还在继续递归，基本就是范围写错。

另外提一个经验：Hoare 分区在递归时，可以加入一个保护判断if (low < high)，确保最小子区间直接返回，不要让其进入循环。虽然大部分实现靠外层条件即可，但多层递归之间出现边界重叠时，这个判断能帮你少踩很多坑。

4.4 不稳定排序：排序对象不仅一个字段时

快速排序是不稳定排序，首元素枢轴并不会改变这个性质。所谓不稳定，是指值相等的元素，排序前后的相对顺序可能发生变化。

举个实际例子。假设有一批订单，先按用户编号排好了序，现在要按金额排序，同时希望相同金额的订单仍然保持用户编号的顺序。用快排按金额排序后，这个要求大概率不成立，因为分区过程中相等的元素会被交换。

如果你遇到需要稳定排序的场景，比如数据库排序的次级排序键，不要直接拿快排硬上。要么用合并排序或插入排序这类稳定排序，要么给相同键的元素附加一个唯一的次级序号，人为拉开差距后再排序。

这个知识点在面试中经常被当作追问点，理解“不稳定”的来源，比背定义更能让你应对自如。

5. 验证、调试与后续优化方向

5.1 写一组简单的测试用例来验证正确性

算法写完不测试等于没写。我通常用一个断言函数，配上一组覆盖不同情况的输入：

function isSorted(arr) { for (let i = 1; i < arr.length; i++) { if (arr[i] < arr[i - 1]) return false; } return true; } function assert(sortedArr, originalArr) { if (sortedArr.length !== originalArr.length || !isSorted(sortedArr)) { throw new Error('排序结果不正确'); } } const cases = [ [], [1], [5, 4, 3, 2, 1], [3, 1, 2, 3, 3, 0], [7, 2, 1, 8, 5, 3, 6, 4], Array.from({ length: 1000 }, () => Math.floor(Math.random() * 1000)), ]; for (const arr of cases) { const copy = [...arr]; quicksort(copy); assert(copy, arr); }

这里我特意在排序前深拷贝数组，因为原地排序会直接修改原数组。如果只断言“排好序”，却拿原数组和排序后数组对比，结果会一直相等，这个测试就是空转。

NaN、undefined 这类特殊值不在今天讨论范围内，但要注意数组里如果混入这些值，快排的比较逻辑会得到不可预期结果，生产代码最好先做数据清洗。

5.2 在首元素枢轴约束下的优化思路

既然标题要求以第一个元素为枢轴，那我默认不改变枢轴选取逻辑。在这个前提下，仍然可以做一些优化来缓解最坏情况。

第一个思路是预处理：排序前先把数组随机洗牌一次。洗牌相当于把“首元素”的确定性打破，让最坏情况变成概率极小的事件。成本是一次 O(n) 的遍历，收益是大幅降低有序输入导致 O(n²) 的风险。

第二个思路是小区间切换：当子数组长度小于 16 时，不再递归，而改用插入排序。插入排序对小规模数组的常数因子非常小，而快排递归的调用开销在那时候可能超过直接比较的开销。

第三个思路是三数取中，但注意它与“首元素枢轴”的约束冲突。如果你能去掉这个约束，三数取中通常是性价比最高的改进：取 low、high、mid 三个位置的中位数作为枢轴，避免最大值或最小值被选中。

如果面试官追问优化，把这些思路讲清楚足够说明你理解了性能瓶颈的位置。如果生产环境允许，我建议优先用随机枢轴加小区间插入排序的组合，这已经是工程上经过验证的稳妥方案。

我个人在这个题目上踩过最大的坑，是把“能运行”当成了“正确”。面对那些只有几行代码的排序题，第一版跑通并不难，难的是在极端输入下依然不崩。以第一个元素为枢轴这个方案，恰好把快排最脆弱的一面暴露了出来，所以我一直觉得它是学习排序算法很好的切入点。如果你把今天讲的 Lomuto 变体和 Hoare 分区的区别、递归边界的来龙去脉都想通了，面试和实际开发里遇到其他排序问题都会顺手很多。

最后再分享一个小技巧：写快排时不要急着敲代码，先在纸上把一个小数组的分区过程跑一遍。这个习惯帮我避免了很多边界错误，尤其是在指针和递归范围上，纸上推演比盯着终端看日志有效得多。