快速排序面试必考：首元素枢轴的Lomuto与Hoare分区详解-北京尧图网络

面试手写排序算法时快速排序几乎是必考项。但很多人写出来的代码在小数组或已经有序时能跑一上强度就翻车。今天要聊的这个版本——以第一个元素为枢轴的快速排序——正是最常见也最容易写错的一个变体。之所以拿它开刀是因为枢轴选在哪个位置直接影响分区的写法、递归边界和性能表现把这些细节想清楚其他任何快排变体基本都能一眼看懂。这篇文章会把两种主流的原地分区思路都拆开讲配上能直接跑的代码和踩坑记录用实际推演帮你理解每一步交换到底在干什么。适合正在刷算法题、准备面试或者工作中需要手写排序逻辑的同学参考。1. 快速排序为什么值得再写一遍以及第一个元素当枢轴到底意味着什么1.1 一个快速排序的完整流程是什么样子快速排序干的事可以概括成三步选一个枢轴元素。分区把小于枢轴和大于枢轴的元素大致分到两边。递归对左右两边的区间重复执行。用整理扑克牌打比方你从中间抽出一张牌当基准剩余牌里比它小的放左边比它大的放右边然后再把左边和右边各自重复这套操作直到每个区间只剩一张牌。这里有两个关键点需要记住。第一分区完成后枢轴落到了“左小右大”的分界线上所以它的最终位置已经确定后面不再参与排序。第二递归处理的是“左侧区间”和“右侧区间”不包括已经归位的枢轴。“大致分到两边”这几个字很值得琢磨。分区并不要求两边完全有序只保证大小关系正确。快排之所以快靠的是每轮分区都能把问题规模大致砍半递归深度保持在 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 交换少、性能更好但指针和递归边界都比较绕。我给一个对比表对比维度Lomuto 变体Hoare 分区实现难度低中交换次数偏多少返回位置的含义枢轴最终位置左右分区交界递归边界写法(low, idx-1)、(idx1, high)(low, j)、(j1, high)相等元素敏感度较敏感相对均衡实际工程里很多人会混合使用主体排序用 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]low0、high7pivot7v0j1arr[1]27成立v1此刻 v 与 j 相等不需要交换数组不变。j2arr[2]17成立v2v 与 j 相等不需要交换数组不变。j3arr[3]87不成立。j4arr[4]57成立v3交换 arr[3] 和 arr[4]数组变为[7,2,1,5,8,3,6,4]。j5arr[5]37成立v4交换 arr[4] 和 arr[5]数组变为[7,2,1,5,3,8,6,4]。j6arr[6]67成立v5交换 arr[5] 和 arr[6]数组变为[7,2,1,5,3,6,8,4]。j7arr[7]47成立v6交换 arr[6] 和 arr[7]数组变为[7,2,1,5,3,6,4,8]。循环结束交换 arr[0] 和 arr[6]得到[4,2,1,5,3,6,7,8]返回 v6。此时 7 已经落到索引 6它的左边全小于它右边全大于它。接下来递归处理[0, 5]和[7, 7]右侧只有一个元素直接返回左侧继续重复同样的过程。手动推演的意义在于当你调试时对某一轮交换结果有疑问心里有一套“v 维护左边界j 负责扫描”的心智模型而不是死记硬背代码。3.2 几个容易被忽略的细节细节一空数组和单元素数组。默认参数high arr.length - 1在空数组时得到 -1low0 与 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 分区的区别、递归边界的来龙去脉都想通了面试和实际开发里遇到其他排序问题都会顺手很多。最后再分享一个小技巧写快排时不要急着敲代码先在纸上把一个小数组的分区过程跑一遍。这个习惯帮我避免了很多边界错误尤其是在指针和递归范围上纸上推演比盯着终端看日志有效得多。

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

相关推荐

前端选项卡与折叠面板：从交互语义到组件化封装完整指南

用ByteBuddy动态代理实现第三方SDK调用日志拦截与可观测性增强

MPC轨迹跟踪实战：从原理推导到参数调优的完整指南

更多资讯

Skills项目：将技能封装为可执行单元，实现能力复用与编排

上下文模式实战：告别参数透传，优雅管理多场景代码

BEVFormer中英文对照精读：从网格查询到空间与时序注意力

REA事件建模实战：用Resource-Event-Agent重构订单与库存系统

银河麒麟上装达梦和人大金仓，踩过的坑都在这

人脸灰度图像彩色复原：从原理到工程实践的深度学习方案

今日更新

智能硬件视频会议集成：从芯片选型到场景落地的全栈实践

FFmpeg音视频处理与5路RTMP推流实战：从原理到118克盒子部署

RK3528+1GB内存如何变身直播节点？硬编解码与六协议实战复盘

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？