排序这件事写过 Python 的人几乎没有没碰过的面试要被问刷题要用真到项目里又常常发现自己手写的那一份跑不过内置的sorted()。快速排序、归并排序、冒泡排序这三个名字基本就是大部分人接触算法的起点但真正把三份代码都跑一遍、对照着看它们在同样输入下的表现差异其实没多少人做过。我前后在几个项目里被排序坑过——一次是日志按时间片聚合数据本身近乎有序有人用了教科书版快排直接把栈打穿一次是导出报表需要多关键字稳定排序有人图省事自己写了个不稳定的实现导致同分组内顺序每次都变。这些经历让我意识到这三种排序根本不是三个可以互相替换的函数它们代表的是三种完全不同的设计取向选错了不是慢一点的问题是直接出错的问题。下面这份内容适合刚学完算法课想把代码落地的人也适合写了几年业务代码、想把这些底层细节重新捋一遍的人我会把三份实现的完整代码、优化路径、实测数据和踩坑过程都摊开讲。1. 快排、归并、冒泡其实站在三个完全不同的抽象层级上很多人把这三个算法并列记忆觉得它们是同一类东西的三个变种只是效率不同。这个认知会直接导致选型失误。它们在结构上确实都是比较排序都靠元素两两比较来确定次序但解决问题的思路处在完全不同的层次冒泡是枚举式的快排是划分式的归并是合并式的。理解这个差别比背下三段代码重要得多。1.1 先把排序这件事拆成三个可比较的维度我习惯用三个维度来评估任何一个排序实现时间复杂度在什么输入下会变坏、需不需要额外内存、相同元素的相对顺序会不会被打乱。这三个维度直接对应工程里的三种真实约束——数据规模、内存预算、业务语义。冒泡排序在两个维度上都很差最坏和平均都是 O(n²)相等元素不交换所以它是稳定的额外空间 O(1)。它的价值不在性能而在于它是最容易证明正确性的排序——每一轮把最大值冒到末尾这个不变量太直观了写单元测试的时候几乎不会写错边界。快速排序平均 O(n log n)最坏 O(n²)原地排序递归栈除外不稳定。它的强项是常数因子小——同样的 n log n快排的比较次数和内存访问模式对 CPU 缓存最友好因为它在原地不停交换相邻区域的数据访问的都是刚用过的内存。归并排序是三者里唯一能做到最坏也是 O(n log n)的稳定代价是需要 O(n) 的额外空间。它的强项是可预测不管输入长什么样时间都是那个量级不会因为数据分布突然塌方。把这三行摊开看就很清楚了维度冒泡排序快速排序归并排序平均时间O(n²)O(n log n)O(n log n)最坏时间O(n²)O(n²)O(n log n)额外空间O(1)O(log n) 栈O(n)稳定性稳定不稳定稳定对输入分布敏感极敏感敏感不敏感适合的规模几十个元素十万级以内纯 Python需要稳定或链表结构注意表格里适合的规模这一行是纯 Python 实现下的经验值不是说算法本身只能处理这么点数据——换成 C 扩展或者 numpy量级要往上翻两三个数量级。1.2 归并的分完再合和快排的分完就完差在哪一行代码这是我最想让新手停下来想三十秒的地方。两者的递归骨架几乎一模一样都是把数组切成两半递归处理然后返回。区别在于递归调用返回之后做了什么。快排的分区操作发生在递归之前选一个基准值把小于它的扔左边、大于它的扔右边然后对左右两段分别递归。等递归返回的时候什么都不用做了——因为分区那一刻每个元素相对基准的位置就已经是最终位置。所以快排是先干活后递归整个算法里没有合并这个动作。归并正好相反它先把数组一路切到只剩一个元素单个元素天然有序然后在递归返回的路上做合并——把两个已经有序的半段用一个双指针扫一遍拼成一个有序整段。合并这一步是归并排序的全部工作量所在也是最容易写错的地方。这个差异带来一个非常实际的后果快排可以原地做归并几乎不能。因为合并两个有序段的时候你没法保证合并后的结果能直接覆盖回原数组的那段区间而不覆盖还没读的数据所以必须借助一块外部缓冲区。这也是归并排序 O(n) 额外空间的来源不是什么实现技巧问题是算法结构决定的。1.3 为什么 Python 内置的 list.sort() 两个都没选CPython 的list.sort()和sorted()用的是 Timsort一个 2002 年前后成型的混合算法。它做的事情本质上是先扫一遍数组找出天然有序的连续片段run短的用插入排序补齐到一定长度然后用归并的方式把这些 run 两两合并。为什么这么设计因为真实世界的数据几乎从不是完全随机的。从数据库里查出来的记录往往按主键已经大致有序日志按时间追加本身就是有序的用户上传的表格前几千行常常是同一批数据。Timsort 对这类输入的识别能力强到夸张——一个完全有序的 100 万元素列表sorted()几乎是线性扫一遍就返回。而快排对有序输入是最脆弱的下一节会详细说归并虽然稳定但没有利用有序片段的能力。Timsort 相当于把两者的长处拼起来了归并保证了最坏 O(n log n) 和稳定性插入排序保证了小数组上的低开销run 检测保证了对真实数据的自适应。顺带一提Timsort 还有一个归并没有的特性它合并 run 的时候用的是类似栈的结构按固定规则决定合并哪两段避免了一次性开一个和原数组等大的缓冲区——实际内存占用常常只有 n/2 左右。所以尴尬的地方就在这儿你用纯 Python 手写的任何排序性能上都打不过内置的sorted()差距在 20 倍到 50 倍之间因为一个是 C 循环一个是 Python 字节码循环。那我们为什么还要写因为面试要考因为某些场景内置排序用不了比如你排的不是一个完整列表而是链表、或者是流式数据、或者你需要自定义的原地交换语义更因为理解这三份代码是理解为什么内置实现要这么设计的唯一路径。2. 冒泡排序的两处改造让它从教学代码变成能临时救场的工具先讲冒泡因为它是唯一一个优化前后差异巨大、而优化本身又极简单的算法。教科书上那个双重 for 循环版本在我看来属于能跑但不能用的范畴但只需要两处小改动它就能在很多真实场景下变得体面。2.1 双重 for 循环版本在近乎有序数据上为什么还是慢最朴素的写法长这样def bubble_naive(arr): a arr[:] n len(a) for i in range(n - 1): for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] return a问题在于它的循环次数是预先写死的和数据本身的分布完全无关。哪怕你传进来一个已经排好序的列表它依然会老老实实跑完n(n-1)/2次内层迭代一次不少。算一下这个量级n 20000 的时候比较次数是 20000 × 19999 / 2 ≈ 2 亿次。CPython 里一次取值 比较 条件跳转的循环体大概在 60 到 90 纳秒之间2 亿次乘上去就是十几秒。我当时在一个小工具里试过20000 条记录跑了 14 秒多用户直接以为程序卡死了。而这里有个非常讽刺的事实冒泡排序是所有排序里对有序输入最敏感的。因为它的每一次交换都在把逆序对减少一个如果数组本来就有序逆序对数量是 0理论上它应该做 0 次工作才对。问题只出在代码没有把这个性质利用起来。2.2 加一个 swapped 标志能省掉多少轮空转第一处改造是加一个布尔标志记录这一轮有没有发生过交换。如果一整轮下来一次交换都没有说明数组已经有序直接跳出外层循环def bubble_flag(arr): a arr[:] n len(a) for i in range(n - 1): swapped False for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] swapped True if not swapped: break return a就这么三行效果是线性的。一个已经有序的 20000 元素列表改进前 14 秒改进后在我机器上是 0.004 秒左右——因为它只跑一轮内层循环19999 次比较发现没有交换立刻退出。差了 3500 倍。但要注意这个优化只对近乎有序的输入有效。对完全随机的输入几乎每一轮都会有交换标志位永远是 True一点都省不下来甚至因为多了标志位的赋值会稍微慢一点点。所以这个改动不是性能优化是针对特定输入分布的适配。2.3 记最后一次交换位置边界收缩版本的完整写法第二处改造更彻底一点记录每一轮最后一次发生交换的位置下一轮的内层循环只需要扫到这个位置就行。道理很简单如果某一轮里最后一次交换发生在下标 k说明从 k1 到末尾的这段已经完全有序了因为这一轮已经把它们冒上去了下一轮根本没必要再碰。而这个边界往往比n - 1 - i收缩得快得多——极端情况下如果数组只有开头几个元素乱序一轮就能把边界收缩到几乎 0。def bubble_sort(arr): a arr[:] # 复制一份不污染调用方数据 end len(a) - 1 while end 0: last_swap 0 for i in range(end): if a[i] a[i 1]: a[i], a[i 1] a[i 1], a[i] last_swap i end last_swap # 边界直接跳到最后一次交换的位置 return a这里有个细节值得说end last_swap这一句本身就隐含了没有交换就退出的逻辑——如果没有交换last_swap保持初始值 0end变成 0while条件不成立循环自然终止。所以这个版本不需要额外的 swapped 标志一个变量同时承担了边界收缩和提前终止两个职责。这种一个变量干两件事的写法在算法实现里很常见也是代码评审时容易被挑出来的点我自己是倾向于留着但会写一行注释说明。实测下来这个版本在随机数据上比朴素版快 15% 到 25%因为内层循环的右边界在逐步收缩在近乎有序的数据上快出一个数量级。对一个 O(n²) 的算法来说这个改进幅度已经算可观了。2.4 什么情况下我会真的用冒泡说实话纯粹从性能出发没有任何一个场景我应该用冒泡。但有几个边角情况我会考虑它数据量极小且需要绝对可预测的行为比如给 5 个固定配置项排序写一个冒泡比调sorted()更好读也不引入额外的函数调用。教学和代码评审给别人讲什么是不变量的时候冒泡最好讲。硬件资源极度受限且只能做相邻交换的场景有些物理装置比如只能交换相邻槽位的机械结构的模型天然就是冒泡的过程。作为其他算法的子过程Timsort 内部就用了插入排序处理小 run快排的优化版也会在小区间切到插入排序——本质上都是同一个道理小规模时 O(n²) 的算法因为常数因子小反而更快。但注意这里面用的是插入排序不是冒泡因为插入排序的移动次数更少。还有一个我踩过的坑写冒泡的时候一定要记得a arr[:]复制一份。有次我在一个批处理脚本里直接对传入的列表原地排序结果调用方在后面还要用原始顺序数据全乱了排查了快一个小时才定位到。这个教训是通用的——除了明确设计成原地的函数所有排序实现都应该先复制。3. 快速排序在 Python 里最容易踩的三个坑快排是这三者里最容易写出看起来对、实际有隐患的版本。我见过太多人写完一个能通过[3,1,2]测试的快排就以为万事大吉了。3.1 拿第一个元素当基准有序输入直接退化教科书上最常见的选择是取第一个元素当 pivot。这个选择在随机数据上没问题但一旦输入有序或者逆序就会触发最坏情况每次分区后基准值都落在最边上左右两段变成[]和n-1个元素递归深度变成 n。n 20000 时递归深度 20000 层Python 默认递归上限是 1000直接抛RecursionError: maximum recursion depth exceeded in comparison。哪怕你把上限调上去每层的递归调用开销加起来时间复杂度也会退化到 O(n²)——20000 元素差不多要 400 万次比较加上函数调用开销实测跑了两秒多比归并慢了两个数量级。解决办法有几个层次从简单到讲究第一层随机选基准。每次分区前随机交换一下第一个元素和数组里任意一个元素把最坏情况的触发概率压到极低。缺点是随机数生成本身有开销而且要调用random.randint又是函数调用。第二层三数取中。取首、中、尾三个元素的中位数作为基准。这个做法对已经有序和已经逆序这两种最常见的最坏输入都有奇效同时完全不引入随机性行为可复现。我一般用这个。第三层小区间切换插入排序。当子区间长度小于某个阈值我习惯用 16直接调插入排序。原因很实在长度 16 的时候快排要递归 4 层每层有函数调用、分区扫描、边界判断的开销而一次插入排序的内层循环最多 120 次比较纯循环没有函数调用反而更快。这个阈值在不同语言里不一样C 语言里常见的是 8 到 16Python 因为函数调用开销大阈值可以取到 16 甚至 32。3.2 递归栈的深度不是靠 setrecursionlimit 硬撑的很多人遇到RecursionError的第一反应是import sys sys.setrecursionlimit(100000)这个操作很危险。Python 的递归上限保护的不只是你的算法会不会逻辑上无限递归更重要的是保护解释器本身的 C 栈。CPython 的每一层 Python 递归调用都会消耗一段 C 栈空间把上限设到十万一旦真的递归到那么深进程很可能直接段错误崩溃而且崩的时候没有任何 traceback只有一个Segmentation fault排查起来极其痛苦。我在一个数据处理脚本里就被这个坑过设了setrecursionlimit(50000)在本地小数据集上跑得好好的上了生产遇到一批特殊分布的数据进程直接挂了日志里什么都没有。后面是靠二分排查加上手动打印深度才定位到的。正确的做法是控制递归深度本身而不是抬高上限。快排有一个非常优雅的技巧每次递归先处理较短的那一半较长的那一半用循环继续。def _quick(a, lo, hi): while lo hi: if hi - lo 16: _insertion(a, lo, hi) return mid lo (hi - lo) // 2 # 三数取中把 lo / mid / hi 三个位置排好序中位数放到 mid if a[mid] a[lo]: a[mid], a[lo] a[lo], a[mid] if a[hi] a[lo]: a[hi], a[lo] a[lo], a[hi] if a[hi] a[mid]: a[hi], a[mid] a[mid], a[hi] pivot a[mid] i, j lo, hi while i j: while a[i] pivot: i 1 while a[j] pivot: j - 1 if i j: a[i], a[j] a[j], a[i] i 1 j - 1 # 关键先递归短的一侧长的一侧交给 while 循环 if j - lo hi - i: _quick(a, lo, j) lo i else: _quick(a, i, hi) hi j这个改动的效果是递归深度从最坏 O(n) 降到 O(log n)因为每次真正的递归调用处理的区间长度都不超过当前区间的一半。log2(100000) ≈ 17也就是说十万个元素递归深度也不会超过 20 层左右默认的 1000 上限绰绰有余。提示这个技巧不是 Python 专属的任何有递归深度限制的语言都适用但在 Python 里收益特别明显因为 Python 没有尾递归优化递归调用的开销是实打实的。配套的_insertion也很简单注意它是原地操作指定区间def _insertion(a, lo, hi): for i in range(lo 1, hi 1): key a[i] j i - 1 while j lo and a[j] key: a[j 1] a[j] j - 1 a[j 1] key这里用while而不是for因为要边比较边后移for循环不好表达找到位置就停这个逻辑。另外注意条件里是a[j] key而不是用才能保证相等元素的相对顺序不变这样插入排序是稳定的。虽然整体快排不稳定但子过程保持稳定没坏处而且如果你后面要在这个基础上做三路分区这个细节会有用。3.3 大量重复元素下 Lomuto 分区的性能塌方与三路分区上面用的是 Hoare 双指针分区它对重复元素的处理已经比 Lomuto 单指针版本好很多了。但如果你遇到的是大量重复值的数据——比如按状态字段排序几万条记录里只有三五种状态——双指针分区依然会退化。原因是双指针分区把数组分成小于等于 pivot和大于等于 pivot两段中间那一堆等于 pivot 的元素会被均匀地分到两边然后两边各自递归。如果所有元素都相等每次分区后两边还是各占一半递归深度 log n总工作量 n log n看起来还行但实际是每次比较都是相等的比较交换操作一堆常数非常大。更彻底的解法是三路分区荷兰国旗问题把数组分成小于、等于、大于三段等于的那段直接跳过不递归def quick_sort_3way(arr): a arr[:] _q3(a, 0, len(a) - 1) return a def _q3(a, lo, hi): if lo hi: return pivot a[lo] lt, gt, i lo, hi, lo while i gt: if a[i] pivot: a[lt], a[i] a[i], a[lt] lt 1 i 1 elif a[i] pivot: a[i], a[gt] a[gt], a[i] gt - 1 # 注意这里 i 不动换过来的元素还没检查 else: i 1 # 现在 [lo, lt-1] pivot[lt, gt] pivot[gt1, hi] pivot _q3(a, lo, lt - 1) _q3(a, gt 1, hi)gt - 1之后i不能加这是三路分区最容易写错的地方——从右边换过来的元素还没跟 pivot 比较过必须留在原地重新判断。我第一次写的时候就是在这里加了i 1结果数组里有几个元素被跳过排序结果局部乱序测试数据小的时候还看不出来。三路分区在一千个元素里只有五种不同值这种数据上性能提升是数量级的——因为等于 pivot 的那一大段一次就处理完了完全不用递归。同时它在普通随机数据上也不会变慢所以我现在写快排基本都直接上三路分区的版本。4. 归并排序多出来的那块内存买到了什么归并被低估得最厉害。很多人的印象是它比快排慢还费内存然后就再也不看了。但在真实工程里归并出现的频率比想象中高得多。4.1 稳定性不是纸面概念多关键字排序时它会咬人先讲稳定性为什么重要。假设你有一批订单记录需要先按金额排序金额相同再按时间排序。有两种做法做法一是写一个复合比较函数把两个字段一起比。这在 Python 里可以用keylambda o: (o.amount, o.time)一次搞定确实不需要稳定性。做法二是两趟排序先按时间排一遍再按金额排一遍。这只有在第二次排序是稳定的时候才正确——稳定性保证金额相同的那些记录会保持上一趟按时间排好的相对顺序。在 Python 里你可能会说用key元组不就行了。但如果排序发生在数据库外层、或者你要排序的对象来自某个不能预先取出全部字段的接口两趟排序就是唯一的选择。这时候如果你自己写了个不稳定排序结果就是每次运行同一金额的订单顺序都不一样报表看起来在随机跳动。归并排序天然稳定原因在于合并那一步的判断条件if a[i] a[j]取左边用了而不是。当两边元素相等时优先取左边那个左边那一段本来就在原数组里靠前所以相等元素的相对顺序被保留了。就这么一个符号决定了稳定性。快排不稳定因为它有跨距离的交换一次a[i], a[j] a[j], a[i]可能把两个相等元素中的一个甩到很远的位置之后再也回不到原来的相对关系。这不是实现问题是分区操作的固有性质。4.2 自顶向下和自底向上两种写法的开销差在哪归并排序有两种写法我建议都掌握因为它们的适用场景不一样。自顶向下就是常见的递归版写起来最贴合算法描述def merge_sort_topdown(a): if len(a) 1: return a mid len(a) // 2 left merge_sort_topdown(a[:mid]) right merge_sort_topdown(a[mid:]) return _merge_two(left, right) def _merge_two(left, right): out [] append out.append # 局部绑定减少属性查找 i j 0 nl, nr len(left), len(right) while i nl and j nr: if left[i] right[j]: # 保证稳定 append(left[i]) i 1 else: append(right[j]) j 1 if i nl: out.extend(left[i:]) if j nr: out.extend(right[j:]) return out这个版本好看但有两个性能问题。一是a[:mid]和a[mid:]每次递归都产生新的列表n 个元素总共要复制 n log n 次内存分配压力不小。二是递归本身有函数调用开销。实测 20000 个随机数递归版大约 0.06 秒自底向上版 0.042 秒差了 40% 左右。自底向上用迭代代替递归先两两合并再四四合并宽度每次翻倍def merge_sort(arr): n len(arr) a arr[:] if n 1: return a buf [0] * n width 1 while width n: for lo in range(0, n, width * 2): mid min(lo width, n) hi min(lo width * 2, n) _merge_into(a, buf, lo, mid, hi) a, buf buf, a # 交换角色避免每轮重新分配 width * 2 return a def _merge_into(a, buf, lo, mid, hi): i, j, k lo, mid, lo while i mid and j hi: if a[i] a[j]: buf[k] a[i] i 1 else: buf[k] a[j] j 1 k 1 while i mid: buf[k] a[i] i 1 k 1 while j hi: buf[k] a[j] j 1 k 1这个版本只有一个缓冲区a和buf每轮交换角色整个过程只分配一次内存。而且因为是自底向上天然没有递归深度问题。有一个容易忽略的细节合并循环结束后不需要把buf剩余部分清空。因为每一轮_merge_into都会把[lo, hi)这个区间完整地写一遍buf里那个区间的内容全部被覆盖了残留的旧值没有影响。但如果你的hi计算有误某些位置没被写到下一轮就会把上一轮的垃圾数据当成有效值合并进去——这个 bug 极其隐蔽表现是绝大多数情况下正确偶尔有元素错位。我建议写完先用小数据跑一遍带校验的测试import random for _ in range(200): data [random.randint(0, 20) for _ in range(random.randint(0, 40))] assert merge_sort(data) sorted(data), data用带重复元素的小范围随机数据容易撞出边界问题。4.3 合并阶段的三个性能细节归并排序的绝大部分时间花在_merge_into这个内层循环上所以优化都集中在这里。第一局部变量绑定。buf[k] a[i]这样的写法每次都要做两次索引操作和一次属性查找。把列表对象绑到局部变量上CPython 会把它当成局部变量用LOAD_FAST指令访问比LOAD_GLOBAL快。上面的代码里append out.append就是这个思路。第二小数组直接插入排序。和快排一样当归并的子段长度小于 16 的时候递归调用的开销超过收益。自底向上的版本可以从width 16开始先用插入排序把每个 16 元素的小块排好然后再做归并。这个改动能让总时间下降 10% 到 20%。第三提前终止判断。合并之前先检查a[mid - 1] a[mid]如果成立说明左半段的最大值小于等于右半段的最小值整个区间已经有序直接跳过这次合并。对近乎有序的数据这个判断能省掉绝大部分工作量。这个优化在自顶向下的版本里效果更明显因为子段有序的概率更高。def _merge_into(a, buf, lo, mid, hi): if mid hi or a[mid - 1] a[mid]: return # 已经有序省一次合并 # ... 正常合并逻辑注意mid - 1这个下标当mid lo时它会越界取到lo - 1。所以在调用处要保证mid lo或者在函数开头加上if mid lo: return。5. 同机实测四种输入分布下的表现和选型判断讲完原理最重要的还是数据。我搭了一个简单的测试脚本把四种实现放在同一台机器上跑输入是四种典型分布。下面所有数字来自一台普通开发笔记本上的单线程 CPython 3.11每个用例取三次运行的中位数只用来比较量级和相对关系换台机器数字会变但排序关系基本一致。5.1 测试脚本怎么搭才不至于测出假数据先讲怎么测因为这里面的坑比算法本身多。import random, time def bench(fn, data, repeat3): times [] for _ in range(repeat): src data[:] # 每次喂一份新副本 t0 time.perf_counter() out fn(src) times.append(time.perf_counter() - t0) times.sort() return times[len(times) // 2] def make_data(n, kind): if kind random: return [random.randint(0, 10**6) for _ in range(n)] if kind sorted: return list(range(n)) if kind reversed: return list(range(n, 0, -1)) if kind few_unique: return [random.choice([1, 2, 3, 4, 5]) for _ in range(n)]三个必须注意的点第一要验证结果正确性。性能测试之前先拿小数据用assert fn(data) sorted(data)跑一遍。我吃过这个亏——有个快排版本的分区边界写错了在随机数据上恰好能出正确结果测试跑出来的时间还挺好看实际上根本没排对。第二数据生成要在计时之外。random.randint生成 20000 个数本身就要十几毫秒如果混在计时区间里小规模测试的误差会大到没法看。第三别忘了data[:]复制。如果你的实现是原地的第一次跑完数据就排好了第二次跑的是有序数据测出来的时间完全是另一回事。上面bench里每次喂src data[:]就是为了避免这个。5.2 实测结果与解读规模 2000随机数据实现时间秒相对倍数朴素冒泡0.152600x冒泡边界收缩0.131520x插入排序0.058230x快速排序三数取中小区间插入0.00187x归并自底向上0.003514xsorted()0.000251x规模 20000随机数据实现时间秒备注冒泡边界收缩12.8约 2 亿次比较符合 n²/2 推算快速排序0.024归并自底向上0.042sorted()0.0031规模 20000已有序实现时间秒现象朴素冒泡13.4完全不看输入照跑不误冒泡边界收缩0.004一轮结束快排首元素基准抛RecursionError递归深度 20000快排三数取中0.019每次都切在正中间归并自底向上0.038有提前终止判断才降到这个量级sorted()0.0008run 检测直接扫过去规模 20000只有 5 种不同值实现时间秒快排双指针分区0.061快排三路分区0.007归并自底向上0.041这几张表里最值得琢磨的是最后一张。双指针快排在重复值多的数据上比三路分区慢了将近 9 倍而且这个差距会随着重复比例上升继续拉大。而在这张表里三路快排居然比归并快了 6 倍——所以在重复值多这个特定场景下快排依然是赢家前提是你用对了分区方式。5.3 按场景选排序的三条判断线数据摆在这儿选型其实就三条判断线按顺序问自己第一条能不能直接用sorted()能就直接用。它是 C 实现最快稳定最坏 O(n log n)还自带 run 检测。除非你的数据是链表、是流式的、或者有特殊的原地交换需求否则没有任何理由手写排序。我见过太多项目里自己维护了一个几十行的排序函数实际上性能差二十倍还引入了 bug 风险。第二条内存是不是硬约束如果是比如嵌入式、或者数组特别大接近内存上限只能选原地算法快排是唯一的选择代价是失去稳定性。这时候要确保你的分区实现不会退化三数取中、小区间插排、三路分区这三样至少要有前两个。第三条需不需要稳定如果需要稳定且数据不在链表里用归并。如果数据是链表归并反而是最自然的选择——链表归并不需要额外数组合并两个有序链表只要改指针额外空间只有 O(log n) 的递归栈迭代版甚至可以做到 O(1)。链表的归并合并写起来是这样class Node: __slots__ (val, next) def __init__(self, val, nxtNone): self.val val self.next nxt def merge_list(a, b): dummy Node(0) tail dummy while a and b: if a.val b.val: tail.next a a a.next else: tail.next b b b.next tail tail.next tail.next a or b return dummy.nexta or b这一句很 Python含义是如果 a 不为 None 就接 a否则接 b。因为两个链表都是有序的剩下的那一段整体都比已合并的大直接挂上去就行不需要再逐个遍历。6. 面试和代码评审里被问得最多的四个问题最后这一节我整理了几个反复出现的问题不是标准答案是我自己踩过之后形成的理解。这些问题在实际的代码评审里也会出现答得含糊容易被认为只是背过。6.1 快排最坏 O(n²)为什么工程上还偏爱它标准答案会说因为常数因子小、原地、缓存友好。这话对但不够具体。我通常这么解释第一最坏情况是可以规避的。通过随机化基准或者三数取中触发 O(n²) 的输入需要被刻意构造日常数据几乎不可能撞上。而归并的 O(n log n) 是保证但它的常数是实打实的大——每层合并都要读写一遍整个数组内存带宽吃得厉害。第二快排的分区是顺序访问。分区的时候两个指针从两端往中间走访问的都是连续内存CPU 的预取器能有效工作。归并合并的时候是一个指针读左段、一个指针读右段、同时写第三块缓冲区三个数据流来回跳缓存命中率明显低。这就是为什么同样是 n log n快排常数更小。第三快排不需要额外内存。在大数据量下一个 n 大小的缓冲区可能直接把内存打满触发 swap性能断崖式下降。但是——这个偏爱是有前提的。在 Python 里这个前提基本不成立因为纯 Python 的快排怎么优化都跑不过 C 实现的 Timsort。所以如果面试官问的是Python 里用哪个正确答案是sorted()而且要能说清楚 Timsort 的设计思路这比背快排代码更能体现理解深度。6.2 稳定性、原地性、时间复杂度三张表这三个属性经常被混着问我习惯分开记并且记住每个属性的原因而不是结论算法为什么稳定/不稳定为什么原地/不原地冒泡只在a[j] a[j1]时交换相等不换所以稳定只做相邻交换不需要额外空间快速排序分区时有跨距离交换相等元素的相对位置被打乱分区在原数组上完成只有递归栈归并排序合并时用优先取左段相等元素保持原序合并需要独立的输出缓冲区有一个容易记混的点插入排序是稳定的。因为它是把元素逐个插到前面已排序部分的合适位置遇到相等元素时用的是严格大于才后移所以相等元素不会被越过。这也是 Timsort 和快排优化版都选插入排序处理小区间的原因之一——不仅能提速还不破坏稳定性。还有一点值得强调稳定性只对相等元素有意义而相等是由你自己的比较逻辑定义的。如果你排序的对象是字典、自定义类而比较用的是某个字段那么相等指的是那个字段相等其他字段可能完全不同。这一点在做多关键字排序时特别容易出问题——你以为两次排序叠加是稳定的结果第一次的排序键在第二次里被当成相等了顺序就乱了。6.3 递归改写迭代快排好改归并不好改面试里经常有把递归快排改成非递归这种题。快排改写很直接用一个显式的栈保存待处理的区间就行def quick_sort_iter(arr): a arr[:] stack [(0, len(a) - 1)] while stack: lo, hi stack.pop() while lo hi: if hi - lo 16: _insertion(a, lo, hi) break mid lo (hi - lo) // 2 if a[mid] a[lo]: a[mid], a[lo] a[lo], a[mid] if a[hi] a[lo]: a[hi], a[lo] a[lo], a[hi] if a[hi] a[mid]: a[hi], a[mid] a[mid], a[hi] pivot a[mid] i, j lo, hi while i j: while a[i] pivot: i 1 while a[j] pivot: j - 1 if i j: a[i], a[j] a[j], a[i] i 1 j - 1 # 短的一侧压栈长的一侧继续循环 if j - lo hi - i: if i hi: stack.append((i, hi)) hi j else: if lo j: stack.append((lo, j)) lo i return a注意这里依然保留了短边压栈、长边循环的策略如果不这么做栈的深度会退化成 O(n)用显式栈和用递归栈就没区别了只是把崩溃点从RecursionError变成了内存耗尽。归并排序改成迭代就自然多了——自底向上的版本本身就是迭代的这也是我推荐优先掌握它的原因。反过来如果你手上只有递归版归并想改成迭代其实就是把递归的分解顺序翻译成按宽度递增的循环思路很清晰。最后分享一个我在实际项目里的体会不要试图用纯 Python 手写排序去优化性能瓶颈。如果你的 profiling 显示排序占了 30% 以上的时间正确的方向不是把冒泡改成快排而是换数据结构用堆、用有序容器、换工具numpy 的sort、数据库的ORDER BY、或者减少需要排序的数据量先过滤再排序。手写排序的真正价值在于理解算法行为和边界条件在于能读懂别人代码里的排序逻辑在于面试时能讲清楚为什么而不是把那几十行代码塞进生产环境。我在一个报表导出功能里做过对比把自研的快排换成sorted(key...)之后整体耗时从 4.2 秒降到 0.3 秒改动量只有三行——那三行代码比任何算法优化都值钱。 
长河君 · 2026/10/28 20:03:49 · 阅读 1.2k Python排序算法实战：快排、归并、冒泡的实现优化与选型
排序这件事写过 Python 的人几乎没有没碰过的面试要被问刷题要用真到项目里又常常发现自己手写的那一份跑不过内置的sorted()。快速排序、归并排序、冒泡排序这三个名字基本就是大部分人接触算法的起点但真正把三份代码都跑一遍、对照着看它们在同样输入下的表现差异其实没多少人做过。我前后在几个项目里被排序坑过——一次是日志按时间片聚合数据本身近乎有序有人用了教科书版快排直接把栈打穿一次是导出报表需要多关键字稳定排序有人图省事自己写了个不稳定的实现导致同分组内顺序每次都变。这些经历让我意识到这三种排序根本不是三个可以互相替换的函数它们代表的是三种完全不同的设计取向选错了不是慢一点的问题是直接出错的问题。下面这份内容适合刚学完算法课想把代码落地的人也适合写了几年业务代码、想把这些底层细节重新捋一遍的人我会把三份实现的完整代码、优化路径、实测数据和踩坑过程都摊开讲。1. 快排、归并、冒泡其实站在三个完全不同的抽象层级上很多人把这三个算法并列记忆觉得它们是同一类东西的三个变种只是效率不同。这个认知会直接导致选型失误。它们在结构上确实都是比较排序都靠元素两两比较来确定次序但解决问题的思路处在完全不同的层次冒泡是枚举式的快排是划分式的归并是合并式的。理解这个差别比背下三段代码重要得多。1.1 先把排序这件事拆成三个可比较的维度我习惯用三个维度来评估任何一个排序实现时间复杂度在什么输入下会变坏、需不需要额外内存、相同元素的相对顺序会不会被打乱。这三个维度直接对应工程里的三种真实约束——数据规模、内存预算、业务语义。冒泡排序在两个维度上都很差最坏和平均都是 O(n²)相等元素不交换所以它是稳定的额外空间 O(1)。它的价值不在性能而在于它是最容易证明正确性的排序——每一轮把最大值冒到末尾这个不变量太直观了写单元测试的时候几乎不会写错边界。快速排序平均 O(n log n)最坏 O(n²)原地排序递归栈除外不稳定。它的强项是常数因子小——同样的 n log n快排的比较次数和内存访问模式对 CPU 缓存最友好因为它在原地不停交换相邻区域的数据访问的都是刚用过的内存。归并排序是三者里唯一能做到最坏也是 O(n log n)的稳定代价是需要 O(n) 的额外空间。它的强项是可预测不管输入长什么样时间都是那个量级不会因为数据分布突然塌方。把这三行摊开看就很清楚了维度冒泡排序快速排序归并排序平均时间O(n²)O(n log n)O(n log n)最坏时间O(n²)O(n²)O(n log n)额外空间O(1)O(log n) 栈O(n)稳定性稳定不稳定稳定对输入分布敏感极敏感敏感不敏感适合的规模几十个元素十万级以内纯 Python需要稳定或链表结构注意表格里适合的规模这一行是纯 Python 实现下的经验值不是说算法本身只能处理这么点数据——换成 C 扩展或者 numpy量级要往上翻两三个数量级。1.2 归并的分完再合和快排的分完就完差在哪一行代码这是我最想让新手停下来想三十秒的地方。两者的递归骨架几乎一模一样都是把数组切成两半递归处理然后返回。区别在于递归调用返回之后做了什么。快排的分区操作发生在递归之前选一个基准值把小于它的扔左边、大于它的扔右边然后对左右两段分别递归。等递归返回的时候什么都不用做了——因为分区那一刻每个元素相对基准的位置就已经是最终位置。所以快排是先干活后递归整个算法里没有合并这个动作。归并正好相反它先把数组一路切到只剩一个元素单个元素天然有序然后在递归返回的路上做合并——把两个已经有序的半段用一个双指针扫一遍拼成一个有序整段。合并这一步是归并排序的全部工作量所在也是最容易写错的地方。这个差异带来一个非常实际的后果快排可以原地做归并几乎不能。因为合并两个有序段的时候你没法保证合并后的结果能直接覆盖回原数组的那段区间而不覆盖还没读的数据所以必须借助一块外部缓冲区。这也是归并排序 O(n) 额外空间的来源不是什么实现技巧问题是算法结构决定的。1.3 为什么 Python 内置的 list.sort() 两个都没选CPython 的list.sort()和sorted()用的是 Timsort一个 2002 年前后成型的混合算法。它做的事情本质上是先扫一遍数组找出天然有序的连续片段run短的用插入排序补齐到一定长度然后用归并的方式把这些 run 两两合并。为什么这么设计因为真实世界的数据几乎从不是完全随机的。从数据库里查出来的记录往往按主键已经大致有序日志按时间追加本身就是有序的用户上传的表格前几千行常常是同一批数据。Timsort 对这类输入的识别能力强到夸张——一个完全有序的 100 万元素列表sorted()几乎是线性扫一遍就返回。而快排对有序输入是最脆弱的下一节会详细说归并虽然稳定但没有利用有序片段的能力。Timsort 相当于把两者的长处拼起来了归并保证了最坏 O(n log n) 和稳定性插入排序保证了小数组上的低开销run 检测保证了对真实数据的自适应。顺带一提Timsort 还有一个归并没有的特性它合并 run 的时候用的是类似栈的结构按固定规则决定合并哪两段避免了一次性开一个和原数组等大的缓冲区——实际内存占用常常只有 n/2 左右。所以尴尬的地方就在这儿你用纯 Python 手写的任何排序性能上都打不过内置的sorted()差距在 20 倍到 50 倍之间因为一个是 C 循环一个是 Python 字节码循环。那我们为什么还要写因为面试要考因为某些场景内置排序用不了比如你排的不是一个完整列表而是链表、或者是流式数据、或者你需要自定义的原地交换语义更因为理解这三份代码是理解为什么内置实现要这么设计的唯一路径。2. 冒泡排序的两处改造让它从教学代码变成能临时救场的工具先讲冒泡因为它是唯一一个优化前后差异巨大、而优化本身又极简单的算法。教科书上那个双重 for 循环版本在我看来属于能跑但不能用的范畴但只需要两处小改动它就能在很多真实场景下变得体面。2.1 双重 for 循环版本在近乎有序数据上为什么还是慢最朴素的写法长这样def bubble_naive(arr): a arr[:] n len(a) for i in range(n - 1): for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] return a问题在于它的循环次数是预先写死的和数据本身的分布完全无关。哪怕你传进来一个已经排好序的列表它依然会老老实实跑完n(n-1)/2次内层迭代一次不少。算一下这个量级n 20000 的时候比较次数是 20000 × 19999 / 2 ≈ 2 亿次。CPython 里一次取值 比较 条件跳转的循环体大概在 60 到 90 纳秒之间2 亿次乘上去就是十几秒。我当时在一个小工具里试过20000 条记录跑了 14 秒多用户直接以为程序卡死了。而这里有个非常讽刺的事实冒泡排序是所有排序里对有序输入最敏感的。因为它的每一次交换都在把逆序对减少一个如果数组本来就有序逆序对数量是 0理论上它应该做 0 次工作才对。问题只出在代码没有把这个性质利用起来。2.2 加一个 swapped 标志能省掉多少轮空转第一处改造是加一个布尔标志记录这一轮有没有发生过交换。如果一整轮下来一次交换都没有说明数组已经有序直接跳出外层循环def bubble_flag(arr): a arr[:] n len(a) for i in range(n - 1): swapped False for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] swapped True if not swapped: break return a就这么三行效果是线性的。一个已经有序的 20000 元素列表改进前 14 秒改进后在我机器上是 0.004 秒左右——因为它只跑一轮内层循环19999 次比较发现没有交换立刻退出。差了 3500 倍。但要注意这个优化只对近乎有序的输入有效。对完全随机的输入几乎每一轮都会有交换标志位永远是 True一点都省不下来甚至因为多了标志位的赋值会稍微慢一点点。所以这个改动不是性能优化是针对特定输入分布的适配。2.3 记最后一次交换位置边界收缩版本的完整写法第二处改造更彻底一点记录每一轮最后一次发生交换的位置下一轮的内层循环只需要扫到这个位置就行。道理很简单如果某一轮里最后一次交换发生在下标 k说明从 k1 到末尾的这段已经完全有序了因为这一轮已经把它们冒上去了下一轮根本没必要再碰。而这个边界往往比n - 1 - i收缩得快得多——极端情况下如果数组只有开头几个元素乱序一轮就能把边界收缩到几乎 0。def bubble_sort(arr): a arr[:] # 复制一份不污染调用方数据 end len(a) - 1 while end 0: last_swap 0 for i in range(end): if a[i] a[i 1]: a[i], a[i 1] a[i 1], a[i] last_swap i end last_swap # 边界直接跳到最后一次交换的位置 return a这里有个细节值得说end last_swap这一句本身就隐含了没有交换就退出的逻辑——如果没有交换last_swap保持初始值 0end变成 0while条件不成立循环自然终止。所以这个版本不需要额外的 swapped 标志一个变量同时承担了边界收缩和提前终止两个职责。这种一个变量干两件事的写法在算法实现里很常见也是代码评审时容易被挑出来的点我自己是倾向于留着但会写一行注释说明。实测下来这个版本在随机数据上比朴素版快 15% 到 25%因为内层循环的右边界在逐步收缩在近乎有序的数据上快出一个数量级。对一个 O(n²) 的算法来说这个改进幅度已经算可观了。2.4 什么情况下我会真的用冒泡说实话纯粹从性能出发没有任何一个场景我应该用冒泡。但有几个边角情况我会考虑它数据量极小且需要绝对可预测的行为比如给 5 个固定配置项排序写一个冒泡比调sorted()更好读也不引入额外的函数调用。教学和代码评审给别人讲什么是不变量的时候冒泡最好讲。硬件资源极度受限且只能做相邻交换的场景有些物理装置比如只能交换相邻槽位的机械结构的模型天然就是冒泡的过程。作为其他算法的子过程Timsort 内部就用了插入排序处理小 run快排的优化版也会在小区间切到插入排序——本质上都是同一个道理小规模时 O(n²) 的算法因为常数因子小反而更快。但注意这里面用的是插入排序不是冒泡因为插入排序的移动次数更少。还有一个我踩过的坑写冒泡的时候一定要记得a arr[:]复制一份。有次我在一个批处理脚本里直接对传入的列表原地排序结果调用方在后面还要用原始顺序数据全乱了排查了快一个小时才定位到。这个教训是通用的——除了明确设计成原地的函数所有排序实现都应该先复制。3. 快速排序在 Python 里最容易踩的三个坑快排是这三者里最容易写出看起来对、实际有隐患的版本。我见过太多人写完一个能通过[3,1,2]测试的快排就以为万事大吉了。3.1 拿第一个元素当基准有序输入直接退化教科书上最常见的选择是取第一个元素当 pivot。这个选择在随机数据上没问题但一旦输入有序或者逆序就会触发最坏情况每次分区后基准值都落在最边上左右两段变成[]和n-1个元素递归深度变成 n。n 20000 时递归深度 20000 层Python 默认递归上限是 1000直接抛RecursionError: maximum recursion depth exceeded in comparison。哪怕你把上限调上去每层的递归调用开销加起来时间复杂度也会退化到 O(n²)——20000 元素差不多要 400 万次比较加上函数调用开销实测跑了两秒多比归并慢了两个数量级。解决办法有几个层次从简单到讲究第一层随机选基准。每次分区前随机交换一下第一个元素和数组里任意一个元素把最坏情况的触发概率压到极低。缺点是随机数生成本身有开销而且要调用random.randint又是函数调用。第二层三数取中。取首、中、尾三个元素的中位数作为基准。这个做法对已经有序和已经逆序这两种最常见的最坏输入都有奇效同时完全不引入随机性行为可复现。我一般用这个。第三层小区间切换插入排序。当子区间长度小于某个阈值我习惯用 16直接调插入排序。原因很实在长度 16 的时候快排要递归 4 层每层有函数调用、分区扫描、边界判断的开销而一次插入排序的内层循环最多 120 次比较纯循环没有函数调用反而更快。这个阈值在不同语言里不一样C 语言里常见的是 8 到 16Python 因为函数调用开销大阈值可以取到 16 甚至 32。3.2 递归栈的深度不是靠 setrecursionlimit 硬撑的很多人遇到RecursionError的第一反应是import sys sys.setrecursionlimit(100000)这个操作很危险。Python 的递归上限保护的不只是你的算法会不会逻辑上无限递归更重要的是保护解释器本身的 C 栈。CPython 的每一层 Python 递归调用都会消耗一段 C 栈空间把上限设到十万一旦真的递归到那么深进程很可能直接段错误崩溃而且崩的时候没有任何 traceback只有一个Segmentation fault排查起来极其痛苦。我在一个数据处理脚本里就被这个坑过设了setrecursionlimit(50000)在本地小数据集上跑得好好的上了生产遇到一批特殊分布的数据进程直接挂了日志里什么都没有。后面是靠二分排查加上手动打印深度才定位到的。正确的做法是控制递归深度本身而不是抬高上限。快排有一个非常优雅的技巧每次递归先处理较短的那一半较长的那一半用循环继续。def _quick(a, lo, hi): while lo hi: if hi - lo 16: _insertion(a, lo, hi) return mid lo (hi - lo) // 2 # 三数取中把 lo / mid / hi 三个位置排好序中位数放到 mid if a[mid] a[lo]: a[mid], a[lo] a[lo], a[mid] if a[hi] a[lo]: a[hi], a[lo] a[lo], a[hi] if a[hi] a[mid]: a[hi], a[mid] a[mid], a[hi] pivot a[mid] i, j lo, hi while i j: while a[i] pivot: i 1 while a[j] pivot: j - 1 if i j: a[i], a[j] a[j], a[i] i 1 j - 1 # 关键先递归短的一侧长的一侧交给 while 循环 if j - lo hi - i: _quick(a, lo, j) lo i else: _quick(a, i, hi) hi j这个改动的效果是递归深度从最坏 O(n) 降到 O(log n)因为每次真正的递归调用处理的区间长度都不超过当前区间的一半。log2(100000) ≈ 17也就是说十万个元素递归深度也不会超过 20 层左右默认的 1000 上限绰绰有余。提示这个技巧不是 Python 专属的任何有递归深度限制的语言都适用但在 Python 里收益特别明显因为 Python 没有尾递归优化递归调用的开销是实打实的。配套的_insertion也很简单注意它是原地操作指定区间def _insertion(a, lo, hi): for i in range(lo 1, hi 1): key a[i] j i - 1 while j lo and a[j] key: a[j 1] a[j] j - 1 a[j 1] key这里用while而不是for因为要边比较边后移for循环不好表达找到位置就停这个逻辑。另外注意条件里是a[j] key而不是用才能保证相等元素的相对顺序不变这样插入排序是稳定的。虽然整体快排不稳定但子过程保持稳定没坏处而且如果你后面要在这个基础上做三路分区这个细节会有用。3.3 大量重复元素下 Lomuto 分区的性能塌方与三路分区上面用的是 Hoare 双指针分区它对重复元素的处理已经比 Lomuto 单指针版本好很多了。但如果你遇到的是大量重复值的数据——比如按状态字段排序几万条记录里只有三五种状态——双指针分区依然会退化。原因是双指针分区把数组分成小于等于 pivot和大于等于 pivot两段中间那一堆等于 pivot 的元素会被均匀地分到两边然后两边各自递归。如果所有元素都相等每次分区后两边还是各占一半递归深度 log n总工作量 n log n看起来还行但实际是每次比较都是相等的比较交换操作一堆常数非常大。更彻底的解法是三路分区荷兰国旗问题把数组分成小于、等于、大于三段等于的那段直接跳过不递归def quick_sort_3way(arr): a arr[:] _q3(a, 0, len(a) - 1) return a def _q3(a, lo, hi): if lo hi: return pivot a[lo] lt, gt, i lo, hi, lo while i gt: if a[i] pivot: a[lt], a[i] a[i], a[lt] lt 1 i 1 elif a[i] pivot: a[i], a[gt] a[gt], a[i] gt - 1 # 注意这里 i 不动换过来的元素还没检查 else: i 1 # 现在 [lo, lt-1] pivot[lt, gt] pivot[gt1, hi] pivot _q3(a, lo, lt - 1) _q3(a, gt 1, hi)gt - 1之后i不能加这是三路分区最容易写错的地方——从右边换过来的元素还没跟 pivot 比较过必须留在原地重新判断。我第一次写的时候就是在这里加了i 1结果数组里有几个元素被跳过排序结果局部乱序测试数据小的时候还看不出来。三路分区在一千个元素里只有五种不同值这种数据上性能提升是数量级的——因为等于 pivot 的那一大段一次就处理完了完全不用递归。同时它在普通随机数据上也不会变慢所以我现在写快排基本都直接上三路分区的版本。4. 归并排序多出来的那块内存买到了什么归并被低估得最厉害。很多人的印象是它比快排慢还费内存然后就再也不看了。但在真实工程里归并出现的频率比想象中高得多。4.1 稳定性不是纸面概念多关键字排序时它会咬人先讲稳定性为什么重要。假设你有一批订单记录需要先按金额排序金额相同再按时间排序。有两种做法做法一是写一个复合比较函数把两个字段一起比。这在 Python 里可以用keylambda o: (o.amount, o.time)一次搞定确实不需要稳定性。做法二是两趟排序先按时间排一遍再按金额排一遍。这只有在第二次排序是稳定的时候才正确——稳定性保证金额相同的那些记录会保持上一趟按时间排好的相对顺序。在 Python 里你可能会说用key元组不就行了。但如果排序发生在数据库外层、或者你要排序的对象来自某个不能预先取出全部字段的接口两趟排序就是唯一的选择。这时候如果你自己写了个不稳定排序结果就是每次运行同一金额的订单顺序都不一样报表看起来在随机跳动。归并排序天然稳定原因在于合并那一步的判断条件if a[i] a[j]取左边用了而不是。当两边元素相等时优先取左边那个左边那一段本来就在原数组里靠前所以相等元素的相对顺序被保留了。就这么一个符号决定了稳定性。快排不稳定因为它有跨距离的交换一次a[i], a[j] a[j], a[i]可能把两个相等元素中的一个甩到很远的位置之后再也回不到原来的相对关系。这不是实现问题是分区操作的固有性质。4.2 自顶向下和自底向上两种写法的开销差在哪归并排序有两种写法我建议都掌握因为它们的适用场景不一样。自顶向下就是常见的递归版写起来最贴合算法描述def merge_sort_topdown(a): if len(a) 1: return a mid len(a) // 2 left merge_sort_topdown(a[:mid]) right merge_sort_topdown(a[mid:]) return _merge_two(left, right) def _merge_two(left, right): out [] append out.append # 局部绑定减少属性查找 i j 0 nl, nr len(left), len(right) while i nl and j nr: if left[i] right[j]: # 保证稳定 append(left[i]) i 1 else: append(right[j]) j 1 if i nl: out.extend(left[i:]) if j nr: out.extend(right[j:]) return out这个版本好看但有两个性能问题。一是a[:mid]和a[mid:]每次递归都产生新的列表n 个元素总共要复制 n log n 次内存分配压力不小。二是递归本身有函数调用开销。实测 20000 个随机数递归版大约 0.06 秒自底向上版 0.042 秒差了 40% 左右。自底向上用迭代代替递归先两两合并再四四合并宽度每次翻倍def merge_sort(arr): n len(arr) a arr[:] if n 1: return a buf [0] * n width 1 while width n: for lo in range(0, n, width * 2): mid min(lo width, n) hi min(lo width * 2, n) _merge_into(a, buf, lo, mid, hi) a, buf buf, a # 交换角色避免每轮重新分配 width * 2 return a def _merge_into(a, buf, lo, mid, hi): i, j, k lo, mid, lo while i mid and j hi: if a[i] a[j]: buf[k] a[i] i 1 else: buf[k] a[j] j 1 k 1 while i mid: buf[k] a[i] i 1 k 1 while j hi: buf[k] a[j] j 1 k 1这个版本只有一个缓冲区a和buf每轮交换角色整个过程只分配一次内存。而且因为是自底向上天然没有递归深度问题。有一个容易忽略的细节合并循环结束后不需要把buf剩余部分清空。因为每一轮_merge_into都会把[lo, hi)这个区间完整地写一遍buf里那个区间的内容全部被覆盖了残留的旧值没有影响。但如果你的hi计算有误某些位置没被写到下一轮就会把上一轮的垃圾数据当成有效值合并进去——这个 bug 极其隐蔽表现是绝大多数情况下正确偶尔有元素错位。我建议写完先用小数据跑一遍带校验的测试import random for _ in range(200): data [random.randint(0, 20) for _ in range(random.randint(0, 40))] assert merge_sort(data) sorted(data), data用带重复元素的小范围随机数据容易撞出边界问题。4.3 合并阶段的三个性能细节归并排序的绝大部分时间花在_merge_into这个内层循环上所以优化都集中在这里。第一局部变量绑定。buf[k] a[i]这样的写法每次都要做两次索引操作和一次属性查找。把列表对象绑到局部变量上CPython 会把它当成局部变量用LOAD_FAST指令访问比LOAD_GLOBAL快。上面的代码里append out.append就是这个思路。第二小数组直接插入排序。和快排一样当归并的子段长度小于 16 的时候递归调用的开销超过收益。自底向上的版本可以从width 16开始先用插入排序把每个 16 元素的小块排好然后再做归并。这个改动能让总时间下降 10% 到 20%。第三提前终止判断。合并之前先检查a[mid - 1] a[mid]如果成立说明左半段的最大值小于等于右半段的最小值整个区间已经有序直接跳过这次合并。对近乎有序的数据这个判断能省掉绝大部分工作量。这个优化在自顶向下的版本里效果更明显因为子段有序的概率更高。def _merge_into(a, buf, lo, mid, hi): if mid hi or a[mid - 1] a[mid]: return # 已经有序省一次合并 # ... 正常合并逻辑注意mid - 1这个下标当mid lo时它会越界取到lo - 1。所以在调用处要保证mid lo或者在函数开头加上if mid lo: return。5. 同机实测四种输入分布下的表现和选型判断讲完原理最重要的还是数据。我搭了一个简单的测试脚本把四种实现放在同一台机器上跑输入是四种典型分布。下面所有数字来自一台普通开发笔记本上的单线程 CPython 3.11每个用例取三次运行的中位数只用来比较量级和相对关系换台机器数字会变但排序关系基本一致。5.1 测试脚本怎么搭才不至于测出假数据先讲怎么测因为这里面的坑比算法本身多。import random, time def bench(fn, data, repeat3): times [] for _ in range(repeat): src data[:] # 每次喂一份新副本 t0 time.perf_counter() out fn(src) times.append(time.perf_counter() - t0) times.sort() return times[len(times) // 2] def make_data(n, kind): if kind random: return [random.randint(0, 10**6) for _ in range(n)] if kind sorted: return list(range(n)) if kind reversed: return list(range(n, 0, -1)) if kind few_unique: return [random.choice([1, 2, 3, 4, 5]) for _ in range(n)]三个必须注意的点第一要验证结果正确性。性能测试之前先拿小数据用assert fn(data) sorted(data)跑一遍。我吃过这个亏——有个快排版本的分区边界写错了在随机数据上恰好能出正确结果测试跑出来的时间还挺好看实际上根本没排对。第二数据生成要在计时之外。random.randint生成 20000 个数本身就要十几毫秒如果混在计时区间里小规模测试的误差会大到没法看。第三别忘了data[:]复制。如果你的实现是原地的第一次跑完数据就排好了第二次跑的是有序数据测出来的时间完全是另一回事。上面bench里每次喂src data[:]就是为了避免这个。5.2 实测结果与解读规模 2000随机数据实现时间秒相对倍数朴素冒泡0.152600x冒泡边界收缩0.131520x插入排序0.058230x快速排序三数取中小区间插入0.00187x归并自底向上0.003514xsorted()0.000251x规模 20000随机数据实现时间秒备注冒泡边界收缩12.8约 2 亿次比较符合 n²/2 推算快速排序0.024归并自底向上0.042sorted()0.0031规模 20000已有序实现时间秒现象朴素冒泡13.4完全不看输入照跑不误冒泡边界收缩0.004一轮结束快排首元素基准抛RecursionError递归深度 20000快排三数取中0.019每次都切在正中间归并自底向上0.038有提前终止判断才降到这个量级sorted()0.0008run 检测直接扫过去规模 20000只有 5 种不同值实现时间秒快排双指针分区0.061快排三路分区0.007归并自底向上0.041这几张表里最值得琢磨的是最后一张。双指针快排在重复值多的数据上比三路分区慢了将近 9 倍而且这个差距会随着重复比例上升继续拉大。而在这张表里三路快排居然比归并快了 6 倍——所以在重复值多这个特定场景下快排依然是赢家前提是你用对了分区方式。5.3 按场景选排序的三条判断线数据摆在这儿选型其实就三条判断线按顺序问自己第一条能不能直接用sorted()能就直接用。它是 C 实现最快稳定最坏 O(n log n)还自带 run 检测。除非你的数据是链表、是流式的、或者有特殊的原地交换需求否则没有任何理由手写排序。我见过太多项目里自己维护了一个几十行的排序函数实际上性能差二十倍还引入了 bug 风险。第二条内存是不是硬约束如果是比如嵌入式、或者数组特别大接近内存上限只能选原地算法快排是唯一的选择代价是失去稳定性。这时候要确保你的分区实现不会退化三数取中、小区间插排、三路分区这三样至少要有前两个。第三条需不需要稳定如果需要稳定且数据不在链表里用归并。如果数据是链表归并反而是最自然的选择——链表归并不需要额外数组合并两个有序链表只要改指针额外空间只有 O(log n) 的递归栈迭代版甚至可以做到 O(1)。链表的归并合并写起来是这样class Node: __slots__ (val, next) def __init__(self, val, nxtNone): self.val val self.next nxt def merge_list(a, b): dummy Node(0) tail dummy while a and b: if a.val b.val: tail.next a a a.next else: tail.next b b b.next tail tail.next tail.next a or b return dummy.nexta or b这一句很 Python含义是如果 a 不为 None 就接 a否则接 b。因为两个链表都是有序的剩下的那一段整体都比已合并的大直接挂上去就行不需要再逐个遍历。6. 面试和代码评审里被问得最多的四个问题最后这一节我整理了几个反复出现的问题不是标准答案是我自己踩过之后形成的理解。这些问题在实际的代码评审里也会出现答得含糊容易被认为只是背过。6.1 快排最坏 O(n²)为什么工程上还偏爱它标准答案会说因为常数因子小、原地、缓存友好。这话对但不够具体。我通常这么解释第一最坏情况是可以规避的。通过随机化基准或者三数取中触发 O(n²) 的输入需要被刻意构造日常数据几乎不可能撞上。而归并的 O(n log n) 是保证但它的常数是实打实的大——每层合并都要读写一遍整个数组内存带宽吃得厉害。第二快排的分区是顺序访问。分区的时候两个指针从两端往中间走访问的都是连续内存CPU 的预取器能有效工作。归并合并的时候是一个指针读左段、一个指针读右段、同时写第三块缓冲区三个数据流来回跳缓存命中率明显低。这就是为什么同样是 n log n快排常数更小。第三快排不需要额外内存。在大数据量下一个 n 大小的缓冲区可能直接把内存打满触发 swap性能断崖式下降。但是——这个偏爱是有前提的。在 Python 里这个前提基本不成立因为纯 Python 的快排怎么优化都跑不过 C 实现的 Timsort。所以如果面试官问的是Python 里用哪个正确答案是sorted()而且要能说清楚 Timsort 的设计思路这比背快排代码更能体现理解深度。6.2 稳定性、原地性、时间复杂度三张表这三个属性经常被混着问我习惯分开记并且记住每个属性的原因而不是结论算法为什么稳定/不稳定为什么原地/不原地冒泡只在a[j] a[j1]时交换相等不换所以稳定只做相邻交换不需要额外空间快速排序分区时有跨距离交换相等元素的相对位置被打乱分区在原数组上完成只有递归栈归并排序合并时用优先取左段相等元素保持原序合并需要独立的输出缓冲区有一个容易记混的点插入排序是稳定的。因为它是把元素逐个插到前面已排序部分的合适位置遇到相等元素时用的是严格大于才后移所以相等元素不会被越过。这也是 Timsort 和快排优化版都选插入排序处理小区间的原因之一——不仅能提速还不破坏稳定性。还有一点值得强调稳定性只对相等元素有意义而相等是由你自己的比较逻辑定义的。如果你排序的对象是字典、自定义类而比较用的是某个字段那么相等指的是那个字段相等其他字段可能完全不同。这一点在做多关键字排序时特别容易出问题——你以为两次排序叠加是稳定的结果第一次的排序键在第二次里被当成相等了顺序就乱了。6.3 递归改写迭代快排好改归并不好改面试里经常有把递归快排改成非递归这种题。快排改写很直接用一个显式的栈保存待处理的区间就行def quick_sort_iter(arr): a arr[:] stack [(0, len(a) - 1)] while stack: lo, hi stack.pop() while lo hi: if hi - lo 16: _insertion(a, lo, hi) break mid lo (hi - lo) // 2 if a[mid] a[lo]: a[mid], a[lo] a[lo], a[mid] if a[hi] a[lo]: a[hi], a[lo] a[lo], a[hi] if a[hi] a[mid]: a[hi], a[mid] a[mid], a[hi] pivot a[mid] i, j lo, hi while i j: while a[i] pivot: i 1 while a[j] pivot: j - 1 if i j: a[i], a[j] a[j], a[i] i 1 j - 1 # 短的一侧压栈长的一侧继续循环 if j - lo hi - i: if i hi: stack.append((i, hi)) hi j else: if lo j: stack.append((lo, j)) lo i return a注意这里依然保留了短边压栈、长边循环的策略如果不这么做栈的深度会退化成 O(n)用显式栈和用递归栈就没区别了只是把崩溃点从RecursionError变成了内存耗尽。归并排序改成迭代就自然多了——自底向上的版本本身就是迭代的这也是我推荐优先掌握它的原因。反过来如果你手上只有递归版归并想改成迭代其实就是把递归的分解顺序翻译成按宽度递增的循环思路很清晰。最后分享一个我在实际项目里的体会不要试图用纯 Python 手写排序去优化性能瓶颈。如果你的 profiling 显示排序占了 30% 以上的时间正确的方向不是把冒泡改成快排而是换数据结构用堆、用有序容器、换工具numpy 的sort、数据库的ORDER BY、或者减少需要排序的数据量先过滤再排序。手写排序的真正价值在于理解算法行为和边界条件在于能读懂别人代码里的排序逻辑在于面试时能讲清楚为什么而不是把那几十行代码塞进生产环境。我在一个报表导出功能里做过对比把自研的快排换成sorted(key...)之后整体耗时从 4.2 秒降到 0.3 秒改动量只有三行——那三行代码比任何算法优化都值钱。