企业官网建设流程全解析

排序这件事，写过 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) 的额外空间。它的强项是可预测：不管输入长什么样，时间都是那个量级，不会因为数据分布突然塌方。

把这三行摊开看就很清楚了：

注意：表格里"适合的规模"这一行是纯 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，说明从 k+1 到末尾的这段已经完全有序了（因为这一轮已经把它们冒上去了），下一轮根本没必要再碰。而这个边界往往比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保持初始值 0，end变成 0，while条件不成立，循环自然终止。所以这个版本不需要额外的 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 到 16，Python 因为函数调用开销大，阈值可以取到 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，[gt+1, hi] > pivot _q3(a, lo, lt - 1) _q3(a, gt + 1, hi)

gt -= 1之后i不能加，这是三路分区最容易写错的地方——从右边换过来的元素还没跟 pivot 比较过，必须留在原地重新判断。我第一次写的时候就是在这里加了i += 1，结果数组里有几个元素被跳过，排序结果局部乱序，测试数据小的时候还看不出来。

三路分区在"一千个元素里只有五种不同值"这种数据上，性能提升是数量级的——因为等于 pivot 的那一大段一次就处理完了，完全不用递归。同时它在普通随机数据上也不会变慢，所以我现在写快排基本都直接上三路分区的版本。

4. 归并排序：多出来的那块内存买到了什么

归并被低估得最厉害。很多人的印象是"它比快排慢，还费内存"，然后就再也不看了。但在真实工程里，归并出现的频率比想象中高得多。

4.1 稳定性不是纸面概念，多关键字排序时它会咬人

先讲稳定性为什么重要。假设你有一批订单记录，需要先按金额排序，金额相同再按时间排序。有两种做法：

做法一是写一个复合比较函数，把两个字段一起比。这在 Python 里可以用key=lambda 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, repeat=3): 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，随机数据：

规模 20000，随机数据：

规模 20000，已有序：

规模 20000，只有 5 种不同值：

这几张表里最值得琢磨的是最后一张。双指针快排在重复值多的数据上，比三路分区慢了将近 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, nxt=None): 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.next

a 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 稳定性、原地性、时间复杂度三张表

这三个属性经常被混着问，我习惯分开记，并且记住每个属性的"原因"而不是结论：

有一个容易记混的点：插入排序是稳定的。因为它是把元素逐个插到前面已排序部分的合适位置，遇到相等元素时用的是"严格大于才后移"，所以相等元素不会被越过。这也是 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 秒，改动量只有三行——那三行代码比任何算法优化都值钱。