快速排序是数据结构课程里“性价比”很高的一个算法代码量不大思想深刻实际表现又强面试和项目里都常碰。但很多新手学到“快速排序”往往只学到外壳一旦要自己写或者要把它用到工程里各种边界问题就全冒出来了基准值选在头上导致有序数组直接退化、递归太深爆栈、重复数据多的时候快排慢成渣、排序后相对顺序乱了才发现不稳定带来的麻烦。这篇文章我想根据自己的实践把快速排序从原理到经典优化完整梳理一遍包括分区到底怎么写、基准值怎么选、什么时候切换成插入排序、重复元素多了怎么处理、递归爆栈怎么办、非递归怎么写。适合三类人看刚学完基础还没自己完整实现过一遍的初学者准备面试想理顺细节的人以及工作中需要手写排序但又不想直接抄内置函数的工程师。1. 快速排序的核心思想与基础实现1.1 先理解分治排序问题如何被拆解快速排序用的分治思路一句话概括就是选一个基准值把数组拆成“比基准小的一堆”和“比基准大的一堆”然后对这两堆分别做同样的操作直到每个子区间只剩一个元素或空区间。这个思路听起来简单但和归并排序有本质区别。归并排序是“先拆到底再边合并边排序”真正让数据有序的动作发生在归并阶段也就是说它在合并时要额外申请临时数组。快速排序则相反它在拆解阶段就通过“分区”把元素放到了正确的一侧而基准值也被放到了最终位置等到递归完成时数组已经原地有序不需要额外的合并步骤。这就是为什么快速排序可以做到 O(1) 的额外辅助空间忽略递归栈归并排序却要 O(n) 的空间。把这个拆解动作做得越干净后续递归承担的任务就越少。分区之后左子区间里的所有元素都小于基准值右子区间里的所有元素都大于基准值基准值不用再参与排序。问题规模从 n 变成了两个约 n/2 的子问题这就是高性能的来源。实际写代码的时候很多人会忽略一个重要细节分区的返回值到底指向哪里递归边界该怎么设。不同分区方法返回的索引含义不一样递归区间也跟着变这一步如果不搞清楚后面写出来的代码不是在边界上死循环就是把某个元素漏掉。后面第 2 节我会专门讲这个坑。1.2 基准元素与分区过程分区是整个快速排序的核心也是所有优化手段的落脚点。我自己初学时的感受是递归那部分只要理解了写出来并不难真正容易出问题的全在 partition 函数里。常见的基础实现有两种写法。第一种是“单向扫描”方式思路很好懂选最后一个元素当基准维护一个“已处理区”从左往右扫遇到小于等于基准的元素就把它交换到已处理区末尾扫描结束后把基准放到已处理区后面。这种写法交换次数比较清晰但等号处的细节很容易踩坑。第二种是“双向扫描”方式效率更高也更接近工程实现左右各一个指针左指针找大于等于基准的元素右指针找小于等于基准的元素找到就交换直到两个指针交错。单次交换能让两个元素同时归位所以比较和交换次数更少。双向扫描的等号处细节也一样重要处理不好会导致基准被挪来挪去甚至出现某个子区间为空的情况。我强烈建议初学者把这两种分区都各写一遍然后跑各种极端数据对比。分区没写对后面所有优化都是在错误的地基上盖楼。1.3 基础版递归实现先用最容易理解的单向扫描方式写一版语言我用 Python 演示。def quicksort(nums, left, right): if left right: return p partition(nums, left, right) quicksort(nums, left, p - 1) quicksort(nums, p 1, right) def partition(nums, left, right): pivot nums[right] i left - 1 for j in range(left, right): if nums[j] pivot: i 1 nums[i], nums[j] nums[j], nums[i] nums[i 1], nums[right] nums[right], nums[i 1] return i 1这一版逻辑最直白适合教学但不是工程最优选择。因为每次扫描都把“小于等于基准”的元素交换到前面如果数组里大量元素等于基准这些等值元素会全挤到一侧破坏平衡最坏情况下会退化到 O(n^2)。所以后面 3.3 节要讲三向切分来解决重复元素问题。再补充一版双向扫描的分区实现这版在工程中更常见def partition_dual(nums, left, right): pivot nums[(left right) // 2] i left - 1 j right 1 while True: i 1 while nums[i] pivot: i 1 j - 1 while nums[j] pivot: j - 1 if i j: return j nums[i], nums[j] nums[j], nums[i]注意这版返回的 j 不是基准的最终位置而是“左右分界点”。递归时要用两段区间[left, j]和[j1, right]不能照搬单向扫描那版的递归写法。很多网上流传的代码拼接错位就是因为没注意到两种分区返回值的语义不同。2. 快速排序的效率边界与复杂度拆解2.1 最好、最坏、平均情况到底怎么算很多人记住“快速排序平均 O(n log n)”但不知道这个结论成立的前提。我建议亲手推一遍这样才能理解为什么基准值选择能成为优化重点。最好情况是每次分区恰好把数组分成两个等长的子区间。递归过程形成一棵完全平衡的树每层的分区代价是 O(n)树高是 log n所以总复杂度是 O(n log n)。最坏情况是每次分区都极度不平衡比如基准值恰好是当前区间的最小值那么右子区间的长度是 n-1左子区间为空。递归退化成一条链每层都要扫描近似 n 个元素总比较次数是 n (n-1) (n-2) ... 1也就是 O(n^2)。这种退化不是只存在于理论里直接用第一个或最后一个元素当基准然后排序一个已经有序或逆序的数组实测就能看到运行时间呈抛物线增长。平均情况的分析比较复杂数学功底好的可以去看经典推导不想看推导的话只要记住结论在随机分布的输入下快速排序的表现非常接近 O(n log n)而且常数系数比其他分治排序小实际运行往往更快。这也是名字叫“快速”的原因。我做过一个粗糙实验用一百万随机整数分别跑冒泡、归并、双向扫描快排归并大约需要几百毫秒快排能节省三成左右时间而且不占用额外大块内存。当然这个数据在不同语言和机器上会变但趋势基本一致。2.2 稳定性辨析为什么快速排序不稳定稳定性这个概念在很多业务场景里很重要。假设有一批订单先按金额排序再按时间排序如果排序算法是稳定的第二次排序后相同时间的订单内部还会保持金额的先后顺序。如果不稳定相同时间内的顺序可能被打乱。快速排序是不稳定的。原因在于分区时会远距离交换元素可能把相等元素的相对顺序弄反。举个例子数组[a1, a2, a3]表示三个值相同的元素它们在原始顺序中是 a1、a2、a3经过一次分区基准或相等元素可能被交换到别的区间a1 和 a3 的位置对调相对顺序就变了。如果你确定业务依赖相同关键字之间的原始顺序就不要用快速排序或者给比较函数增加一个带唯一粒度的“次要关键字”比如把对象 ID 也纳入比较人为保证排序的确定性。这一点是快排在工程上需要特别注意的。2.3 递归深度与栈开销有序数据的栈溢出风险递归快排的栈开销取决于递归深度。最好情况下递归深度是 log n一百万元素深度也就二十层左右毫无压力最坏情况下深度是 n一百万元素就可能在某次递归调用中压入几十万层栈帧。而且这种最坏情况在现实中很常见数组本来就已经排好序或近似有序时如果基准取首个或末尾元素分区出的两个子区间一个为空另一个长 n-1递归深度直接逼近 n。我见过不少项目在数据量只有几万的时候就崩溃或响应极慢查到最后就是这种“有序数据 固定基准”组合造成的。解决办法有两条路线一条是改进基准值选取让分区尽量平衡属于从根源上规避另一条是把递归改成显式栈循环属于物理上绕开调用栈深度的限制。两条路线不算冲突工程上经常同时用后面第 3、4 节展开讲。下面用一个表格把快排的复杂度边界汇总清楚场景时间复杂度辅助空间需要规避的原因最好情况O(n log n)O(log n)分区非常平衡平均情况O(n log n)O(log n)随机数据下接近最好最坏情况O(n^2)O(n)分区极不平衡常由固定基准导致稳定性不稳定/远距离交换破坏等值元素顺序3. 快速排序的经典优化策略3.1 基准值选取三数取中与随机化针对“固定基准遇上非随机数据会退化”的问题最直接的优化是改进选基准的方式。第一种是随机化从当前区间随机挑一个元素当基准。这不能保证每次分区都平衡但能让“每次都不平衡”的概率变得极低。尤其对于输入数据是近乎有序的情况加入随机化后退化成 O(n^2) 的概率可以忽略不计。代价是需要随机数开销而且随机数生成器本身有成本。第二种是“三数取中”从当前区间的左端、中间、右端各取一个元素选其中值大小居中的那个当基准。这种做法的好处是能直接避开有序数据的坑数组基本有序时最左、最中、最右三个位置的值中间的那个通常很接近整个区间的中间值分区自然平衡。代码上可以在 partition 之前先做一个三数排序交换把基准挪到区间的某个固定位置然后复用原有分区逻辑。我自己的习惯是优先上三数取中数据规模特别大、或者担心输入存在恶意分布时再加随机化。三数取中代码量不大对性能的提升却非常明显。3.2 小区间切换插入排序另一个容易被忽略的优化是“小区间到底递归不递归”。分区是一个 O(n) 操作但它有固定开销函数调用、比较、交换、划分边界。当子区间长度很小的时候这个固定开销占比就显得很高继续递归不划算。工程里常见的做法是设置一个阈值比如区间长度小于等于 16 时直接改用插入排序。插入排序在小数据集上的实测表现往往优于快排因为它的循环很简单对缓存友好而且小数据本身接近有序的概率大插入排序对这种“几近有序”的小片段尤其快。这个阈值没有唯一标准。我在常用语言里测试下来8 到 24 之间差异不大取 16 是个比较稳妥的默认值。不要把它设得太大比如 100 甚至更多否则大量小片段都走 O(n^2) 的插入排序整体性能反而会被拖慢。混合思路的代码结构大致是这样def quicksort_mixed(nums, left, right): if left right: return if right - left 1 16: insertion_sort(nums, left, right) return p partition_dual(nums, left, right) quicksort_mixed(nums, left, p) quicksort_mixed(nums, p 1, right)示意图里的插入排序函数就是普通的插入排序只是限定在[left, right]区间内工作。3.3 三向切分处理重复元素数组里存在大量重复元素时普通双向分区会怎么表现想象一个百万级数组里面只有 1 和 2 两种值。双向扫描虽然把小于基准和大于基准的元素分开但等于基准的元素会左右各占一堆导致两边的分区结果仍然很长递归次数没有显著减少处理重复元素时做了大量无效交换。荷兰国旗问题式的三向切分是经典解法一趟分区把数组切为三个区域分别存放“小于基准”“等于基准”“大于基准”的元素。等于基准的区域一次性归位后续递归不再触碰相当于把重复元素直接压缩掉了。def quicksort_3way(nums, left, right): if left right: return lt, i, gt left, left 1, right pivot nums[left] while i gt: if nums[i] pivot: nums[lt], nums[i] nums[i], nums[lt] lt 1 i 1 elif nums[i] pivot: nums[i], nums[gt] nums[gt], nums[i] gt - 1 else: i 1 quicksort_3way(nums, left, lt - 1) quicksort_3way(nums, gt 1, right)这段实现里lt指向小于区的右边界gt指向大于区的左边界i是当前扫描位置。等于基准的元素就被夹在[lt, gt]中间不再参与递归。这个优化对“大量重复值”的输入效果非常显著。如果数据里重复值不多三向切分的额外判断会略微增加常数开销所以我不是所有场景都用它而是根据数据特征决定。4. 非递归实现与其他工程化改造4.1 用显式栈替代递归防止调用栈爆掉递归快排的栈深度不稳定最坏情况下和数组规模呈线性关系。在递归深度受限的语言或平台里比如某些嵌入式环境或函数调用深度受限制的场景直接递归很容易触发栈溢出。一种稳妥的方案是自己维护一个栈把待处理的区间存进去循环弹出处理。这样做的好处是栈占用可以控制且不会因为递归调用层级太多而崩溃。def quicksort_iterative(nums): if len(nums) 1: return nums stack [(0, len(nums) - 1)] while stack: left, right stack.pop() if left right: continue p partition_dual(nums, left, right) if p 1 right: stack.append((p 1, right)) if left p: stack.append((left, p)) return nums这里有一个小小的优化细节总是先把较大的区间压栈再压较小的区间这样循环弹出时会先处理较小的区间。为什么这么做因为较大的区间虽然晚处理但它被保存在栈里的时候不会导致栈无限制膨胀整体栈的大小可以被压到 O(log n) 的级别。这个技巧在很多避免递归深度的实现里都用得到。用显式栈代替递归还有个额外好处你想在排序中途做“限流”或“暂停恢复”时会更容易因为状态完全在一个栈对象里可以随时停下来观察。4.2 用循环改写单侧递归减小递归深度如果并不想彻底放弃递归写法还有一个折中策略只递归处理较小的一侧较大的一侧用循环继续在当前函数内处理。这种方法在不少教科书里叫“尾递归优化”但准确说是“限制递归深度”的手段。它把递归深度从可能达到 n 降低为 O(log n)同时又比显式栈更轻量。def quicksort_tail(nums, left, right): while left right: p partition(nums, left, right) if p - left right - p: quicksort_tail(nums, left, p - 1) left p 1 else: quicksort_tail(nums, p 1, right) right p - 1这个写法要稍微想一下每次只递归小区间大区间进入下一轮 while 继续分区这样函数调用栈里永远只会同时存在一条较短的调用链。结合三数取中、插入排序阈值之后这个版本基本达到了比较接近工程级快排的水平。4.3 工程中排序选型到底怎么取舍讲到这里难免会有人问既然快排还能优化为什么很多语言内置的排序函数不直接用纯快排我的理解是工程上的排序选型从来不是只盯一个算法的理论复杂度而是在最坏情况、稳定性、常数开销、数据分布不确定等多重目标之间找平衡。很多内置排序实际上是“混合排序”数据量小时用插入排序稍大时用快排并且通过内省式检测如果递归深度超过某个阈值就切换到堆排序。这样既保留快排的平均高性能又保证最坏情况不会退化到 O(n^2)。所以在实际项目里我的建议很直接绝大多数场景直接用语言内置排序函数它已经包含了很多优化。只有当你明确知道数据特征或者内存访问路径有特殊要求时才考虑手写排序。手写时至少把三数取中、小区间插入、三向切分这类常见优化做进去否则不如内置函数。需要稳定排序、且需要手写时优先考虑归并排序而不是快排。5. 实战排错与排序算法学习的一些经验5.1 常见问题速查表我在手写快排和给模拟项目X的数据预处理模块加固排序环节时反复踩过几个坑。整理成一张速查表方便对照现象可能原因排查方法排序后仍有元素没在正确位置分区返回值语义用错递归边界不对打印每个分区的 left、right、p 值递归无限循环程序卡死基准值选择导致某个子区间长度为 0检查分区后左右子区间是否至少有一个不变数据接近有序时特别慢固定取首/末元素当基准改用三数取中或随机基准大量重复元素时性能急剧下降普通分区把等值元素分散改用三向切分大数组直接栈溢出递归深度接近 n改成显式栈或单侧递归优化排序后相同关键字的顺序变了快排本身不稳定业务逻辑却依赖稳定换归并排序或给比较函数加次要关键字5.2 一个最容易忽略的分区边界坑开头说“分区返回值语义不同”这里展开讲。用单向扫描那版分区的返回值是基准值的最终下标所以左右子区间是[left, p-1]和[p1, right]。用双向扫描那版返回值是左右指针交错的位置基准不一定在这个位置所以递归区间是[left, p]和[p1, right]。很多把网上代码粘到项目里的人会发现排序后某些元素顺序不对原因就是两版代码混用。我自己一开始也没少在这一步吃亏。调试方法很简单在排序前后分别打印数组如果发现“小的在大的后面”就先确认递归区间和分区返回值的匹配关系。还有一种隐蔽问题单向扫描分区时用还是会影响相等元素的分布。会把相等元素扫到左侧会扫到右侧如果基准又被放到某一侧可能让子区间长度失衡。平时看不出问题但极端重复数据下就很容易触发退化。5.3 我是怎么检验排序算法写对没写对的疯狂写几个测试用例并不够因为你验得再多也只是一部分样本。我建议至少要覆盖这么四类空数组和单元素数组这一类直接返回不该报错。完全有序、完全逆序的数组主要用于暴露基准值退化问题。大量重复元素的数组比如几万个 1 和 2 混在一起专门测三向切分。随机大数组用来对比不同实现的实际运行时间。除功能测试外我还习惯在代码里埋一个计数器统计比较次数和交换次数。同一个输入不同优化版本跑出来的计数差异会非常明显比只靠计时器更稳定也不受系统负载影响。这个习惯帮我快速判断一个理论上的优化是否真的有效。5.4 几个我常用的学习顺序建议如果是对快排还不太熟的读者我建议按这个顺序练先写递归 单向分区确保理解分治和基准再改成双向分区理解两种分区返回值差异然后加三数取中和插入排序阈值接着加三向切分最后如果项目有限制再把递归改成显式栈循环。每改一步都用上一节的测试用例集跑一遍。这串流程走完不夸张地说你对快速排序的理解已经超过绝大多数只会调内置排序的人。实际调试时如果再有疑问可以把暂停回目录翻看这篇应该能解决大部分问题。我在实际使用中最大的体会是快速排序并不是一个“背代码”的算法它更像一个实验场让你理解基准、分区、递归这几件事是怎么耦合的。优化策略看着多但本质上都在做同一件事想办法让每次分区尽量平衡同时减少不必要的比较和交换。把这些想明白了不管未来换哪种语言拿过来十几分钟就能写出一个靠谱的快排。