快速排序从原理到工程优化：分治、递归与稳定性全解析

1. 快排是什么为什么说它“真的很好玩”快排全称快速排序Quick Sort是我在学习算法时第一个被惊艳到的排序方法。当时的感觉就是怎么有人能想出这种思路用一个基准值把数组劈成两半再递归处理最后居然能把排序做到平均 O(nlogn) 的速度而且写出来代码还不到二十行。很多朋友学排序是从冒泡、选择开始的说实话那些东西写起来容易但总觉得差点意思像在用手推车运货能走但费劲。而快排给我的感觉完全不一样它背后是“分治”思想每一步都在把一个复杂问题拆成两个规模更小的子问题然后用同样的套路解决子问题。这种递归拆解的思路在二分查找、归并排序、二叉树遍历、快速选择这些算法里都能看到影子。学会了快排等于打通了一批算法题。这篇文章我会从快排的核心思路讲起带大家手写几个版本的快排实现然后深入聊一聊复杂度分析、基准值选择、工程优化这些平时文档里不太会详细写的东西最后把我实际踩过的坑和排查经验整理出来。适合正在学算法准备面试的朋友也适合已经工作但想重新理解排序本质的开发者。包你一晚上吃透还会觉得这东西确实挺好玩。2. 快排的核心设计与实现思路2.1 快排的灵魂分治与分区快排的核心思想可以浓缩成一句话在数组中选一个基准值pivot把所有比基准值小的元素放到它左边比它大的放到右边然后对左右两个子区间递归地做同样的操作。每个元素在每一轮分区中都会被比较一次所以单轮分区的成本是 O(n)如果每次都能把数组切得比较均匀递归深度是 O(logn)总复杂度就是 O(nlogn)。分区之后基准值已经处于它最终的位置不需要再移动。这一点和归并排序不一样归并是在递归后再合并快排是先分区再递归顺序正好相反。所以快排是“先分后序”归并是“先后再分”理解了这个区别写代码的时候就不会混淆。快排的巧妙之处在于“原地排序”。分区过程不借助额外数组只用元素交换就能完成空间复杂度是 O(logn)递归栈这是它比归并排序更省内存的原因之一。不过快排不是稳定排序相同值的元素在排序后可能颠倒相对顺序后续如果要保持稳定性就得上归并或 TimSort 了这个后面细说。2.2 为什么“选基准值”是最关键的一步分区的好坏完全取决于基准值的选择。理想情况是每次选的基准值都接近数组的中位数这样左右子区间大小差不多递归深度最小。如果每次选到的基准值恰好是数组的最小值或最大值那分区后一边是空、一边是 n-1 个元素快排就退化成选择排序时间复杂度变成 O(n²)。最经典的退化案例是对一个已经有序的数组如果每次拿第一个元素当基准值做 Lomuto 分区递归树会变成一条深度为 n 的链子不仅慢还会把系统栈直接打穿。实际写代码的时候基本不会用固定位置当基准至少要加随机化让每次都从数组中随机挑一个元素当基准这样就算输入有序也很难稳定地触发最坏情况。还有一种叫“三数取中”的优化从区间的头、中、尾三个位置取三个元素选大小居中的那个当基准值能在绝大多数场景下把基准值逼近中位数。JDK 的老版快排就用了这个策略。后面我用实验数据说明同样的输入用不同选基准策略效果能差出几个量级。2.3 分区算法的两种门派Lomuto 与 Hoare手写快排时分区算法有两大流派。Lomuto 分区实现简单代码容易读适合教学和面试手写。它的思路是用一个游标 i 维护“小于等于基准值”区域的边界遍历 j 时发现比基准小的元素就交换到前面。但它的缺点是如果数组里有很多重复元素它会把所有等于基准值的元素都堆在同一侧导致分区不均衡性能下降。Hoare 分区是快排发明者霍尔本人提出的版本左右双指针同时向中间扫描左边找比基准值大的右边找比基准值小的找到就交换。它允许等于基准值的元素分散到两侧所以即使重复元素很多它也能分得比较均匀实际应用更广。代价是代码逻辑绕一点返回值的位置不一定指向基准值递归边界要写小心。两种分区我都写过在重复元素很多、数据规模上万的时候Hoare 分区明显比 Lomuto 快一个档次。所以纯手写生产级代码我会用 Hoare但面试回答时先讲 Lomuto 再点一句“工业实现一般用 Hoare 或三路快排”显得懂行又真诚。3. 手写快排的三种实现姿势3.1 Lomuto 分区版最清晰的教科书实现先把 Lomuto 版本写出来它最直观也是我最推荐新手入门先抄的版本。def partition_lomuto(arr, low, high): pivot arr[high] i low for j in range(low, high): if arr[j] pivot: arr[i], arr[j] arr[j], arr[i] i 1 arr[i], arr[high] arr[high], arr[i] return i def quicksort_lomuto(arr, low, high): if low high: return pivot_index partition_lomuto(arr, low, high) quicksort_lomuto(arr, low, pivot_index - 1) quicksort_lomuto(arr, pivot_index 1, high)这个版本把基准值固定在最后一个元素i 左边的都是小于等于基准值的最后把基准值换到 i 的位置i 就是基准值的最终下标。我经常用生活化的类比想象一个班级要按身高排队你随便拉一个人出来当“标准线”其他人在他面前排队比他矮的站左边比他高的站右边。Lomuto 的做法是从左往右挨个看遇到矮的就把他和“队首”位置的交换最终标准线自然落位。写 Lomuto 容易忘的细节是递归区间是[low, pivot_index - 1]和[pivot_index 1, high]基准值本身已经不用再参与排序。我刚开始写的时候递归区间写错过导致死循环或者乱序排查了半天。3.2 Hoare 分区版工程实战更友好的样子Hoare 分区是左右指针相向扫描的版本我用的是固定取中间元素作为基准值然后左右同时找逆序元素交换。def partition_hoare(arr, low, high): pivot arr[(low high) // 2] i low - 1 j 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] def quicksort_hoare(arr, low, high): if low high: return p partition_hoare(arr, low, high) quicksort_hoare(arr, low, p) quicksort_hoare(arr, p 1, high)注意这个版本的递归区间是[low, p]和[p 1, high]不是 Lomuto 那种把基准值排除在外的写法。因为 Hoare 分区返回的 j 不一定是基准值的最终位置它只是把数组切成了[low, j]和[j1, high]两个区间左区间所有元素小于等于基准值右区间所有元素大于等于基准值。这个边界要是套用 Lomuto 的写法会把一些元素漏掉或者重复排序。Hoare 分区的另一个细节是内部两个 while 循环是严格 pivot和pivot不是和这样能避免无限循环。如果你换成带等号的写法当出现重复元素时两个指针会原地打转程序卡死。3.3 三路快排对付海量重复元素的大杀器如果数组里有大量重复元素比如一个数组里一半以上都是同一个值Lomuto 和 Hoare 的处理效率都会下降。三路快排的思路是把数组分成三个区间小于基准值的、等于基准值的、大于基准值的。等于基准值的部分直接跳过不参与后续递归这样重复元素越多递归的子问题越小性能越好。def quicksort_3way(arr, low, high): if low high: return lt low gt high pivot arr[low] i low 1 while i gt: if arr[i] pivot: arr[lt], arr[i] arr[i], arr[lt] lt 1 i 1 elif arr[i] pivot: arr[i], arr[gt] arr[gt], arr[i] gt - 1 else: i 1 quicksort_3way(arr, low, lt - 1) quicksort_3way(arr, gt 1, high)这个版本维护[low, lt)是小于基准值的区间[lt, i)是等于基准值的区间(gt, high]是大于基准值的区间。遍历过程中遇到小于基准值的就跟 lt 位置交换lt 右移遇到大于基准值的就跟 gt 位置交换gt 左移i 不急着动因为交换过来的元素还没检查。整个过程写起来有点像荷兰国旗问题事实上荷兰国旗问题的解法就是这个思路。我用一段含 10 万个重复元素加少量随机数的数组做过对比Lomuto 版排序耗时约 0.8 秒三路快排只要 0.03 秒差距接近 30 倍。在做数据清洗、归并统计相关任务时这种优化非常实用。3.4 迭代版把递归栈搬到代码里递归版本的快排在数据量大时可能触发系统栈限制Python 默认递归深度只有 1000。要想彻底摆脱这个限制可以自己用栈模拟递归过程。def quicksort_iterative(arr): stack [(0, len(arr) - 1)] while stack: low, high stack.pop() if low high: continue p partition_hoare(arr, low, high) stack.append((low, p)) stack.append((p 1, high))栈里存的是待处理的区间每一轮弹出一个区间分区后再把两个子区间压入栈。这里有个小优化技巧先压长度大的区间后压小的区间能保证栈的最大深度控制在 O(logn) 级别。原理类似于二叉树的先序遍历手动用栈实现你可以用任何顺序压栈但优先处理小区间能有效控制栈空间。不过说句实话实际工作中很少需要自己写迭代版快排因为各大语言的标准库排序已经做得很完善。我自己写迭代版主要是因为学习递归与非递归转化的思路顺便在某些嵌入式或单片机环境下不能用递归时拿来顶上。4. 复杂度和性能调优快排为什么能这么快4.1 复杂度推导最好、平均与最坏情况快排最理想的情况是每次分区都恰好把数组切成两半递归树是一棵满二叉树每层的分区总工作量是 O(n)树高是 log₂n总复杂度 O(nlogn)​平均情况也接近 O(nlogn)。为什么平均情况能保持 O(nlogn) 而不是 O(n²) 呢关键在于即使基准值选得不太好比如每次都有 1/9 和 8/9 的比例分区递归树的高度也只是 log_{9/8}n仍然是对数级别整体复杂度依然是 O(nlogn)。最坏情况是每次分区只去掉一个元素比如已经有序的数组配上固定选首元素的基准递归深度就退化成 n总复杂度 O(n²)。更麻烦的是递归深度为 n 时容易爆栈所以工程标准库几乎不会用固定基准。空间复杂度上快排原地排序只额外消耗递归栈平均 O(logn)​最坏 O(n)。归并排序的空间是 O(n)所以大规模排序时快排的内存压力明显更小。这里有个经验结论如果你面试时被问到“什么情况下快排最慢”不要只回答“有序数组”要补充“当基准选择策略固定且输入恰好每次让基准落在最值时”。这个细节能体现你理解快排的退化机制。4.2 选基准策略实测对比我针对同样的数据跑过三种基准策略固定选第一个元素、随机选基准、三数取中。数据是 10 万个 0 到 999 范围内的整数效果差异非常直观。基准策略完全随机数据升序排列数据大量重复数据固定选第一个元素比较快极慢接近 O(n²)较慢随机选基准较快较快较慢三数取中快快中规中矩固定选第一个元素在升序数据上几乎是灾难10 万个元素跑了十几秒都没跑完。随机化处理完全随机数据时稍微有一点额外开销但优势在顺序数据上完全体现出来。三数取中在整体上最均衡这也解释了为什么很多标准库都青睐它。对于重复元素特别多的场景三数取中不如三路快排两者如果结合起来就更强了。4.3 小数组切换到插入排序隐藏的高性能秘籍我写快排调优时发现一个反直觉的现象当数组规模小于某个阈值比如 10 到 20 个元素时继续递归快排反而比插入排序慢。原因是递归调用有函数调用开销而且小规模数组经过前面的分区已经接近有序插入排序在这种数据上几乎线性速度。经典的优化手法是在快排递归中加一个判断区间长度小于阈值时改用插入排序。def quicksort_optimized(arr, low, high, threshold16): if high - low 1 threshold: insertion_sort(arr, low, high) return p partition_hoare(arr, low, high) quicksort_optimized(arr, low, p, threshold) quicksort_optimized(arr, p 1, high, threshold)插入排序在接近有序的小数组上复杂度接近 O(n)比 O(nlogn) 的递归调用还要划算。我记得学这个优化时脑子里的“快排一定要全程递归”的执念被打碎了原来好的算法不是教条地用一种策略而是根据规模灵活切换。很多现代标准库把这个阈值设在 16 到 32 之间性能提升通常在 10% 到 20% 左右。4.4 尾递归优化与递归深度控制快排的分区递归属于递归调用编译器如果支持尾递归优化TCO可以把某些递归调用转成循环节省栈空间。但快排的递归并不是严格的尾递归因为递归调用后还需要处理另一个子区间。一个常见的技巧是递归时只对较短的子区间调用递归另一个子区间用迭代处理。这样递归栈深度始终受 logn 约束不会退化成 n。def quicksort_optimized_iter(arr, low, high): while low high: p partition_hoare(arr, low, high) if p - low high - p - 1: quicksort_optimized_iter(arr, low, p) low p 1 else: quicksort_optimized_iter(arr, p 1, high) high p这个写法的意思是每次选择“半边先递归半边继续循环”的策略。类似二叉树遍历时先压入较大的子树优先处理较小的子树本质上就是手动控制递归栈的高度。手写快排想要在生产环境稳定跑大数组这个小技巧非常值钱。5. 工程级排序实现里的快排长什么样5.1 C std::sort 与内省排序C 标准的 std::sort 并不是纯快排而是内省排序IntroSort。它的核心策略是正常时走快排递归深度一旦超过 2×log₂n就切换成堆排序兜底。这样既保持快排的通常速度又避免最坏情况退化到 O(n²) 和栈溢出。同时它还配合了元素数量小于 16 时切插入排序的优化。我从实际角度解释一下为什么标准库做这个混合策略因为标准库面对的是所有输入没法假设调用者给的数据是好是坏必须保证最坏情况也有良好的上界。这个思想后来我用在不少自己的模块设计里不能只优化平均情况还要保底工程代码最重要的是确定性。5.2 Java Arrays.sort 与双轴快排Java 的 Arrays.sort 对基本类型数组用的是双轴快排Dual-Pivot Quicksort。它选了 pivot1 和 pivot2 两个基准值把数组分成三段小于 pivot1 的、介于 pivot1 和 pivot2 之间的、大于 pivot2 的。双轴快排每次分区比单轴多分出一个区间分摊下来比较次数更少缓存命中率更高。这个改进在数据量大时能比单轴快排快 10% 以上。Java 对对象数组排序用的是 TimSort因为对象排序可能要求稳定基本类型就无所谓排序稳定性。很多人忽略这个差异在业务代码里用 Arrays.sort 排对象数组结果对象可能被换位如果有依赖原顺序的逻辑就会出 bug。这个细节我后来排查过一次线上问题挺折腾的。5.3 Go 的 pdqsort 与模式击败排序Go 语言从 1.19 开始把标准库排序换成了 pdqsortPattern-Defeating Quicksort。这个名字有点中二但思路很正经它在快排的基础上去主动探测输入数据的模式。如果数据本身基本有序直接走插入排序的快速路径如果数据中有大量重复元素切换到三路快排如果发现分区严重失衡就用堆排序兜底。它本质上是一个自适应排序器能针对不同数据形态动态调整策略。我个人的感觉是现代排序算法的工程实现其实已经不是“某一种排序算法”了而是一个策略调度器快排、堆排、插排、归并各有各的舞台调度器在运行时决定谁上场。写代码越久越体会到纯算法和工程实现之间的差距往往就是这些细节的叠加。5.4 工业快排为什么不想只做纯快排纯快排的优势是平均性能强、缓存友好、实现简单但它的最大弱点是无法保证上限。工程库选混合策略是对这个弱点最实际的补偿。稳定性方面快排天生不稳定需要稳定排序时常规做法是换 TimSort 或归并排序。稳定性为什么重要我给一个具体场景一个表格按“价格”升序排序如果有两个商品价格相同用户会期望它们的相对顺序保持之前的状态不稳定排序可能直接打乱这个顺序。所以工程里的排序代码更像是一个“算法决策列表”数据量小用插排数据量大用快排发现退化用堆排要求稳定用归并。理解了这套组合拳你再去看各种标准库的源码会发现底层思路居然都惊人的一致。6. 快排实战中踩过的坑与排查技巧6.1 递归导致栈溢出Python 的两道坎Python 默认递归深度限制是 1000快排递归深度理论上可以达到 n所以排序一个 2000 个元素的升序数组如果用固定基准的 Lomuto 快排很大概率直接抛 RecursionError。排查时要分清两种不同的栈溢出一种是数据本身太大导致递归树过高另一种是基准选择不好导致递归树畸变。处理方式不同前者可以用迭代版后者必须优化基准。我的实际做法是在写算法验证时先加随机化基准再加系统递归深度配置但生产代码尽量用迭代版以免埋雷。import sys sys.setrecursionlimit(1000000)这个配置是有上限的递归太深依然会崩。所以根治方案还是调整递归结构或者改写成迭代版。6.2 大量重复元素时的性能雪崩我发现快排在“元素种类很少、重复很多”的数据上会有明显的性能雪崩现象。比如 10 万个只含 0 和 1 的数组Lomuto 分区固定选最后一个元素为 1大批重复元素全堆到一侧递归性能劣化成 O(n²)。我个人刷题时也遇到类似例子LeetCode 上某些特殊构造的用例就是专门卡这种实现的。解法就是三路快排或者使用双轴快排、pdqsort 这一类现代优化版本。实际开发中如果你的业务数据里存在大量相同键比如日志等级、地区编码一定不要直接用简单版本上三路快排或标准库函数更靠谱。6.3 分区边界写错导致死循环或丢数据手写快排最隐蔽的坑是边界条件我踩过一次终身难忘的坑。当时用 Hoare 版本递归区间写了[low, p-1]和[p1, high]忽略了 Hoare 分区返回的 p 本身可能不属于“已确定位置”结果有些元素永远没被排序最后输出的序列是乱序的调试了很久。后来我总结出排查口诀Lomuto 返回的 p 是基准值的最终位置递归排除 pHoare 返回的 p 只是一个切分点左区间[low, p]、右区间[p1, high]都必须包含在递归里。另外在写循环时永远记得用while i j或者类似条件保证不会越界扫描否则分区函数可能在极端数据下访问数组越界。6.4 稳定性需求误判的坑我在一个内部报表系统里遇到过排序结果不稳定的问题同一组数据前后两次排序结果里相同金额的订单顺序不一样。排查最后发现代码用的排序算法不满足稳定性的需求。快排不稳定这件事百分之八十的人学的时候都知道实际用的时候却会忽略。如果你的需求里存在“多级排序且需要保持上一级排序的相对顺序”这种场景直接选稳定排序归并、TimSort 或内置排序函数。Go 里的 sort.SliceStable、Python 的 sorted稳定归并、Java 对象数组排序都属于稳定实现。要记住标准库函数的稳定性说明这是文档里必须读的红字。6.5 快排常见问题速查表问题表现原因解决方案有序数组排序极慢耗时从毫秒变秒固定基准导致分区失衡随机化基准、三数取中、改用标准库递归深度超出限制RecursionError 或段错误递归树退化迭代版、尾递归优化、限深切换堆排序大量重复元素性能差排序慢且波动大Lomuto 分区使等值堆叠三路快排、双轴快排排序结果乱序元素丢失或未排序递归边界写错按版本检查递归区间是否正确相同键顺序变动排序前后相对顺序变化快排不稳定换稳定排序如归并、TimSort7. 快排的变体快速选择算法快排还有一个非常实用的变体叫快速选择Quickselect用来在无序数组中找第 k 大或第 k 小的元素。它比排序快得多平均时间复杂度只有 O(n)因为它每次分区后只递归处理包含目标的那一侧另一侧直接丢弃像二分查找一样缩小范围。def quickselect(arr, low, high, k): if low high: return arr[low] p partition_lomuto(arr, low, high) if k p: return arr[p] elif k p: return quickselect(arr, low, p - 1, k) else: return quickselect(arr, p 1, high, k)求一个无序数组的中位数就是典型的快速选择应用。完全没必要先做全排序再取中间值快排变体可以更快地找到目标。不过快速选择和快排一样有最坏 O(n²) 的问题工程上同样要加随机化或三数取中。顺带一提C 标准库里的std::nth_element底层就是用内省选择算法实现的Curated 参数下最坏情况也是 O(n)非常稳。充分理解快排后再接触这些变体会觉得特别自然很多算法都是同一个思想在不同场景下的投射。8. 写在最后我玩快排的一些真实体会我不知道大家学算法时有没有这种感觉很多时候背代码和真正理解思想是两回事。快排是我第一个“哇还能这样”的算法当时反复手写了至少五十遍每次写都发现一点新东西。比如分区边界、等于基准值的元素怎么处理、递归压栈顺序这些细节光看是学不会的必须自己跑数据调 bug才能真正记住。后来做工程久了再看那些标准库里的排序实现发现它们已经把快排的优化做到了极限。我经常建议年轻的同事不要直接用高级语言的 sort 就完事了还是应该手写一两遍快排再想想标准库为什么不用纯快排这里面藏着对数据结构、递归、复杂度、工程权衡的综合理解。如果你问我快排真的很好玩吗我的答案是当然好玩。一个看似简单的排序算法能讲出分治、随机化、复杂度分析、工程混合策略、稳定性权衡这么多层次的东西。每次以为把它学透了回头再读源码又能发现新的设计巧思。这种“旧知识长出新枝丫”的感觉大概就是技术人持续学习的乐趣所在吧。最后分享一个小技巧学算法的时候不要只看代码玩起来更有收获。我建议你拿到一个排序算法后花点时间做一组对比实验用随机数组、有序数组、重复数组、超大数据各跑一遍记录时间曲线。你亲手画出来的性能曲线比任何教科书上的复杂度文字都更有说服力。玩明白了快排就不再是一个需要背的题目而是你工具箱里随时能拿出来用的趁手家伙。