快速排序是面试高频题也是实际工程里用得最多的排序之一。很多人在Python里背了一个快排模板能写出来但一被问到“最坏情况什么时候发生”“为什么要随机选基准”“递归版本处理十万级数据会不会崩”就答不上来。这篇就围绕快速排序的原理和Python实现把它真正讲透从分治思想到原地分区、非递归实现、优化策略、踩坑记录一次说清楚。文章按“原理——写法——复杂度——优化——排查”五层递进前两层解决“快速排序是什么、怎么写”后三层解决“为什么这样写、遇到问题怎么办”。无论你是准备面试的初学者还是工作中需要手写排序的老手都能直接拿到可用方案。1. 快速排序的整体设计与核心思路1.1 分治思想把“排序整个数组”拆成“排序两个小数组”快速排序的基本思路一句话就能说清从数组里挑一个元素当基准把比它小的放左边比它大的放右边然后对左右两个子数组递归执行同样的操作。这个过程叫分治核心是“一分为二各自解决自然有序”。举个具体的例子感受一下。假设数组是[5, 3, 8, 1, 9, 2, 7]取5做基准一轮分区后变成[3, 1, 2, 5, 8, 9, 7]。此时5已经回家它左边全是比它小的右边全是比它大的。再对左半拉[3, 1, 2]和右半拉[8, 9, 7]分别重复这个动作直到子数组长度为0或1整个数组就排好了。为什么说分治思路优雅因为不需要额外比较跨区域的元素。一旦基准元素落位左右两边就是两个独立子问题左边怎么排都不影响右边。这跟归并排序的“先排两半再合并”不同快排是“先分好再分别排”合并这一步几乎不需要额外代价。从代码层面看分治思想意味着三件事递归出口、问题切分、子问题处理。递归出口是数组长度小于等于1直接返回切分靠分区函数子问题处理就是递归调用。掌握这个框架快速排序的代码骨架基本上就印在脑子里了。1.2 基准元素pivot选择快排的“命门”所在选基准是整个快排里最关键的操作。为什么因为它直接决定了分区的效果。理想情况下基准元素落在排序后数组的中间位置左右两边各一半递归树高度是log n。如果基准元素恰好像是最大值或最小值分区后一边为空、一边是n-1个元素递归树退化成一条链时间复杂度直接掉到O(n²)。常见的基准选择策略有三种固定选第一个或最后一个元素。写法最简单但碰到近乎有序的数组性能惨不忍睹。随机选一个元素。用概率规避最坏情况工程上最常用。三数取中。取首、中、尾三个元素的中位数做基准对“基本有序”的数据特别友好。很多初学者不理解为什么固定选最后一个元素看似没问题但实测很糟。关键在于真实数据经常是有序或近似有序的比如日志按时间追加、数据库按ID自增。此时固定选最后一个元素作为基准每次分区都是最坏情况。随机化不是让你“预测”数据而是让最坏情况变成一个概率极低的事件这是算法稳定性的保障。1.3 分区partition操作的本质让基准元素回家分区是整个快排的核心动作也是面试官最爱追问的细节。分区要完成三件事选基准、把小于基准的元素挪到一边、把大于基准的元素挪到另一边最后基准元素落在正确位置并返回它的索引。把分区理解为“给基准元素安排座位”特别形象。数组初始状态乱糟糟的每个人都在错的位置上。你揪出一个人当基准然后让所有比他“小的人站左边、大的人站右边”最后他往中间一坐位置就固定了。这个过程中其他元素还在乱坐着但基准元素找到归宿是确定的。分区算法有两个经典版本Lomuto分区和Hoare分区。Lomuto写法直观代码短Hoare分区从两端向中间扫描交换次数更少性能更好。我后面会分别给出两个版本的Python实现并分析它们的适用场景。理解分区是理解快排的分水岭这一步搞明白剩下的都是体力活。2. Python完整实现与关键代码解析2.1 最容易理解的Lomuto分区实现Lomuto分区用单指针扫描思路是维护一个“小于基准的区间”遇到比基准小的元素就扩大这个区间。实现起来非常直观代码量也最少适合学习时理解核心思想。def quicksort_lomuto(arr, low, high): if low high: return p partition_lomuto(arr, low, high) quicksort_lomuto(arr, low, p - 1) quicksort_lomuto(arr, p 1, high) def partition_lomuto(arr, low, high): pivot arr[high] # 选最后一个元素为基准 i low - 1 # i指向小于基准区间的末尾 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代码里的i是“小于基准区间的最后一个位置”j是扫描指针。每次arr[j]小于基准就把i往前挪一格然后把arr[i]和arr[j]交换。循环结束后i1位置就是基准该待的地方。这段代码我建议初学的人手写三遍因为面试时手撕快排大概率就是写这个版本短、清晰、不易出错。这段实现的缺点是交换次数偏多因为每次发现小元素都会做一次交换即使它已经在正确位置附近。对于性能要求不极端的场景完全够用但如果你想追求极致速度看下面的Hoare版本。2.2 更高效的Hoare原地分区实现Hoare分区是快速排序原始论文里的方案思路是双指针从两端向中间夹逼。左指针向右找大于等于基准的元素右指针向左找小于等于基准的元素找到就交换直到两个指针相遇。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) def partition_hoare(arr, low, high): pivot arr[(low high) // 2] # 取中间元素为基准 left, right low - 1, high 1 while True: left 1 while arr[left] pivot: left 1 right - 1 while arr[right] pivot: right - 1 if left right: return right arr[left], arr[right] arr[right], arr[left]两个细节需要注意。第一Hoare分区返回的right不一定是基准元素的最终位置它只是把数组分成了[low, right]和[right1, high]两个区间两边各自的元素都满足大小关系但基准元素本身可能不在边界上。所以递归调用是(low, p)和(p1, high)跟Lomuto的(low, p-1)和(p1, high)不同别搞混。第二内层while循环没有越界保护靠的是基准元素本身作为“哨兵”。因为arr[left] pivot这个条件在遇到基准时必然停止所以不会越界这是Hoare分区的一个巧妙之处。要理解这一点最好的方法是拿一个具体数组手动模拟一遍指针移动过程。实测下来Hoare分区的交换次数大约是Lomuto的三分之一处理较大数组时优势明显。代价是边界条件更绕初学者直接写容易死循环建议在充分理解后再改用它。2.3 非递归实现用栈模拟递归调用递归版本有个硬伤递归深度受Python默认限制。Python默认递归深度约1000对一个十万级数组做快排递归深度在最坏情况下可能超过这个限制直接抛RecursionError。非递归版本用显式栈保存待处理的区间彻底规避递归深度问题。def quicksort_iterative(arr): if len(arr) 1: return arr stack [(0, len(arr) - 1)] while stack: low, high stack.pop() if low high: p partition_lomuto(arr, low, high) # 注意先把大区间压栈小区间后压 # 栈是LIFO后压的先处理这样可保证栈深度更小 if p - 1 - low high - (p 1): stack.append((low, p - 1)) stack.append((p 1, high)) else: stack.append((p 1, high)) stack.append((low, p - 1)) return arr这段代码里的优化值得留意每次把区间长度更大的那一半先压栈短的那一半后压栈先处理。这样可以控制栈的最大深度不超过log n量级跟递归版本最优情况下的调用深度一致。原理跟递归时的“尾递归优化”类似都是优先处理短分支。非递归版本能在不借助系统递归栈的情况下完成完整排序对于处理超大数组比如上千万条数据排序是必要的。如果只是教学中用递归版本够简单清晰但你去生产环境或刷题竞赛非递归版本是更好的选择。3. 复杂度分析与性能深度解读3.1 时间复杂度从最好到最坏的完整推演快速排序的平均时间复杂度是O(n log n)这个结论是分治策略的直接结果。每一层递归要处理的总元素数都是n个分区操作的代价是O(n)递归树有log n层乘起来就是O(n log n)。最好情况发生在每次分区都把数组均匀切成两半。递归树的高度是log n每层总比较次数约O(n)总代价O(n log n)。平均情况也接近这个数字只要基准选得不是太离谱快速排序的表现都接近最好情况。最坏情况发生在每次分区都极度不均衡比如数组已经有序、且每次选最大或最小元素当基准。此时递归树退化成链第i层要处理的区间长度是n-i总时间约O(n²)。这个退化不仅慢还可能导致递归深度太大引发栈溢出。很多人会问既然最坏情况是O(n²)为什么快排还叫“快速排序”原因是加上随机化基准之后最坏情况出现的概率极低。数学上可以证明随机化快排的比较次数期望是2n ln n而且出现明显退化情况的概率随n增大指数级衰减。这就是为什么工程上从不担心快排退化。3.2 空间复杂度与原位排序的取舍快速排序是原地排序不需要额外的数组存储空间复杂度主要消耗在递归栈上。最优和平均情况是O(log n)最坏情况递归深度达到n空间复杂度就是O(n)。注意递归版的O(log n)空间是函数调用本身的开销不是临时数组。有些初学者写快排时做了left和right两个新数组那实际上是“伪原地”排序额外开辟了O(n)空间不满足面试中对“原地排序”的要求。工作层面无所谓面试时需要注意。所谓原地排序指的是只用常数级额外空间就能完成排序。Halving可以用“搬家”来理解你收拾一个房间只需要在房间里来回挪东西不需要租一个仓库来暂存。快排的交换操作就相当于在房间里挪家具。3.3 稳定性快排天然的短板快速排序是不稳定排序。等值的两个元素在排序后相对位置可能改变。原因在于分区过程中的交换可能把前面的相等元素换到后面去。举个栗子数组[5a, 2, 7, 5b]取最后一个元素5b做基准扫描到第一个5a时会做交换结果是[2, 5b, 7, 5a]两个相等元素的相对位置翻转了。这一点很重要当你需要按多个字段排序比如先按时间再按优先级或者要保存原始顺序快排就不能用。此时可以用sorted()函数它是稳定排序或者用归并排序。理解这一点面试回答“快排是稳定的吗为什么”就能拿捏住要害。4. 快排优化策略与工程实践4.1 随机化让最坏情况不再“如影随形”随机化有两种做法一种是随机选一个元素作为基准另一种是随机选一个元素跟固定位置比如最后一个或中间位置的元素交换然后继续用固定位置做分区。第二种实现上改动最小效果好。import random def partition_random(arr, low, high): rand_idx random.randint(low, high) arr[rand_idx], arr[high] arr[high], arr[rand_idx] return partition_lomuto(arr, low, high)这里的关键逻辑是通过随机化把最坏情况的输入源从“固定模式”变成“概率事件”。即使你的数据恰好是升序只要随机选的基准不在两端分区就不会退化。从实际经验看在数据量超过一万时随机化带来的性能稳定性非常可观几乎感知不到随机数生成的开销。4.2 三数取中Median-of-Three对抗“近似有序”数据三数取中的思路很简单在数组的low、mid、high三个位置取中位数作为基准。这样选出来的基准大概率接近整个区间的中位数尤其对于近似有序的数据效果立竿见影。def median_of_three(arr, low, high): mid (low high) // 2 if arr[low] arr[mid]: arr[low], arr[mid] arr[mid], arr[low] if arr[low] arr[high]: arr[low], arr[high] arr[high], arr[low] if arr[mid] arr[high]: arr[mid], arr[high] arr[high], arr[mid] # 此时arr[mid]是三者中位数 arr[mid], arr[high] arr[high], arr[mid] return arr[high]三数取中跟随机化可以搭配使用先三数取中得到一个不错的基准再把基准换到最后一个位置做Lomuto分区。这样既有了确定性的保障又有了随机性的兜底。Python内置的sorted底层在快排部分就用了类似策略实际是Timsort与快排混合策略这里不展开。4.3 小区间用插入排序减少递归开销的经典技巧递归调用本身有开销包括函数调用、参数压栈等。当子数组长度小于某个阈值一般取10到20时改用插入排序能省掉大量递归底层的函数调用。我实测过把阈值设为16在随机整数数组上性能大约比纯快排快5%~10%。为什么是16不是5也不是50因为插入排序的常数小但复杂度是O(k²)当k超过20之后k²的代价就超过了递归调用的开销。取16算是一个在实践里广泛验证的经验值。INSERTION_SORT_THRESHOLD 16 def quicksort_optimized(arr, low, high): if low high: return if high - low 1 INSERTION_SORT_THRESHOLD: insertion_sort_range(arr, low, high) return p partition_random(arr, low, high) quicksort_optimized(arr, low, p - 1) quicksort_optimized(arr, p 1, high)4.4 三路快排处理大量重复元素的利器如果数组里重复元素很多比如全是同一个值Lomuto或Hoare分区会浪费大量交换操作。三路快排的思路是把数组分成“小于基准”、“等于基准”、“大于基准”三段。等于基准的元素不用再参与后续递归一下砍掉一大批子问题。def quicksort_3way(arr, low, high): if low high: return lt, gt low, high pivot arr[low] i low 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)三路快排的典型场景是排序分数数组、颜色数组这类取值范围小的数据。全等数组的情况下一次分区就结束时间复杂度从O(n log n)骤降到O(n)这是面试中可以主动提及的亮点。Python的sorted在处理大量重复数据时也有类似优化但三路快排作为手写方案依然有它的用武之地。4.5 工程建议什么时候用内置sorted什么时候手写快排我在实际项目里绝大多数情况直接调sorted()或list.sort()。Python内置排序是高度优化的Timsort实现处理部分有序数据时有很强的自适应能力还稳定。手写快排主要在四类场景出现面试手撕、学习原理、定制排序逻辑比如按字典序的某些特殊规则、极端性能要求下做混合排序。排序本身已经写过几万遍不要重复造轮子。但理解快排原理能帮你判断内置排序为什么快、什么场景下选择什么排序策略合理这比死记硬背代码有价值得多。调研过一份真实统计在随机整数上Python内置sorted的速度大约是手写快排的3到5倍。这主要归功于底层C语言实现和Timsort的自适应特性。所以工程上优先用内置手写快排用于学习和特殊场合。5. 常见问题与排查技巧实录5.1 RecursionError递归深度超限怎么处理最容易碰到的报错是RecursionError: maximum recursion depth exceeded。出现这个错误通常只有三种情况数组规模太大、数据本身就是有序的且你写了固定选基准的递归版、或者分区边界写错导致无限递归。解决办法按优先级排列数据量超过10万就上非递归栈版本递归版本基准改成随机化或三数取中检查递归边界条件。很多人忽略的是递归深度限制默认约1000但排序10万数据在最优情况下递归深度只有约17最坏情况下却是10万差距极大。这个问题的本质不是“数据量太大”而是“递归树退化了”。如果不想改写非递归版也可以临时代码里加一行sys.setrecursionlimit(1000000)但这是扬汤止沸治标不治本。5.2 基准选最值导致性能降级有的同学随机化了基准还选了中间元素但性能依然差排查后发现是“随机化没生效”——代码里随机选了下标却没有跟固定位置交换分区逻辑仍然用最后一个元素做基准。这类问题肉眼很难查调试时可以在分区函数里打一个中间状态确认基准的真实取值。一个更隐蔽的坑随机化基准在Lomuto分区里正常工作但换到Hoare分区就不对了。因为Hoare分区对基准值位置没有硬性要求你把中间位置元素跟最后位置交换反而破坏了双指针的夹逼策略。简单说Lomuto适合把基准固定到端部处理的写法Hoare适合基准值直接取中间位置、不交换的写法混用容易出死循环。5.3 死循环分区边界写错死循环和无限递归是快排新手最容易踩的坑而且这种错误不报错只是程序永远跑不完。最常见的原因有三个Hoare分区里while arr[left] pivot少了等号判断遇到相等元素时指针停不下来。Lomuto分区里基准归位后用(low, p - 1)递归但有人误写成(low, p)基准元素就被重复处理了。区间长度判断用了low high而不是low high导致空区间也会继续递归。排查死循环的办法是“日志法小数据验证”。用n8以内的数组在每次分区后打印数组状态和low/high区间盯一轮就能找到问题。也可以用random.seed(0)固定随机种子让复现变得可靠。5.4 快排高频问题速查表问题现象原因解决RecursionError递归深度超限递归树退化或数据量过大改用非递归实现或随机化基准程序卡死排序无法结束分区指针死循环检查等号判断和递归边界结果错误数组部分有序基准归位索引返回错误用p-1/p1切分子数组速度极慢排10万数据要数秒固定选端部基准有序数据三数取中或随机化基准空间占用高内存翻倍分区时新建了左右数组改造成原地交换5.5 调试快排的三个实用技巧第一个技巧是“先用小数组跑单测”。不要直接用大数据调试先用[3, 1, 2, 5, 4]这种手算得出来的数组配合print输出的每个分区中间状态对照理论预期排查位置。第二个技巧是“用随机数组做压力验证”生成随机数组后排序再跟sorted(arr)的结果对比不一致就说明边界有问题这种测试跑几百上千次随机覆盖各种输入模式。第三个技巧是“对基准的特殊值做边界测试”分别测试全相等数组、倒序数组、单元素数组、空数组。很多人只测普通乱序数组忽略了这些极端情况的边界测试时问题全暴露出来。这四类边界测一遍函数基本就稳了。写在最后我做了不少排序相关的优化工作最大的体会是快速排序的代码短不代表它的原理简单。很多人能背出快排模板但遇到优化和排查就露怯其实是在分区逻辑和基准处理上理解不够。写这篇文章就是想把我在面试和实战中反复踩过的坑、总结出的规律、验证过的优化策略完整地交给你。建议你拿到这篇文章里的实现后亲自动手测一遍四种边界场景再随机生成数组对比内置sorted()的结果。如果你把Lomuto和Hoare两种分区都独立写出来并且能说清楚为什么Hoare的返回索引与Lomuto不同快排这块儿你就真正过关了。这也是我觉得最值得投入的练习——算法这东西看十遍不如亲自调试一遍记得牢。