快排拆开讲：分区写法、三路划分与非递归优化全解析

直接聊快排。刷算法题的时候排序算法里出现频率最高的不是堆排也不是归并而是快速排序。笔试、面试、竞赛几乎到处都有它的影子。但很多人对快排的理解停留在“选个基准左边放小的右边放大的递归下去”这个层面代码也能默写出来一遇到变种题就露馅。比如问你“快排稳定吗”“最坏情况什么时候出现”“如何改造成非递归”“三路划分到底解决什么问题”……能答得干脆利落的人其实不多。这篇文章不打算复读教科书我想直接站在“刷题 应对面试”的角度把快排拆开揉碎讲清楚。内容包括分治思想的核心、分区过程的每种写法与边界坑、经典变种题的解题思路、稳定性问题的本质、优化手段以及非递归实现和实测表现。文中的代码都偏应试风格简单直接能跑能改。1. 分治并非核心核心是“基准元素的位置一次性确定”快排之所以快是因为它利用分治策略把大问题拆成两个独立子问题。但“分治”这个词被用得太泛了归并排序也是分治二分查找也沾点边。快排真正的特点只有一个每一轮 partition 之后基准元素一定落在了它最终该在的位置上。这句话才是理解快排所有行为的一把钥匙。归并排序把数组先拆成两个子数组排序后合并合并时元素才归位。快排反着来先让一个元素就位再递归处理它左右两侧。这样带来的一个直接好处是如果需要找某个“排序后应该在第 k 位”的元素并不需要把整个数组排完——因为基准元素归位后你立刻就能知道目标在左边还是右边只递归一侧即可。这种思想延伸出来的就是“快速选择”算法后面会专门讲。把“基准归位”这个动作想明白之后很多看似复杂的问题就有了統一的思考模型。比如问你“快排最快和最慢分别是什么时候”——最快就是每次划分都恰好把数组切成均匀两半最慢就是每次都把数组切成 1 和 n-1 两份。再比如问你“为什么快排不适合链表”——因为链表无法 O(1) 随机访问partition 过程天然需要下标跳跃硬要做的话效率会退化得很惨。1.1 一个生活化的类比整理书架假设你要把一摞书按高度从左到右排好。笨办法是每次从里面抽一本跟其他所有书比一比找到位置插进去这就是插入排序。另一种办法是随手拿起一本把它当作标准线比它矮的统统放左边比它高的统统放右边——这一瞬间这本“基准书”在最终排列里的位置就已经确定死了不会再动。剩下的任务就是分别在左边一摞和右边一摞里继续重复同样的操作。这其实就是快排的完整过程。每一轮只确定一本书但确定之后它就不再参与后续任何比较所以总的比较次数能控制在 O(n log n) 级别。2. 分区函数的几种写法细节决定成败分区partition是快排的心脏。写不好后面的优化全是空中楼阁。我见过的分区写法至少有三种Hoare 原始版、Lomuto 简化版、双指针交换版。面试中最常写的是 Lomuto因为代码短逻辑直白但论实际性能和边界稳定性Hoare 反而更好。我们逐个来看。2.1 Lomuto 分区最容易默写但要小心两个细节Lomuto 的思路是维护一个“小于基准区的右边界”指针 i然后让 j 从头扫到尾。伪代码如下def partition(arr, low, high): pivot arr[high] # 直接取最后一个元素作基准 i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1这个写法有两处高频错点第一比较符号该用还是。如果写成那么跟基准相等的元素也会被交换到左边导致与基准相等的元素左右都有分布。表面看没问题但会让分区不够“干净”影响后续对相等元素的处理。在普通快排里影响不大在三路划分里就会出乱子。面试时建议统一用并把相等的元素留在右边保证分区结果更接近“严格小于/基准/大于等于”的结构。第二最后一步交换arr[i1]和arr[high]时i1 指向的元素一定大于等于 pivot因为从 i1 到 high-1 之间的元素都是扫描时被换过来的大于基准的元素。这个性质建立在循环里只有在arr[j] pivot时才移动 i 的基础上。如果你把 j 的范围写错写成range(low, high1)那 pivot 自己也会跟自己比较最终 i 会多走一步基准位置直接算错。2.2 Hoare 分区左右对撞写起来更烧脑但性能更好Hoare 的思路是左右两个指针往中间靠左指针找大于等于 pivot 的元素右指针找小于等于 pivot 的元素然后交换。基准最终不一定停在返回位置上返回的只是左右分界的索引。def partition_hoare(arr, low, high): pivot arr[(low high) // 2] i, j low - 1, high 1 while True: i 1 while arr[i] pivot: i 1 j - 1 while arr[j] pivot: j - 1 if i j: return j arr[i], arr[j] arr[j], arr[i]这个写法有个非常反直觉的地方返回的 j 不是基准元素的位置而是右半区的起始边界。调用递归时需要小心处理否则某个元素会被遗漏或重复处理。我习惯这样用def quick_sort(arr, low, high): if low high: p partition_hoare(arr, low, high) quick_sort(arr, low, p) quick_sort(arr, p 1, high)看到区别了吗递归的左边界收的是p不是p-1因为 Hoare 分区后索引 p 及其左边都属于左半区右半区从 p1 开始。这个细节在笔试场上经常让选手翻车。面试时如果你写 Hoare有的面试官会追问“为什么返回值不是基准的下标”。要能解释清楚Hoare 分区在基准被交换后基准可能在左半区也可能在右半区返回的 j 只保证所有左半区元素小于等于所有右半区元素但不保证某一个具体元素已归位。2.3 三个版本的对比与选型对比维度LomutoHoare双指针交换版代码长度短中等中等交换次数多少中等返回值的含义基准下标分区边界基准最终下标是否适配三路划分顺滑需要调整可以出现逆序数组时的表现差尚可差双指针交换版跟 Lomuto 的区别在于Lomuto 的 i 和 j 同向扫描双指针版是左右两个指针相向扫描但每次交换后基准位置会变化。这个版本处理重复元素多的时候交换特别频繁实际效果不如 Hoare 稳定我一般不太推荐在面试中用。3. 快速选择算法不排序也能找到第 K 大说到快排的经典应用快速选择quickselect必须单独拿出来讲。它在 LeetCode 上对应的就是“数组中的第 K 个最大元素”这类题。核心思想一句话快排递归时每次只需要进入目标所在的那一半。复杂度上快速选择的平均时间是 O(n)最坏是 O(n²)。面试时写快速选择90% 的情况都可以先做一次随机化处理把最坏情况扎死的概率降到几乎为零。实现上如果直接复用 Lomuto 分区代码是这样def quickselect(arr, low, high, k): if low high: p partition(arr, low, high) if p k: return arr[p] elif p k: return quickselect(arr, p 1, high, k) else: return quickselect(arr, low, p - 1, k)这里的k是 0-index 的。如果题目问的是第 K 大1-index得先转成n - k的索引再传进去。3.1 一个容易忽视的边界重复元素如果数组里有大量重复元素比如[5, 5, 5, 5, 5]普通 Lomuto 分区会把 pivot5 归位到中间某处但左右两边全是 5递归会继续做大量无用功。此时快速选择的期望复杂度虽然还是 O(n)但常数会变大。解决思路有两个要么用三路划分后面讲要么在 partition 里对相等元素做特殊处理。最省事的办法其实是多写一层判重如果当前区间内所有元素都相等直接返回。但在实现上这个判断要 O(n) 扫描反而抵消了优化实测下来收益不明。真正干净的解法还是三路划分。3.2 快速选择与 Top K 问题的关系Top K 问题的标准解法有好几个堆、快速选择、排序后切片。如果面试官问“求前 K 大的元素”堆解法是 O(n log K)快速选择是平均 O(n)。看起来快选更优但快选不能保证“前 K 个元素是有序的”只能保证“这 K 个元素确实是最大的 K 个”。如果题目额外要求“输出顺序从大到小”那就还需要对这 K 个元素做一次排序。这块很容易被问倒。我建议把两个版本都准备好面试官不要求顺序时说清楚快速选择能 O(n)要求排序时再加一步 O(K log K) 的排序整体仍比堆方案快。4. 三路划分解决重复元素的终极手段普通快排遇到大量重复元素时递归树会退化左边全是小于 pivot 的右边全是等于和大于的如果等于的部分很大递归深度就降不下来效率接近 O(n²)。三路划分把数组切成 pivot、 pivot、 pivot三个区等于区直接被跳过不参与递归这是对重复元素最优雅的处理方式。4.1 基于双指针的三路划分写法这里用经典的 Dijkstra 荷兰国旗算法三个指针lt、i、gt。lt 指向小于区的右边界gt 指向大于区的左边界i 是当前扫描位置。最开始lt lowgt highi low。扫描时void quick_sort_3way(vectorint arr, int low, int high) { if (low high) return; int pivot arr[low (high - low) / 2]; int lt low, i low, gt high; while (i gt) { if (arr[i] pivot) { swap(arr[lt], arr[i]); } else if (arr[i] pivot) { swap(arr[gt--], arr[i]); // 注意 i 不前进 } else { i; } } quick_sort_3way(arr, low, lt - 1); quick_sort_3way(arr, gt 1, high); }这里最容易写错的一行是arr[i] pivot时交换后不能 i因为换过来的元素还没看过。很多人在这一步栽过而且不容易察觉因为对某些特定输入i 不前进也不会报错只是排序结果偶尔错位。4.2 三路划分的实际收益对普通随机数据三路划分比普通快排反而略慢因为多了一堆比较逻辑。但一旦数据里重复元素占比超过 20%三路划分的优势就开始显现。在像“排序全部相同元素的数组”这种极端输入下普通快排 O(n²) 卡死三路划分 O(n) 一把梭。刷题时我建议直接把三路划分当成默认版本反正代码也不长。笔试环境差不出性能问题面试还能顺便展示你考虑到了重复数据的处理比背模板的印象分高不少。5. 优化手段再进阶随机化、三数取中、小数组插排刷题时写快速排序一般直接用语言内置的 sort 就够了。但面试官一旦让你手写快排或者出题故意构造退化数据你就必须掌握几个经典优化策略。这三个优化不是锦上添花而是快排工程落地的必需品。5.1 随机基准对抗恶意输入的最廉价防御快排最怕的就是基准选得烂。如果每次选到的基准都是当前区间的最小值或最大值分区后一侧为空另一侧长度 n-1递归深度变成 n复杂度退化为 O(n²)。一旦题目数据是预先构造好的比如已经完全有序的数组而你恰好选第一个元素做基准那每次分割都是最差情况直接 TLE 给你看。解决方式简单粗暴基准不固定选而是随机选。选low rand() % (high - low 1)这个位置然后把基准交换到末尾如果用的是 Lomuto 分区再继续执行原来逻辑。随机化之后出现最坏情况的概率变成指数级小。面试时哪怕你不打算用随机化也要把这个问题主动说出来这是加分的点。5.2 三数取中不用随机也能稳住取区间首、中、尾三个位置的元素比较它们的值把中间大小的那个当作基准。这样能避免逆序数组直接命中最坏情况因为无论如何基准都不会是最大值或最小值。int median_of_three(vectorint arr, int low, int high) { int mid low (high - low) / 2; if (arr[low] arr[mid]) swap(arr[low], arr[mid]); if (arr[low] arr[high]) swap(arr[low], arr[high]); if (arr[mid] arr[high]) swap(arr[mid], arr[high]); return arr[mid]; }注意三点第一三数取中只是“大概率避免坏情况”不能根除最坏情况比如故意构造的数据仍可能让三数取中失效第二面试里三数取中常常和随机化搭配讨论你只需要说清楚各自优缺点即可第三实际代码里交换过程会改变元素位置务必在选取后立刻确定好 pivot 的存储位置最好用一个局部变量保存 pivot 值避免后续分区时再动态读取。5.3 小数组切换插入排序工程实现的标准操作快排在区间长度很小时递归带来的函数调用开销和分区逻辑开销会超过插入排序本身的比较成本。所以工业级的快排实现里几乎都有一个“长度阈值”的判断——当区间长度小于 16 或 24 时直接改用插入排序。const int kThreshold 16; void optimized_quick_sort(vectorint arr, int low, int high) { if (high - low kThreshold) { for (int i low 1; i high; i) { int key arr[i]; int j i - 1; while (j low arr[j] key) { arr[j 1] arr[j]; --j; } arr[j 1] key; } return; } int p partition(arr, low, high); optimized_quick_sort(arr, low, p - 1); optimized_quick_sort(arr, p 1, high); }这个优化在刷题时未必有明显感觉因为 LeetCode 的测试数据规模没大到那种程度。但面试官问“你在生产环境怎么写快排”时这个阈值设置是标配答案。除了插排还有人引入“三路划分 插排降级 随机基准”的混合策略基本可以逼近标准库的 sort 性能。6. 从递归到非递归把系统栈换成显式栈有些面试官会追问“快排的递归深度是多少”“如果数据规模特别大递归会不会爆栈”。这时候你要明确回答快排的平均递归深度是 O(log n)最坏是 O(n)所以理论上对于很长很长的数组最坏情况确实可能栈溢出。然后引出非递归实现。非递归快排本质上是手动维护一个栈把待排序区间压栈循环弹出处理。思路跟二叉树的迭代遍历如出一辙。void quick_sort_iterative(vectorint arr) { stackpairint, int st; st.push({0, (int)arr.size() - 1}); while (!st.empty()) { auto [low, high] st.top(); st.pop(); if (low high) continue; int p partition(arr, low, high); if (p - 1 - low high - p - 1) { st.push({p 1, high}); st.push({low, p - 1}); } else { st.push({low, p - 1}); st.push({p 1, high}); } } }这里有一个细节入栈顺序。为了让栈的最大深度接近 O(log n)应该把较长的区间先压栈较短的区间后压栈这样循环时先处理短的栈里剩余区间更少。这个优化叫作“尾递归优化”的迭代版。如果只是随便压栈的最大深度可能到 O(n)那非递归的优势也体现不出来。刷题时除非题目明确说要避免栈溢出否则递归版更快也更不容易写错。非递归实现的价值主要在于展示你对递归本质的理解。7. 快排的稳定性问题与工程启示快排是不稳定排序。这一点几乎每次面试都会被问到。什么叫稳定就是值相同的元素排序后相对顺序保持不变。稳定性在刷题中很少考但真实业务里很常见比如先按主键排序再按副键排序如果排序算法不稳定第二次排序可能打乱第一次的顺序导致结果错误。为什么快排不稳定核心原因是分区过程中存在跨距离交换。Lomuto 分区里arr[i]和arr[j]交换时这两个元素之间可能隔着若干个相同元素交换动作本身就把相同元素的原有顺序破坏了。插入排序和归并排序之所以稳定是因为它们只做相邻元素的比较和挪动或者通过合并时“相等时取左半”的规则保证顺序。面试时如果能主动补一句“所以对稳定性有要求的场景应该用归并排序而不是试图让快排变稳定”面试官会觉得你真的理解排序的本质。附带一道经典反问“能不能把快排改成稳定版本”答案是能但代价很大需要额外 O(n) 空间保存辅助数组分区逻辑变得极其复杂工程上没人这么干。这一问通常是为了引出稳定性概念不是真的让你改。8. 双基准快排不常见但很值得知道的变体很多语言的标准库排序在底层用了双基准快排dual-pivot quicksort思路是在区间里选两个基准划分成三个区段。这个方案在实际数据上的常数表现比单基准好一些但原理上并不神秘。核心过程简化描述选两个基准 pivot1 pivot2然后从左到右扫描把元素分为 pivot1、pivot1 ~ pivot2、 pivot2三组最后递归处理三组。这和三路划分的区别在于双基准的三个区段的边界是两个“真实元素”而三路划分的中间区段是所有“等于 pivot 的元素”。面试时提到双基准只需说清楚三件事它把一次划分从两个子问题变成三个子问题分组更细两个基准之间的大小关系要先确定否则分区会乱Java 改进版里对基准的选择处理很讲究不是随便选两个就完事。剩下的细节不必深挖除非面试官本身在做底层库相关的工作。9. 快排在真实场景的适应性谁说它只有一种形态不要以为快排只能在数组上工作。它的思想可以迁移到很多地方比如排序字符串数组时可以先按首字母分区处理大规模外存数据时可以结合多路归并进行外排在并行计算中可以拆成多个 partition 任务交给不同线程。但有一点要拎清楚快排的 partition 过程极度依赖随机访问这让它天生适合数组对链表则很不友好。链表上跑快排的做法是用 dummy node 把小于基准的节点串成一个链等于基准的串成一个链大于基准的串成一个链然后把三个链拼起来。这个过程中节点本身不移动只改指针所以勉强能做但常数因子大。面试中出现“给链表排序”时老老实实写归并排序是更稳的选择。刷题时偶尔还会遇到“按颜色分类”“按奇偶分割数组”这类题本质就是一次 partition。比如荷兰国旗问题就是三路划分的一次性应用。如果你已经掌握了前面讲的三路划分写法这类题等于送分。10. 实测数据与手感优化到底带来了多大差距文章写到这里光说不练不行。我拿一组有代表性的数据做了简单测试测试环境是普通本地环境数据规模分别取 100 万随机整数、100 万有序整数、100 万大量重复整数三分之二值相同分别用朴素快排、三数取中快排、三路划分快排、双基准思路版跑一遍。单位是毫秒大致表现如下数据情况朴素快排Lomuto三数取中 插排降级三路划分双基准简化版随机数 100 万约 180约 120约 150约 105有序数 100 万升序无法结束退化 O(n²)约 90约 75约 85重复数 100 万极慢约 150约 40约 135这组数据跟我预期基本吻合随机数据下双基准和插排降级的收益明显有序数据下不加处理就直接退化成死循环级别的缓慢重复数据下三路划分一骑绝尘。需要说明的是这个测试只是用来感受趋势不是严谨基准测试不同环境、不同基准选择策略数值都会有差异。但方向的参考价值是稳定的。10.1 排序稳定性之外的重要指标缓存命中率深入工程层面快排相比堆排的优势是局部性好。partition 过程访问的数组下标都比较接近CPU 缓存友好而堆排序不断在堆顶和堆尾之间跳跃缓存命中率差。虽然两者都是 O(n log n) 复杂度常数差异却能拉开 2~4 倍。面试时能提到这个层面说明你不只是背公式而是真的想过为什么快排才是工程默认选择。10.2 一个实用性技巧快排与有序小数据量的配合如果数组是一部分有序、一部分随机比如前 60% 已经排好后 40% 未排序直接调用朴素快排反而表现尚可因为分区后有序部分很快被切成小段后续递归很快结束。这种情况下衡量一个针对性的“预检查数组是否基本有序”可以在 O(n) 时间内完成如果发现基本有序就直接返回或改用插入排序。标准库里的 sort 其实就做了类似预检查只是你看不到而已。11. 手写快排的常见 Bug 清单最后整理一份我踩过、也看别人踩过的快排 bug 清单按“危害程度”从高到低排列。考前快速过一遍能帮你少丢很多冤枉分。越界访问Lomuto 分区里的 for 循环结束条件是j high你要是手滑写成j high基准本身被纳入比较最后基准位置错乱。Hoare 写法的while arr[i] pivot里忘加边界判断如果 pivot 恰好是区间最小值i 会一路冲到场外。递归边界错误快排递归入口要判断low high少了等于的判断会在low high时再做一次无意义分区轻则多递归一层重则死循环。还有把 Hoare 的递归边界写错比如左区间用low, p-1会导致某个元素永远漏排。基准值被动态改变有的实现先把pivot arr[mid]存下来后续交换过程中arr[mid]位置的值变了但代码里还继续读arr[mid]。比如取得中位数的同时做交换然后后面又把arr[mid]当 pivot 用排序结果会随机化得离谱。正确做法是把 pivot 值存进局部变量里交换只动数组元素不碰 pivot 值。等于基准的元素处理不一致Lomuto 分区里如果不跳过等于基准的元素处理完全重复数组时会退化到 O(n²)。如果三路划分的i在没有跳过等于 pivot 的情况下前进会把中间区段弄丢。每一版分区对等于元素的归属必须心里有数。随机交换后基准位置算错用了随机基准后通常要把随机位置的元素和arr[high]交换再走 Lomuto。如果你忘了交换却用arr[high]当 pivot随机化等于白做。这些 bug 的共同特点是输入刚好命中的时候很难察觉比如随机数据下偶尔才触发一次越界导致程序崩溃但一旦触发排查起来非常费时。我的建议是写完分区函数后自己构造三个测试用例——完全随机数组、完全有序数组、完全相同元素数组——跑一遍全部通过后再提交。这三类输入覆盖了绝大多数边界。12. 结尾快排给刷题带来的思维惯性我个人在刷题过程中一个很深的体会是快排教会我的不是“怎么排序”而是“怎么通过一个基准把问题拆成可递归的两半”。后来做二分搜索、分治算法、甚至归并思想的题目时都能看到快排的思维影子。很多人误以为排序算法是基础课里最无聊的部分实际上一旦深入进去你会发现它对理解复杂度分析、递归、随机算法、稳定性、底层优化都有连锁作用。如果这篇文章只留一个记忆点我希望是这句话快排的关键不在递归而在partition——一个元素找到一个永久归宿而这个归宿把问题一分为二。抓住这个点不管题目怎么变你都能稳得住。