如果你刚接触算法大部分教程都会告诉你排序是数据结构绕不开的第一课而快速排序又是排序算法里最值得花时间吃透的那一个。在Python里实现快速排序格外有意思——这门语言太方便了方便到可以用几行列表推导式写出不亚于教科书实现的快排但也正因为这种方便很多新手会忽略排序背后的性能陷阱等到数据量一上来就踩坑。这篇文章想聊的不只是怎么写一段快速排序代码而是从思路到实现、从复杂度到工程实践把快速排序这个经典算法在Python里的完整玩法捋一遍。内容适配正在学数据结构与算法的人、准备面试刷题的开发者以及工作中需要手写排序逻辑的Python使用者。读完你会搞清楚枢轴怎么选、递归为什么爆栈、重复元素怎么处理、以及Python内置sort为什么能碾压手写快排——这些事情不是背结论就能懂的得动手拆开来看。1. 快速排序的核心思路分治到底是怎么分的1.1 一趟分区把大问题切成小问题快速排序最核心的机制是分区操作。选一个数当枢轴把数组里所有小于它的数放在左边、大于它的数放在右边一趟结束之后枢轴就落在整个序列的最终位置上接下来只需要对枢轴左右两侧的子数组分别重复同样的动作。你可以用生活中的场景来理解一摞待整理的考卷先抽出一张作为基准把所有分数低于它的放到左手边高于它的放到右手边。基准那张试卷的位置不需要再动了剩下的工作只是对两堆分别执行同样的操作直到每一堆都只剩一张或零张。这就是分治思想——把一个大问题拆成两个独立的小问题先处理局部局部处理完整体自然有序。在Python里写分区逻辑有个特别直观的写法用列表推导式一口气筛出小于、等于、大于枢轴的三份序列。这样写代码看起来非常干净能让人一眼看懂分治结构但代价是它会额外创建多个临时列表内存开销不小。实际工程里更常用的是原地分区也就是通过元素交换让数组自己完成重排而不是生成新列表。分治思想在排序之外的用武之地很广比如二分查找、归并排序、二叉树遍历本质上都是同一套拆了再处理的模板。我见过不少初学者把快速排序当背模板题来记这样当然也能写出来但一旦面试官追问一句为什么这趟分区结束后枢轴就到位了很多人就卡壳。问题的答案在于分区时所有小于枢轴的元素都往左走所有大于枢轴的元素都往右走那么枢轴当前所在的这个位置就是它在有序序列里唯一能站的位置。这个逻辑不难但值得你自己画一遍。1.2 为什么在Python里快速排序依然是必选项Python的标准列表排序用的是Timsort并不是快速排序。那为什么还要学它原因有这么几条。第一快速排序的平均时间复杂度是O(n log n)虽然Timsort在真实数据上表现更好但快排的常数因子低、对缓存友好在特定场景——比如纯数值型数据、原地排序需求、内存受限的环境——依然有不可替代的价值。第二大厂面试和算法竞赛考察的不是会不会调sort而是能不能在约束条件下自己推导出分治排序。第三理解快排的分区逻辑对你学习与Partition相关的算法比如求数组第K大的数、荷兰国旗问题帮助极大。我自己最早学快排时也嘀咕过一句Python里有sorted()我干嘛要自己写后来被一道手写快排并处理重复元素的面试题问住才意识到问题不在于有没有内置排序而在于你有没有真的理解分治与分区的边界条件。这让我后来带新人时养成了一个习惯不管对方用的是什么语言第一道手写排序题必须是快排而且必须讲清楚每次分区的区间范围。换个角度看快速排序在Python里的价值并不在于替代内置排序而在于它是一个绝佳的算法思维训练场。你能在几十行代码里同时接触到递归、分治、交换、随机化、复杂度分析这种密度在别的算法里很少见。所以不要被重复造轮子的说法劝退该造的轮子还是得造。2. Python实现快速排序从思维演示到工程可用2.1 最短版本列表推导式写三行很多人展示Python快排会给你看这样一个版本def qsort(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] left [x for x in arr if x pivot] mid [x for x in arr if x pivot] right [x for x in arr if x pivot] return qsort(left) mid qsort(right)这段代码思路完全正确甚至能通过绝大多数小规模测试用例。它把小于、等于、大于枢轴的元素分别筛出来然后递归拼接。但如果你拿它去处理真实数据很快就会撞上三个隐藏问题。第一个问题是每次递归都会生成三个新列表数组长度为n时递归过程中总的额外内存占用可以达到O(n log n)量级。第二个问题是Python的列表拼接操作会复制元素拼接次数一多CPU时间也上去了。第三个问题是当数据量达到几千到几万时这段代码会明显变慢递归调用和列表推导的开销叠加在一起实测下来往往比原地版本慢2到3倍。我把这段代码当作思维演示版来用。它适合放在教程里让人快速抓住快排的本质——选枢轴、分组、递归——但真要落地处理数据还是得靠原地交换的版本。另外注意一件事这个版本里我特意把等于枢轴的元素单独放进mid这是为了规避重复元素导致递归无法收敛的问题等读到后面第5章你会知道这个细节有多重要。2.2 原地分区版本工程上更靠谱原地快排的关键在于写一个分区函数。经典的Lomuto分区是这样做的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 def quick_sort(arr, low, high): if low high: pivot_idx partition(arr, low, high) quick_sort(arr, low, pivot_idx - 1) quick_sort(arr, pivot_idx 1, high)这个版本需要你重点盯住两个地方。第一个地方在分区函数内部选最后一个元素做枢轴i记录的是最后一个小于等于枢轴的元素位置。循环里每发现一个小于等于枢轴的值就把i前进一步同时交换元素。循环结束时i 1位置右边全都是大于枢轴的值再把枢轴换过去一趟分区就完成了。第二处是递归边界。左区间是low到pivot_idx - 1右区间是pivot_idx 1到high。很多刚接触的人会犯一个低级错误递归时把已经被枢轴占住的位置又传了一遍结果排序结果反复颠倒甚至死循环。只要边界多写或少写一位两三个元素的数组就能立刻暴露问题。我自己最初写这个版本时踩过另一个坑循环里如果不加而只用遇到枢轴与其他值相等时会出现枢轴原地不动的情况导致分区不平衡递归深度异常。加不加等号看似小事实际上直接影响快排在重复数据下的表现。如果你关心排序的稳定性这个等号也会产生影响——虽然快速排序本身就不是稳定排序但加等号与否至少能让相等元素的分布可控一些。2.3 随机枢轴把最坏情况变成运气问题快速排序最怕的就是数组本身已经有序或接近有序。如果固定取最后一个元素做枢轴有序数组每次分区都只有一边有数据递归树退化成一条链时间复杂度变成O(n²)。这个问题有一个非常经典的解决思路随机选枢轴或者取首、中、尾三个数的中位数。随机枢轴的实现很简单import random def partition_random(arr, low, high): pivot_idx random.randint(low, high) arr[pivot_idx], arr[high] arr[high], arr[pivot_idx] return partition(arr, low, high)先随机挑一个位置把它和末尾元素交换然后继续走标准的Lomuto分区逻辑。这样做之后最坏情况依然可能出现但从概率上讲连续几次都随机到最差枢轴的可能性已经非常低。换句话说随机化不是消除最坏情况而是让最坏情况变成一个几乎不可能发生的随机事件。如果你不想依赖random模块三数取中法是另一个常见选择取数组首元素、中间元素、末尾元素选三个数中间大小的那个当枢轴。这个策略在工程实现里很流行因为它不引入随机性行为可预测而且对已经有序的数组效果特别好——三个数的中位数恰好是中间值分区马上就均衡。实际项目中我更喜欢把随机化和三数取中结合起来用小规模数组比如长度小于50直接插入排序收尾中等规模用三数取中超大规模在随机位置基础上再做三数取中。这样一层层叠加防御快排在各种数据形态下都能表现得稳。3. 性能深挖复杂度、稳定性与隐藏开销3.1 时间复杂度最好、平均、最坏的推导逻辑快速排序的时间复杂度取决于每次划分是否均衡。最好的情况是每次都把数组对半分递推式是T(n) 2T(n/2) O(n)解出来是O(n log n)。平均情况也是O(n log n)但推导过程比最好情况复杂核心是概率期望对随机排列的数组任意一次划分的期望复杂度是O(n)递归深度期望是O(log n)。最坏的情况是每次划分都极度不平衡比如有序数组配上固定选最后一个枢轴的策略递推式变成T(n) T(n-1) O(n)累加起来是O(n²)。关于平均情况的推导我想多说一句。很多人只背结论但面试时如果能讲清楚平均O(n log n)是怎么来的印象分会差很多。快排的平均复杂度求解通常用递归期望设T(n)为长度为n的数组排序的期望时间划分点均匀随机得到期望递推式T(n) n (1/n) * Σ(T(k-1) T(n-k))其中k从1到n这个式子化简之后可以证明T(n) O(n log n)。推导过程不需要背但你得理解它蕴含的逻辑每一次划分点的位置是随机的所有可能的划分情况取平均之后递归树的高度依然是对数级别。有个新手容易混淆的点是O(n log n)是平均情况但最坏情况O(n²)依然存在。所以当你听到快排是O(n log n)时心里要清楚这是有前提的。这也是为什么工程实现要做随机化或三数取中——因为这些策略能让最坏情况在概率上被压制让平均复杂度真正成为你实际能体会到的性能。3.2 空间复杂度递归栈与切片开销快速排序的递归实现有递归栈开销。最好和平均情况下递归深度O(log n)空间复杂度O(log n)最坏情况下深度O(n)空间复杂度O(n)。注意这个空间不算数组本身的存储而是函数调用栈占用的内存。用切片版本写快排时情况会更复杂。每次切片生成新列表递归到下一层时上一层那些临时列表还没释放整个递归过程中的存活列表总长度加起来可以到O(n log n)。这在处理几十万级别的数据时非常明显程序会占用大量内存甚至触发内存告警。所以我的建议很明确真正处理大批量数据优先用原地分区版本。Python的递归限制也要单独拎出来说。默认递归深度上限是1000处理排序时数组长度超过几百就可能触发RecursionError。解决办法可以在代码里手动设置sys.setrecursionlimit(1000000)但更工程化的思路是彻底改成非递归实现用一个显式的栈来模拟递归过程。第6章我会给出代码这里先记住一个结论递归深度不是只能靠调参数解决数据结构层面的替换往往更彻底。3.3 枢轴选择策略横向对比策略最好情况最坏情况优点缺点固定第一个/最后一个O(n log n)O(n²)实现最简单、无额外开销有序数组直接退化随机选择O(n log n)O(n²)概率上避免最坏情况依赖随机数、行为不确定三数取中O(n log n)O(n²)对有序数据特别友好、可预测选数有少量比较开销三数取中随机O(n log n)O(n²)兼顾防御性与随机性实现复杂度更高这张表不是让你背结论而是告诉你怎么根据场景选。如果数据是随机分布的固定取任何一个位置都差不多如果数据可能有序优先考虑随机或三数取中如果排序在服务端频繁被调用且不希望引入随机种子带来的不确定性三数取中更稳妥。提示实际工程里许多标准库的qsort实现会在不同平台上采用不同策略但大多都包含三数取中或类似手段用来防御有序输入造成的性能退化。4. 实操记录从零写一个能上路的QuickSort4.1 完整代码随机枢轴 原地分区 递归限深把前面聊的思路合并起来我给出一个自己在项目里用过的基础版快排import random import sys def partition(arr, low, high): pivot_idx random.randint(low, high) arr[pivot_idx], arr[high] arr[high], arr[pivot_idx] 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 def quick_sort(arr, low, high): if low high: pi partition(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi 1, high) def sort(arr): if arr: quick_sort(arr, 0, len(arr) - 1) return arr sys.setrecursionlimit(1000000)这里把随机枢轴和Lomuto分区做成了一个整体对外暴露一个sort接口。这样的好处是调用时不用关心递归终止条件只需要传数组进去。需要说明的是sys.setrecursionlimit(1000000)并不是银弹。它只是把递归深度上限放宽实际上Python的递归调用依然有栈开销在极端情况下仍可能触底。如果你要排序的数据超过几十万条建议直接看后面的非递归实现。还有一个细节随机枢轴的随机种子会影响每次运行的实际耗时所以在做性能对比实验时最好固定随机种子否则测出来的结果会有波动。4.2 测试用例与边界验证写排序算法最怕遇到边界条件出错。我用下面这些用例来验证代码是否靠谱# 空数组 arr1 [] # 单元素 arr2 [7] # 包含重复元素 arr3 [5, 3, 8, 3, 2, 5] # 逆序数组 arr4 [9, 8, 7, 6, 5, 4, 3, 2, 1] # 大随机数组 arr5 [random.randint(0, 10000) for _ in range(5000)] for arr in [arr1, arr2, arr3, arr4, arr5]: result sort(arr[:]) assert result sorted(arr), f排序失败: {result}这里特意用arr[:]复制出原始数组再排序避免测试时把原始数据改了。每个用例跑完之后再和Python内置sorted()的结果对比任何一个对不上就说明算法有错误。要注意的是上面这种验证方法全过也不代表代码一定正确。排序算法是递归的最容易出错的地方是分区后的递归区间左区间应该到pi - 1右区间应该从pi 1开始。如果边界多写了或漏写了一位通常在元素数量为2或3的小数组上就会立刻暴露。所以测试一定要包含最小规模的用例而不是一上来就测几千条数据。我把这组测试放在了一个名为test_quick_sort.py的文件里配合assert断言当回归测试用。以后只要改了算法实现跑一遍就知道有没有破坏原有行为。这种习惯在写算法练习时不一定受重视但放到工程环境里非常关键——排序往往是其他业务逻辑的底层依赖出错了很难第一时间发现。4.3 性能实测和Python内置sort比一把我实测了一个10万元素的随机整数数组环境是Python 3.10普通笔记本上跑出来的参考数据如下排序方式耗时Python内置sorted约35ms手写随机枢轴快排约180ms手写切片版快排约450ms用不着惊讶内置sorted()完胜是预期结果。Python的sort是C语言实现的Timsort经过大量优化还针对Python对象比较机制做了专门调整。手写纯Python快排无论怎么优化在常数因子上都会被内置排序甩开。那手写快排还有意义吗我的看法是有而且分场景。如果数据规模不大几千条以内、且讲究代码可读性和可控性手写快排完全够用如果是在刷题、面试手写快排就是必须掌握的硬技能如果是在写生产代码、处理百万级数据不要自己造轮子直接用内置sort或者科学计算库的排序接口。知道自己什么时候该用轮子什么时候该造轮子比会背算法更有价值。5. 实战中躲不开的坑问题排查与优化5.1 RecursionError递归深度爆了怎么办最常见的报错是RecursionError: maximum recursion depth exceeded。前面提过Python默认递归深度是1000而快排的递归深度在理想情况下是O(log n)在退化情况下是O(n)。就算用了随机枢轴处理一个十万元素的数组时如果运气稍差递归深度也可能超过1000。排查方法很直接在递归函数入口打印low和high观察递归深度或者用len(inspect.stack())查看当前栈深。更省事的做法是直接设置更大的递归上限。不过要注意setrecursionlimit也不是改得越大越好它受系统栈大小限制设置过大反而可能导致进程异常退出。真正能根治的方案是把递归改成非递归用栈保存待排序区间的起始和结束位置循环处理。这样一来递归深度就不再是限制因素。第6章会给出具体代码。这里先给你一个经验值当数据量超过10万时我一般会放弃递归版本直接上非递归实现省心很多。5.2 大量重复元素退化到O(n²)的真相如果数组里有大量相同元素普通快排会出问题。Lomuto分区用判断时所有等于枢轴的元素会被放到左侧这会让一侧的子数组变得很大另一侧很小递归树失衡。用也一样问题只是换了一侧。处理重复元素最经典的方案是三路分区也就是把整个数组分成小于、等于、大于枢轴的三段。等于枢轴的部分递归时直接跳过只对小于和大于的部分继续排序。这样处理包含大量重复元素的数组时效果立竿见影。三路快排的Python实现大致是这样def quick_sort_three_way(arr, low, high): if low high: return pivot arr[low] lt low gt high 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 quick_sort_three_way(arr, low, lt - 1) quick_sort_three_way(arr, gt 1, high)这是荷兰国旗问题思路的直接应用。实测下来对一个含有大量重复元素的数组三路版比标准版快很多对完全无重复的随机数组两者差距不大。所以如果你的业务数据里重复很多三路分区是我的首推方案。顺带说一句三路快排是面试中排序包含大量重复元素问题的标准答案。面试官看重的不是你会不会背这段代码而是你能不能解释为什么等于枢轴的元素不需要再参与递归排序。想清楚这一点你就理解了为什么三路分区能从根源上解决重复元素的递归膨胀问题。5.3 切片 vs 原地内存开销差多少用left [x for x in arr if x pivot]这种写法每层递归都会创建新的列表对象。以长度为n的数组为例第一层创建约3个列表第二层创建约6个整体呈指数增长。虽然这些列表在递归返回后会被回收但同一时刻存活在内存中的临时列表总长度能达到O(n log n)量级。我之前用切片版快排排序一个20万元素的数组进程的内存占用一路上涨到几百MB而原地版本同样的数据只有几十MB的额外开销。这个对比非常直观地说明Python的列表推导式虽好但不是所有场景都适合拿来做算法核心逻辑。这里还有个隐蔽的问题切片版每次递归都要遍历数组三遍三次列表推导加上拼接操作的复制总比较次数会明显多于原地版本。换句话说它慢得不只是内存CPU时间也更长。如果你在一个处理大数据量的服务里跑切片版快排甚至会让整个服务的常驻内存升高影响其他请求。这也是我不推荐在真实项目里用切片版的原因。5.4 常见问题速查表问题表现排查思路解决方案递归深度超限RecursionError检查数据规模与递归深度设置recursionlimit或改用非递归有序数组变慢排序耗时长、疑似卡死打印分区后左右子数组长度随机枢轴或三数取中重复元素性能退化排序耗时突然增加观察数据中重复元素比例使用三路分区内存占用飙升排序大数组时内存涨到几百MB检查是否使用切片改原地分区版本排序结果不对元素丢失或位置错乱检查递归边界low/high确保区间是low到pi-1、pi1到high随机性导致结果不稳定多次排序耗时波动大检查random调用频率若无必要可用三数取中替代这张表是我在带新人时常用的一张自查清单。每次手写快排出问题先对照现象锁定方向比对着代码瞎猜要快得多。还有一个容易被忽略的点如果排序结果偶尔出错但总是小范围错误优先怀疑分区函数里的交换逻辑如果结果完全乱序优先怀疑递归边界如果只是慢优先怀疑枢轴选择策略。定位思路比记住答案更重要。6. 快排之外和归并排序对比、非递归实现、内置sort的秘密6.1 快速排序 vs 归并排序各自的适用场景归并排序也是O(n log n)的分治排序和快排最大的区别在于归并排序是稳定的而且最坏情况也是O(n log n)。但归并排序需要额外的O(n)空间来合并两个有序数组快排则是在原数组上通过交换完成排序。怎么选如果稳定性是硬性要求——比如按多个字段排序、排行榜需要保序——优先考虑归并排序如果环境内存受限且不需要稳定性快排的原地特性更有优势。Python内置的Timsort本质上是一种优化的归并排序专门利用数据中已有的有序片段所以真实场景下内置sort几乎总是最省心的选择。学习时建议两个都亲自实现一遍。实现归并的过程能帮助你理解合并这步操作的时空复杂度来源实现快排的过程能帮助你理解分区这步操作的交换逻辑。两者互为参照不少面试题正是在这两种排序基础上演化出来的比如如何对链表进行快速排序如何对几乎有序的数组排序想答好这些问题底层思路必须清晰。6.2 非递归实现用栈模拟递归过程前面多次提到用栈来模拟递归这里给出完整实现def quick_sort_iterative(arr, low, high): stack [(low, high)] while stack: low, high stack.pop() if low high: continue pi partition(arr, low, high) if pi - 1 low: stack.append((low, pi - 1)) if pi 1 high: stack.append((pi 1, high)) return arr核心思路是递归函数调用时系统会为每一层保存参数和状态这里手动用一个栈保存需要排序的区间。每次弹出区间先分区再把左右两个新区间压入栈。栈的深度取决于区间的划分情况最坏情况下也会增长到O(n)但至少绕过了Python的递归深度限制。我在实际处理百万级随机数据时非递归版本比递归版本稳定得多也不会因为递归层数过多而报错。代价是代码看起来没有递归版本那么直观。如果你在面试时被要求用非递归实现快排说明面试官很看重你对栈结构的理解这道题的满分答案就是能清晰解释用栈模拟递归的过程。还有一个可以顺手优化的点处理小规模区间时改用插入排序。因为递归或循环分摊到很小区间时继续分区的开销可能高于直接插入排序。工程上很多实现会在high - low 16时切换到插入排序实测能再提升5%到10%的性能。这个优化在面试时提出来也挺加分。6.3 为什么Python内置sort不直接用快速排序Python内置的sorted()和list.sort()使用的是Timsort算法它是一种稳定、自适应的归并排序变体。Timsort会在数据中检测自然运行段已经排好序的子区间并利用这些运行段来减少比较次数因此对真实业务数据往往包含部分有序片段表现得极其高效。Python不直接用快排主要原因是快排不稳定。Python内置排序承诺保证稳定性这是语言层面的语义约束。另外Timsort对最坏情况的处理更有保证复杂度稳定在O(n log n)不会出现快排那种恰好随机到坏枢轴的可能。那快排是不是没用了当然不是。稳定性和最坏情况保证是有代价的归并类排序需要额外O(n)内存。在嵌入式环境、大数组排序但内存很紧张的场合或者算法竞赛里追求极致性能时经过良好优化的快排三数取中三路分区插入排序兜底仍然能发挥重要作用。理解了这两类排序各自的取舍你才能真正看懂语言内置排序的设计哲学——它不只是选一个最快的排序而是在稳定性、内存、性能之间做权衡。说到最后分享一点我的个人体会。我在很长一段时间里也觉得手写排序是重复造轮子直到有一天排查一段流式数据排序代码因为清楚地知道快排的退化条件和稳定性问题才迅速定位到根源那段业务数据在某个时间段内几乎有序而我用的固定枢轴策略正好踩中了最坏分区。改成随机枢轴之后问题当场消失。从那之后我就明白了算法给人的不只是代码本身更是一整套判断问题、权衡方案的思维方式。如果你现在正在学快速排序不妨把分区过程一步步画出来尤其是元素交换那几步画明白了就相当于推开了整个分治思想的大门。