快速排序大概是每个学数据结构的人都会遇到的一道坎面试里也常被拎出来手写。而我见过的初学者里大部分人卡住的不是递归思想本身而是“分区”这一步——到底怎么把一个数组拆成“左边小、右边大”两块。如果只让我用一种方案把这件事讲明白我一定选 Lomuto 方案它是所有分区写法里最好理解、最不容易写错的一种非常适合用来建立对快排的直觉。这篇内容就围绕“理解 Lomuto 方案”展开讲清楚它的扫描逻辑、复杂度来源、工程化改进思路以及那些我见过别人反复踩、自己也踩过的坑。无论你是刚接触排序算法、准备面试手撕代码还是想弄懂经典排序的实现细节这篇文章都能给你一套可以直接上手的参考。1. 排序任务拆解Lomuto 在快排里的角色1.1 分治三步法先立起来快速排序本质上是分治思想的典型应用整个流程浓缩成三步选基准、分区、递归。第一步从待排序区间里挑一个元素叫 pivot基准值。第二步把区间里所有比 pivot 小的元素挪到它左边比 pivot 大的挪到右边这一步叫 partition。第三步对左右两个子区间递归重复上述过程。这里的关键在于partition 执行完之后pivot 已经处在了它最终的位置上。也就是说一次 partition 就能确定一个元素在有序数组里的最终位置剩下的工作只是把左右两边分别排好。很多初学者把注意力的重心放在“递归”上其实递归反而是最好写的部分真正决定快排对不对、快不快的是 partition。这也是我把 Lomuto 单独拎出来讲的原因理解了它快排的整个骨架才算真正立住了。Lomuto 方案的核心思路可以概括为“一趟扫描维护两个区域边界”。它选区间最后一个元素作为 pivot用指针 i 标记小于 pivot 区域的尾部用指针 j 从头往后扫描。扫描过程中遇到比 pivot 小的元素就把它和 i 指向的位置交换然后 i 前进。扫描结束后把 pivot 交换到 i 位置分区完成。这种写法的最大优点是循环不变量非常直观代码极短调试和证明都容易。它特别适合教学场景也适合作为面试时的快速实现模板。1.2 Lomuto 与 Hoare 之争为什么先学 Lomuto说到快排分区很多人会追问那另一套 Hoare 分区方案呢先给结论两种方案都能让快排正确工作但风格差异很大我整理成一张表更方便对比。对比维度Lomuto 方案Hoare 方案基准选择通常取区间最后一个元素通常取区间中间元素附近任意值扫描方式单指针扫描双指针维护边界两个指针从两端向中间移动代码长度很短逻辑直观略长边界条件多交换次数较多包含与 pivot 的最终交换较少平均性能略优绝对最坏情况有序数组 取末尾基准时退化为 O(n²)同样可能退化但稍难触发理解和教学价值极高适合入门适合进阶优化我建议初学者先彻底掌握 Lomuto原因很实际它的循环不变量简单到可以口头证明。你只需要回答一个问题“j 扫过的区域里比 pivot 小的元素是不是都已经放到 i 左边了”答案是肯定的。而 Hoare 分区的循环里有两个相向移动的指针终止条件容易写错往往“跑通一次”和“次次跑对”是两回事。等你用 Lomuto 建立了正确的直觉再去看 Hoare 的代码就会发现它其实是在用“两端指针交换”的方式来减少交换次数。到那时候你缺的只是理解角度而不是逻辑基础。2. Lomuto 分区方案的扫描逻辑与完整实现2.1 双指针的每一次移动意味着什么我们直接用一个具体例子跑一遍 Lomuto 分区数组为 [9, 7, 5, 3, 1]排序区间是 0 到 4。初始状态pivot arr[4] 1i 0j 从 0 开始扫描。j 0arr[0] 99 不小于 pivot继续。j 1arr[1] 77 不小于 pivot继续。j 2arr[2] 55 不小于 pivot继续。j 3arr[3] 33 不小于 pivot继续。j 循环结束此时 i 仍为 0。交换 arr[0] 与 arr[4]数组变为 [1, 7, 5, 3, 9]。这个例子说明一个关键点Lomuto 的 i 指针只有在“发现比 pivot 小的元素”时才会前进。也就是说i 的左侧始终存放着已经发现的小元素而 i 本身指向“下一个小于 pivot 的元素应该放置的位置”。再举一个更复杂的例子[4, 2, 3, 1, 5]pivot arr[4] 5。j 0arr[0] 4 5交换 arr[0] 和 arr[0]自己换自己i 变为 1。j 1arr[1] 2 5交换 arr[1] 和 arr[1]i 变为 2。j 2arr[2] 3 5交换 arr[2] 和 arr[2]i 变为 3。j 3arr[3] 1 5交换 arr[3] 和 arr[3]i 变为 4。循环结束交换 arr[4] 和 arr[4]返回 4。这个例子揭示了 Lomuto 的一个特性如果 pivot 是区间最大值那么分区结果是“整个区间都被视为小于区”最终 pivot 被换到最右边这其实没有真正达到均衡分割的效果反而为退化埋下了伏笔。后面第 3 节我会重点讲退化问题这里先留个印象。2.2 Python 与 C 参考代码逐行说Lomuto 的代码很短Python 实现如下。def lomuto_partition(arr, left, right): pivot arr[right] i left for j in range(left, right): if arr[j] pivot: arr[i], arr[j] arr[j], arr[i] i 1 arr[i], arr[right] arr[right], arr[i] return i def quick_sort(arr, left, right): if left right: return p lomuto_partition(arr, left, right) quick_sort(arr, left, p - 1) quick_sort(arr, p 1, right)逐行解释关键点。pivot arr[right]选了最右端元素作为基准这是 Lomuto 的经典写法。i left表示小于区的起始边界一开始还没有发现任何小于 pivot 的元素所以小于区为空。循环里的for j in range(left, right)注意循环终点是 right 之前因为 right 是 pivot 的位置pivot 本身不参与比较。if arr[j] pivot这里用的是严格小于。为什么不用 后面我会专门讲这里先记住一个结论用能让连续相等元素的场景表现更好避免无意义的交换和更差的分割。交换完成后i 1小于区的边界右移一位。循环结束后arr[i]及其右边的所有元素都不小于 pivot把 pivot 与 arr[i] 交换pivot 就到了最终位置。递归部分需要注意p 已经处于最终位置所以左右区间分别是[left, p-1]和[p1, right]。很多栈溢出 bug 就是这里区间边界写错导致的。再来一份 C 版本方便在不同场景下对照。int lomutoPartition(int arr[], int left, int right) { int pivot arr[right]; int i left; for (int j left; j right; j) { if (arr[j] pivot) { swap(arr[i], arr[j]); i; } } swap(arr[i], arr[right]); return i; } void quickSort(int arr[], int left, int right) { if (left right) return; int p lomutoPartition(arr, left, right); quickSort(arr, left, p - 1); quickSort(arr, p 1, right); }两份代码本质一致。我个人的习惯是面试时先讲清楚循环不变量再写代码写的时候先把 i 和 j 的职责说出来再动手。这样即使不小心写错面试官也能看到思路是清楚的。2.3 分区前后的循环不变量理解 Lomuto本质上是理解一个循环不变量每一轮 j 循环结束后区间[left, i-1]内的所有元素都小于 pivot区间[i, j-1]内的所有元素都不小于 pivot。这个不变量可以用来验证分区逻辑是否正确。假设循环执行到一半j 指向某个位置此时[left, i-1]已经发现的小于 pivot 的元素。[i, j-1]已经扫描过的大于或等于 pivot 的元素。[j, right-1]尚未扫描的区域。rightpivot 本身。如果 arr[j] 小于 pivot就把它和第 i 个位置交换。交换后新的 arr[i] 是那个小元素i 右移于是小于区扩大一位不变量依然成立。如果 arr[j] 不小于 pivot什么都不做j 继续前进那么“不小于区”自然扩大一位同样保持不变量。循环结束后把 pivot 与 arr[i] 交换。此时 arr[i] 原本是不小于 pivot 的值交换后 pivot 左边的全是小于它的元素右边的全是不小于它的元素分区完成。提示如果你在纸上手动模拟几次会发现 Lomuto 的交换经常出现“自己和自己换”的情况也就是i j。这是正常现象不影响正确性只是算法为了避免过度设计而做出的取舍。3. 复杂度、稳定性与退化场景分析3.1 递归式推导最好、平均、最坏快排的时间复杂度取决于每次分区是否能把数组切割得均匀。我们按三种情况分析。最理想情况每次分区都能把区间切成大致相等的两半。此时递推关系近似为 T(n) 2T(n/2) O(n)。根据主定理或递推展开结果为 O(n log n)。这里的 O(n) 来自每层分区需要完整扫描一遍当前区间的所有元素递归深度是 log n 层两者相乘就是 n log n。平均情况对于随机排列的数据分区切割点大致均匀分布复杂度仍然为 O(n log n)。虽然常数项比最好情况大一些但量级不变。这也是快排在工程中被广泛使用的原因期望性能优秀且原地排序节省空间。最坏情况每次分区选的 pivot 恰好是当前区间的最小值或最大值导致一侧子区间为空另一侧大小为 n-1。递推关系退化为 T(n) T(n-1) O(n)累加得到 O(n²)。这个递推式的含义很直观每次只排好一个元素而且还要完整扫一遍数组相当于选择排序的复杂度。空间复杂度方面快排是原地排序不需要额外数组但递归调用需要栈空间。平均递归深度为 O(log n)所以平均空间复杂度为 O(log n)。最坏情况下递归深度为 O(n)空间复杂度也随之退化为 O(n)。这一点经常有人忽略实际上递归栈空间的消耗同样会在最坏场景触发栈溢出。3.2 有序数组是怎么把 Lomuto 拖垮的这是一个值得单独强调的场景输入数组 [1, 2, 3, 4, 5]Lomuto 取最后一个元素 5 作为 pivot。分区过程所有元素都小于 5i 一路从 0 走到 4最后 pivot 与 arr[4] 交换pivot 回到原位置。返回的 p 4左区间是 [0, 3]右区间为空。接下来左区间是 [1, 2, 3, 4]pivot 取 4同样的过程再次发生i 又走到区间末尾。每一轮都只能缩小一个元素整个算法运行了 n 轮每轮扫描长度依次为 n、n-1、n-2……, 总比较次数接近 n²/2实测下来就是 O(n²) 的表现。这种现象的根源在于Lomuto 选取末尾元素作为 pivot而有序数组的末尾元素恰好是最大值这直接命中了最坏情形。如果输入是逆序数组 [5, 4, 3, 2, 1]pivot 是最小值同样会退化。注意这也是为什么很多教材会提醒“不要在已经有序的数据上直接跑经典快排”。工程上解决这个问题的常规思路是随机化 pivot 或者三数取中第 4 节会展开讲。3.3 “不稳定”到底指的是什么快速排序被归类为不稳定的排序算法意思是值相等的元素在排序后可能改变原有的相对顺序。举个例子数组为 [3a, 3b, 2]其中 3a 和 3b 都等于 3只是用来区分先后。Lomuto 分区pivot 取 2j 0arr[0] 3a不小于 2跳过。j 1arr[1] 3b不小于 2跳过。循环结束交换 arr[2]值为 2和 arr[0]值为 3a数组变为 [2, 3b, 3a]。此时 3a 和 3b 的相对顺序已经反转。这就是“不稳定”的直观含义。为什么 Lomuto 会造成这种现象因为分区的交换操作会把“小于区”的元素整体左移而相等的元素不参与交换规则它们的相对位置就可能被跨越。Hoare 分区同样不稳定这是快排的先天特性。如果你需要稳定排序应该选择归并排序或者改用稳定版本的两阶段排序。这个特性在实际工程中很重要。比如你想先按“组别”再按“年龄”排序两次如果第二次排序不稳定第一次排序的结果就会被破坏最终效果可能完全不符合预期。4. 让 Lomuto 扛住实战三个工程化改造4.1 随机化基准值与三数取中针对有序数组退化问题最直接的修复是让 pivot 不再固定取末尾元素。随机化 pivot 的做法是在分区开始前从区间 [left, right] 里随机选一个下标rand_idx把arr[rand_idx]与arr[right]交换然后继续执行原有 Lomuto 逻辑。import random def quick_sort_random(arr, left, right): if left right: return rand_idx random.randint(left, right) arr[rand_idx], arr[right] arr[right], arr[rand_idx] p lomuto_partition(arr, left, right) quick_sort_random(arr, left, p - 1) quick_sort_random(arr, p 1, right)为什么随机化有效因为最坏情况需要一个“恰好选中最大或最小值”的序列而随机选择让这种事件发生的概率变得极低。从期望意义上看任何固定输入都无法稳定地让随机化快排退化所以实际工程中随机化几乎成了标配。另一种经典做法是三数取中取区间首、中、尾三个元素的中位数作为 pivot。这个策略对“基本有序”的数据特别有效因为中位数能保证分割不会太偏。实现上只需在分区前比较三个位置的值把中位数交换到 right 位置。两套方案也可以叠加使用不过通常三数取中已经足够应对绝大多数场景。4.2 小数组切换插入排序快速排序的递归开销在小数组上并不划算。当区间长度很短时插入排序的常数项更小反而更快。很多语言的排序库普遍采用这个优化思路当子区间长度小于某个阈值时改用插入排序。阈值一般取 8 到 20 之间。实现方式是在 quick_sort 入口处加判断def quick_sort_mixed(arr, left, right): if right - left 1 16: for i in range(left 1, right 1): key arr[i] j i - 1 while j left and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key return p lomuto_partition(arr, left, right) quick_sort_mixed(arr, left, p - 1) quick_sort_mixed(arr, p 1, right)这种混合策略看似多写了一段插入排序代码实际收益很可观。对小数组来说省掉的是多次递归调用带来的函数调用开销和栈操作而插入排序本身的复杂度在小规模下完全够用。4.3 尾递归与迭代式快排快排的递归深度在最坏情况下可能达到 O(n)。即使概率很低在极端输入下仍然有栈溢出的风险。尾递归优化的思路是每次递归调用时只对较短的子区间进行递归而将较长子区间留给下一轮循环继续处理。这样可以有效限制递归深度不超过 O(log n)。def quick_sort_tail(arr, left, right): while left right: p lomuto_partition(arr, left, right) if p - left right - p: quick_sort_tail(arr, left, p - 1) left p 1 else: quick_sort_tail(arr, p 1, right) right p - 1这个技巧的精髓在于永远优先递归短的一边长的一边则通过更新边界在循环内继续处理。由于较短区间的长度不超过整个区间的一半递归深度始终受到对数限制。这种写法在 C 这类对栈空间敏感的场景中尤其实用。如果还想彻底避免递归可以手写显式栈来模拟递归过程。从工程角度讲必要性不算高但如果你想彻底理解递归与迭代的关系倒是一个不错的练习。5. 高频 Bug 自查与对拍验证5.1 五个常见错误代码片段与修复Lomuto 代码短但错误极其隐蔽。我整理几个自己见过的高频问题。第一类循环范围写错。有人会把range(left, right)写成range(left, right 1)。这样一来j 会扫到 pivot 本身导致 pivot 被提前交换分区结果完全错乱。记住pivot 不参与扫描循环终点只能是 right。第二类比较符号方向写反。把arr[j] pivot写成arr[j] pivot分区逻辑就变成了“把大的放左边”整体排序顺序反转最终结果会变成降序。这类错误看起来不起眼但会直接导致排序失败。第三类递归区间包含 pivot。分区返回 p 之后pivot 已经就位递归区间应该是[left, p-1]和[p1, right]。如果把p-1写成p会导致同一元素反复参与排序虽然不会立即报错但会带来无用的额外工作严重时还会造成死循环。第四类i 的初始值写成left 1。这会让小于区跳过了第一个位置最终分区结果错位。始终记住i 从 left 开始因为初始时小于区为空。第五类把 pivot 与 arr[i] 交换漏写。循环结束后pivot 仍然在 right 位置而返回的 i 位置并不是 pivot 的最终位置后续递归会乱套。错误类型错误表现修复方式循环范围多扫一位分区结果错乱改用 range(left, right)比较符号反向排序结果变成降序改为 arr[j] pivot递归包含 pivot元素重复参与排序分别传 p-1 与 p1i 初值多 1小于区边界错误确认 i left漏掉最终交换partiotion 无效交换 arr[i] 与 arr[right]5.2 快速验证暴力对拍和边界用例写完快排后只测一个数组远远不够。我建议用“暴力对拍”的思路来验证自己的实现。具体做法写一个最简单的正确排序函数作为基准比如用 Python 内置的sorted()然后生成大量随机数组逐一对比自己的 quick_sort 结果。import random def verify(times500, max_len20): for _ in range(times): n random.randint(0, max_len) arr [random.randint(-50, 50) for _ in range(n)] expected sorted(arr) quick_sort(arr, 0, n - 1) if arr ! expected: print(error:, arr, expected) return False print(all pass) return True这种方法能快速暴露绝大多数实现错误。除了随机数组还要专门测几类极端用例空数组[]应直接返回。单元素[42]应原样返回。全相等数组[5, 5, 5, 5]观察是否会死循环或结果错误。升序和降序数组观察退化情况。含负数和零的数组确保比较逻辑正确。提示全相等数组是最容易被忽略的用例。如果比较符号写成Lomuto 分区会把所有元素都放进小于区依然正确但交换次数明显增加。更推荐用这样在全等数组下分区同样能正常工作。6. 从 Lomuto 延伸到“分区思想”的更多用法6.1 快选无需完整排序的第 K 大理解了 Lomuto 分区后可以顺手掌握一个非常实用的变体快速选择算法用来求无序数组中第 K 小或第 K 大的元素平均时间复杂度 O(n)。核心观察是Lomuto 分区返回的 p 就是 pivot 的最终位置。如果 p 恰好等于目标下标 k那 pivot 就是答案。如果 k 小于 p说明目标在左区间只需对左区间递归。如果 k 大于 p则对右区间递归。def quick_select(arr, left, right, k): if left right: return arr[left] p lomuto_partition(arr, left, right) if p k: return arr[p] elif k p: return quick_select(arr, left, p - 1, k) else: return quick_select(arr, p 1, right, k)注意这里只递归一侧所以期望复杂度从 O(n log n) 降到了 O(n)。这种利用“分区即定位”的思想比先完整排序再取下标的方法效率高得多是面试中常见的进阶考点。6.2 荷兰国旗问题与三分区思想Lomuto 解决的是“二分区”也就是把数组分成“小于 pivot”和“不小于 pivot”两块。但在某些场景下我们需要“三分区”小于、等于、大于。典型例子是荷兰国旗问题给定一个只含 0、1、2 的数组要求原地排序。这个问题完全可以当作“以 1 为 pivot 的三分区”来处理。思路是用三个指针维护边界low 指向 0 区域末尾mid 作为扫描指针high 指向 2 区域开头。这种三分区思想有一个重要优势当数组里有大量重复元素时二分区快排会退化而三分区可以跳过所有等于 pivot 的元素直接递归处理“小于区”和“大于区”从而避免重复扫描相等元素。这也解释了为什么在元素取值范围狭窄的场景三路快排比普通快排更稳定。如果你把 Lomuto 的分区逻辑彻底吃透了看三分区代码会非常轻松因为它们本质上是同一套“指针维护边界”的框架只是区域数量从一个变成两个。我个人在实际写洛慕托方案时最大的体会是别急着追求 Hoare 那样的极致性能先用 Lomuto 把分区的直觉建立起来。你会在手动模拟无数次指针移动之后突然想明白“为什么 i 和 j 要那样配合”。这个想明白的时刻比背熟任何一段代码都重要。以后再遇到任何基于分区的算法你都能用这套“小于区边界指针”的思路迅速理解它的骨架。
