企业官网建设流程全解析

1. 三兄弟到底差在哪：先把选型逻辑捋清楚

排序算法这件事，我前后写过不下十几遍。第一次是照着教材抄，第二次是为了应付面试，再往后就变成了真的要在项目里用——数据清洗时给一批订单按时间排、跑指标时给几千个分数做分桶、写个小工具时顺手把结果列表排一下。写得越多越发现，python 的快速排序、归并排序、冒泡排序这三者被放在一起讲，从来不是因为它们性能接近，而是因为它们刚好代表了三种完全不同的思路：分治加原地交换、分治加额外空间、纯邻位比较。搞懂这三种思路的取舍，比背下三份代码有价值得多。

这篇文章想解决的问题很具体：很多人能默写出三份代码，但说不清为什么快排会退化、为什么归并要多开一个数组、为什么冒泡在真实项目里几乎不该出现却还要学。我会把三份实现从朴素版一路改到工业可用版，中间穿插参数怎么定、阈值怎么算、坑在哪里。适合两类人看：一是刚学完数据结构想看看真实代码长什么样的新手，二是写过但没深究过细节、想补一课的老手。全文代码都可以直接复制跑，Python 3.8 以上没问题。

1.1 一句话定位三种排序的适用边界

我习惯用一句话给它们各自贴标签，方便在真实场景里快速决策。冒泡排序的标签是"教学标本"，它的价值在于让你理解什么叫"相邻比较、逐步冒泡"，运行效率在真实数据量面前基本没有讨论意义；快速排序的标签是"平均最快的原地选手"，代价是不稳定、最坏情况会退化、递归深度需要盯着；归并排序的标签是"稳定且可预测的外排基础"，代价是需要 O(n) 的额外空间，但它那套"分到最小再合并"的结构能顺手解决一大类附加问题，比如统计逆序对、做外部排序、合并多个有序流。

这三者的核心差异其实落在三个维度上：是否原地、是否稳定、最坏情况是否可控。快排原地但不稳定且最坏 O(n²)；归并稳定且最坏 O(n log n) 但不原地；冒泡原地且稳定但平均 O(n²)。真实工程里，绝大多数情况下你该做的事情是直接调用list.sort()或sorted()——那背后是 Timsort，一种归并和插入排序的混合体。手写这三种排序的场景，更多出现在需要定制比较逻辑、需要在排序过程中携带额外信息、或者需要在受限环境下自己实现时。所以别把这三份代码当成"日常工具"，把它们当成"理解排序思想的三个坐标"。

1.2 复杂度表背后的真实含义

教科书上的复杂度表人人会背，但那张表容易给人错觉，好像 O(n log n) 就一定比 O(n²) 快。实际跑起来，常数因子、内存访问模式、Python 解释器开销，都会把理论曲线搅得面目全非。

表里最值得盯的是"交换/移动次数"和"最坏情况"这两行。归并排序的移动次数是常数级的 O(n log n)，几乎不受输入分布影响，这就是它"可预测"的来源；快排的移动次数会随着数据分布剧烈波动，全相同元素、已经有序、完全逆序这三种输入，能让同一份代码跑出天差地别的耗时。冒泡排序在最坏情况下要做 n(n-1)/2 次比较，n 取一万就是接近五千万次，在 Python 里这个量级基本等于让 CPU 空转十几秒。

注意：复杂度表里的 log 底数在分析时无所谓，但落到"递归深度"这个具体参数上就有所谓了。快排的递归深度约等于 log₂n，n 是一百万时约 20 层，n 是一亿时约 27 层。这个数字看着很小，但如果基准选得差，退化后深度会变成 n，Python 默认递归上限 1000 层，直接 RecursionError。

1.3 Python 这门语言的特殊性会狠狠影响你的实现

同一份快排逻辑，用 C 写和用 Python 写，性能瓶颈完全不在一个地方。C 里你要操心的是缓存命中率和分支预测；Python 里你要操心的是解释器每执行一条字节码的开销。这意味着一个很反直觉的结论：在 Python 里，减少 Python 层的操作次数，比减少理论上的比较次数更有效。

举个具体的例子。归并排序的合并阶段，常见写法是left = arr[:mid]、right = arr[mid:]先切片，然后双指针合并。切片是 C 层实现，速度快，但会复制内存；如果数据量是百万级，每次递归都切一次，总复制量是 O(n log n) 个元素引用，内存峰值和 GC 压力都会上来。另一种写法是用索引区间原地传参，避免切片，理论上更省内存。但在 Python 里实测下来，切片版本往往更快——因为切片那一步是 C 干的，而索引版每个arr[i]都要走一次 Python 的字节码。这就是"语言的实现细节压过理论最优"的典型案例。

还有一个 Python 特有的坑：递归函数调用的开销很高。CPython 每次函数调用都要创建栈帧对象，快排这种递归调用次数在 O(n) 量级的算法，函数调用开销能占到总耗时的一大块。所以我后面讲快排优化时，会把"小数组切插入排序"和"递归深度控制"放在很靠前的位置，因为这两条对 Python 实现的收益最明显。至于sys.setrecursionlimit，可以调，但别乱调——调太高会把 C 栈也撑爆，直接段错误，比 RecursionError 难查一百倍。

2. 冒泡排序：教学价值远大于实用价值，但坑一点不少

先说清楚我的态度：真实项目里我不建议你手写冒泡排序去处理任何超过几百条的数据。但它值得认真写一遍，因为它是"用局部有序推导全局有序"这个思想最朴素的体现，而且它的两个优化点——提前退出、记录最后交换位置——是理解"算法如何针对数据分布做自适应"的入门钥匙。很多人写冒泡就是双重 for 循环糊上去，从不考虑优化，结果在"输入已经基本有序"这种很常见的场景下，白白跑满 n² 次比较。

2.1 朴素版：先看清它为什么慢

最基础的写法是这样的：

def bubble_sort_basic(arr): n = len(arr) for i in range(n - 1): for j in range(n - 1 - i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr

内层循环的边界是n - 1 - i，这个- i不是随手写的。每一轮外层循环结束，当前未排序区间里最大的元素已经被推到区间末尾，下一轮就没必要再比较它。少减这个i，代码仍然能跑对，但会多做大约一半的无用比较——这是我看过的最高频的低级失误之一。

慢的根本原因在于交换次数。冒泡排序每一轮只把一个元素送到最终位置，而每次交换只涉及相邻两个位置。一个元素如果要从数组最右端跑到最左端，需要 swap n-1 次。整体来看，逆序对有多少，就要 swap 多少次。随机排列的数组，逆序对期望是 n(n-1)/4，n 等于 5000 时是六百多万次交换，每次交换在 Python 里展开成一次元组构造加两次赋值，耗时接近一秒。这就是为什么冒泡在真实数据量面前完全没有竞争力。

2.2 两个优化：提前退出与记录最后交换位置

第一个优化很好理解：如果某一轮从头到尾没有发生任何交换，说明整个数组已经有序，后面所有轮次都是白跑，直接 break。

def bubble_sort_early_exit(arr): n = len(arr) for i in range(n - 1): swapped = False for j in range(n - 1 - i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True if not swapped: break return arr

第二个优化更巧妙，也更容易被忽略：记录这一轮最后一次发生交换的位置，那个位置之后的所有元素在本轮结束时都已经有序了，下一轮的内层循环边界可以直接收缩到那里，而不用只减 1。

def bubble_sort_optimized(arr): n = len(arr) end = n - 1 while end > 0: last_swap = 0 for j in range(end): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] last_swap = j end = last_swap return arr

这两个优化合起来，让冒泡排序在"基本有序、只有少量元素错位"的输入上表现相当不错，接近 O(n + k) 级别（k 是错位元素个数）。比如一个已经排好序的日志列表，末尾追加了几条乱序记录，用优化版冒泡处理起来比全量重排快得多。当然，即便这样，sorted()仍然更快——我提这个是为了让你理解优化的思路，而不是鼓励你在项目里用它。

2.3 实测数据与几条实操心得

我在一台普通的开发机上跑过一组对照（数据是随机生成的整数列表，单位毫秒）：

数据量翻倍，冒泡耗时几乎翻四倍，完美贴合 O(n²)；而sorted()的曲线几乎是线性增长的。这个差距在 4000 条的规模上已经超过两千倍，再往上就没有测试的意义了。

注意：在 Python 里做相邻元素交换，arr[j], arr[j+1] = arr[j+1], arr[j]比先用 temp 变量三步赋值略快，因为元组解包在字节码层面有专门优化（ROT_TWO）。这个差异在单次比较里微不足道，但在百万次级别的循环里能省下可观时间。这是我反复压测后才注意到的小细节。

一个容易忽略的点：冒泡排序的稳定性来自"只在严格大于时才交换"这个判断。如果你写成>=，相等的元素也会被交换，稳定性立刻消失。这类细节在纯数字排序里看不出来，但你一旦排的是对象列表、按某个字段排，稳定与否就直接影响结果是否符合预期。

3. 快速排序：平均最快，但坑也最深

快排是这三者里最值得深挖的。它的核心思想一句话能说完：选一个基准，把数组分成"小于基准"和"大于基准"两部分，然后对两部分递归。但真正写起来，分区怎么写、基准怎么选、递归怎么收敛，每一步都有讲究，而且每一步选错都会导致性能断崖式下跌。我在不同项目里写过至少五六个版本，从最朴素的 Lomuto 分区到三路快排，每一次改写都对应一个具体的性能问题。

3.1 分区写法：Lomuto 与 Hoare 的取舍

Lomuto 分区是最容易理解的版本，用单指针扫描，把小于基准的元素逐步换到前面：

def partition_lomuto(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

它的优点是逻辑直白、边界不容易写错，缺点是在大量重复元素的场景下会退化成 O(n²)。原因在于它把所有等于基准的元素都归到同一侧，如果整个数组全是相同值，每次分区只能剥离出一个元素，递归深度变成 n。

Hoare 分区用左右双指针相向扫描，交换次数更少，而且天然能把等于基准的元素分散到两侧：

def partition_hoare(arr, low, high): pivot = arr[(low + high) // 2] i, j = low - 1, high + 1 while True: i += 1 while arr[i] < pivot: i += 1 j -= 1 while arr[j] > pivot: j -= 1 if i >= j: return j arr[i], arr[j] = arr[j], arr[i]

Hoare 版本的返回值是分割点j，递归时要写成quick_sort(arr, low, j)和quick_sort(arr, j + 1, high)，注意不是j - 1。这个边界是新手最容易写错的地方，写错了轻则结果不对，重则无限递归。我的建议是：如果只是为了理解原理，写 Lomuto；如果追求性能，用 Hoare，但一定要配一组包含重复元素、全相同元素、已排序的测试用例反复验证。

3.2 基准怎么选：三种策略的实际差别

基准选择直接决定了快排会不会退化。三种常见策略：

取首元素或尾元素：最简单，但对已经有序的输入是灾难。如果输入是升序数组、基准取末尾元素，每次分区都只能剥离一个元素，递归深度变成 n，复杂度退化为 O(n²)。现实中"已经有序"的数据比你想象的多得多——数据库导出的、日志按时间追加的、上一轮已经排过的，都可能是有序或近似有序的。

随机选取：pivot = arr[random.randint(low, high)]。这一招把最坏情况的概率压到极低，且实现简单，是我个人最推荐的默认方案。代价是每次分区多一次随机数调用，Python 里random.randint的开销不算小，可以做个小优化：在函数外把randint绑定到局部变量，减少属性查找。

三数取中：取首、中、尾三个元素的中位数作为基准。它对"已排序"和"逆序"这两种输入都有很好的抵抗力，且没有随机数开销。实现上要注意：取中位数的过程本身就是三次比较，可以直接把中位数换到末尾位置，这样后面就能复用 Lomuto 的写法。

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[high - 1] = arr[high - 1], arr[mid] return arr[high - 1]

这里有个细节：三次比较之后，arr[low] <= arr[mid] <= arr[high]已经成立，所以arr[low]和arr[high]可以直接排除在分区范围之外，实际参与分区的只剩low+1到high-1。这个"排除两端"的技巧能省掉一些比较，是很多教科书版本没有提到的优化。

3.3 让它真正能上生产：小数组阈值与递归深度

纯递归的快排有个隐性成本：当子数组小到只有几个元素时，递归调用的开销比直接排序还大。这是所有分治算法的通病，解决办法是设一个阈值，小于阈值就切插入排序。

阈值取多少？理论上跟 CPU 缓存行大小有关，业界常见取值在 8 到 32 之间。我在 Python 里做过简单压测，取 16 左右比较均衡——太小了递归调用多，太大了插入排序的 O(k²) 开始显现代价。插入排序在小数组上快，是因为它没有函数调用开销、没有额外内存分配，且 Python 的while循环处理短列表时开销可控。

def insertion_sort_range(arr, low, high): for i in range(low + 1, high + 1): key = arr[i] j = i - 1 while j >= low and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key

另一个必须处理的问题是递归深度。即便用了随机基准，极端情况下深度仍可能超过默认的 1000 层限制。有两种解法：一是调sys.setrecursionlimit，二是手动维护一个栈把递归改成迭代。我更推荐后者，因为它不依赖全局配置，也不会把 C 栈撑爆。

def quick_sort_iterative(arr, threshold=16): if len(arr) < 2: return arr stack = [(0, len(arr) - 1)] while stack: low, high = stack.pop() while low < high: if high - low + 1 <= threshold: insertion_sort_range(arr, low, high) break pivot_idx = partition_hoare(arr, low, high) # 先压入较大的区间，再处理较小的区间，控制栈深度为 O(log n) if pivot_idx - low < high - pivot_idx: stack.append((pivot_idx + 1, high)) high = pivot_idx else: stack.append((low, pivot_idx)) low = pivot_idx + 1 return arr

这段代码里有个很值得学的技巧：先处理较小的那一半，把较大的压栈。这样栈的最大深度被限制在 O(log n)，而不是最坏情况下的 O(n)。这个技巧来自尾递归消除的思路，在 C 里靠编译器优化，在 Python 里只能手动做。

注意：改成迭代版本之后，虽然避免了 RecursionError，但如果分区逻辑写错导致某一侧区间永远不缩小，就会变成死循环而不是报错。所以调试迭代版时，务必在内层 while 里加个计数器，跑到一定次数就抛异常，快速定位问题。

3.4 三路快排：面对大量重复元素的正确姿势

如果数据里重复值很多——比如按省份统计用户、按评分统计问卷结果，取值可能只有几十种——Lomuto 和 Hoare 都会吃亏。三路快排把数组分成"小于、等于、大于"三段，等于基准的那一段直接跳过递归，一次分区就能把一整批相同元素放到最终位置。

def quick_sort_three_way(arr, low, high): if low >= high: return pivot = arr[low] lt, i, gt = low, low + 1, high while i <= gt: if arr[i] < pivot: arr[lt], arr[i] = arr[i], arr[lt] lt += 1 i += 1 elif arr[i] > pivot: arr[gt], arr[i] = arr[i], arr[gt] gt -= 1 else: i += 1 quick_sort_three_way(arr, low, lt - 1) quick_sort_three_way(arr, gt + 1, high)

这里的三个指针lt、i、gt分别维护"小于区右边界""当前扫描位置""大于区左边界"。循环结束时，[low, lt-1]全部小于基准，[lt, gt]全部等于基准，[gt+1, high]全部大于基准。递归时只处理两侧，中间那批完全不用管。

这个版本在"取值种类少、元素数量多"的场景下性能提升非常明显。我试过对一个包含一百万个元素、但取值只有 26 种的列表排序，普通 Hoare 快排要跑将近两秒，三路快排只要零点四秒左右。差距这么大的原因很简单：普通快排会对着那一百万个相同元素反复分区，而三路版本一次就把它们全归位了。

4. 归并排序：稳定、可预测，还能顺手解决别的问题

归并排序是我在真实项目里用得最多的一种手写排序，原因不是它平均最快——快排通常比它快一点——而是它行为可预测。不管输入是随机的、有序的、逆序的、全相同的，它的时间复杂度都是 O(n log n)，没有退化这回事。这种可预测性在需要保证响应时间的场景里非常值钱。而且它的"合并两个有序序列"这个结构，本身就是一个可以复用的组件：合并多个有序文件、求逆序对、做外部排序，全是在它的骨架上搭出来的。

4.1 自顶向下：递归版的基本形态与切片陷阱

最标准的写法是这样的：

def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result

这个写法最大的优点是清晰，缺点是每次递归都返回新列表，内存分配次数是 O(n log n) 级别。对一百万条数据来说，递归树有二十层，每层加起来要分配一百万个元素的列表，总共分配两千万个位置。这还没算上切片本身的复制。

改进方向有两个。第一个是改用索引区间原地操作，只开一个和原数组等大的辅助数组，在合并时把结果写回：

def merge_sort_inplace(arr): n = len(arr) if n <= 1: return arr buffer = [0] * n _merge_sort(arr, buffer, 0, n - 1) return arr def _merge_sort(arr, buffer, low, high): if low >= high: return mid = (low + high) // 2 _merge_sort(arr, buffer, low, mid) _merge_sort(arr, buffer, mid + 1, high) if arr[mid] <= arr[mid + 1]: return _merge(arr, buffer, low, mid, high) def _merge(arr, buffer, low, mid, high): buffer[low:high + 1] = arr[low:high + 1] i, j = low, mid + 1 for k in range(low, high + 1): if i > mid: arr[k] = buffer[j] j += 1 elif j > high: arr[k] = buffer[i] i += 1 elif buffer[i] <= buffer[j]: arr[k] = buffer[i] i += 1 else: arr[k] = buffer[j] j += 1

注意中间那行if arr[mid] <= arr[mid + 1]: return。这是一个很实用的短路优化：如果左半部分的最大值已经小于等于右半部分的最小值，说明两段加起来天然有序，根本不需要合并。对"已经接近有序"的输入，这个判断能省掉大量工作，实测能让归并排序在近似有序数据上快三四成。

4.2 自底向上：彻底摆脱递归

自底向上版本从长度为 1 的子序列开始，两两合并，逐渐扩大块大小。它没有递归调用开销，也不会有栈深度问题，代码还更短：

def merge_sort_bottom_up(arr): n = len(arr) if n <= 1: return arr buffer = [0] * n width = 1 while width < n: for low in range(0, n, width * 2): mid = min(low + width - 1, n - 1) high = min(low + width * 2 - 1, n - 1) if mid < high and arr[mid] > arr[mid + 1]: _merge(arr, buffer, low, mid, high) width *= 2 return arr

mid和high都要用min截断，因为最后一块的长度可能不满 width。这两个边界处理是自底向上版本最容易出错的地方，漏了就抛 IndexError 或者产生静默的错误排序结果。我踩过一次，原因是测试用例的数组长度刚好是 2 的幂，边界永远不触发，换成 1000 这种非 2 的幂才暴露出来。所以测试用例一定要用"非 2 的幂、小于 2×width、奇数长度"这类边界数据。

自底向上版本还有个隐藏优势：它是完全可预测的执行流，没有函数递归的不可控开销，在某些受限环境（比如需要严格控制栈空间、或者需要在单次执行中精确控制时间片）下更好用。代价是代码稍微不那么直观，理解成本高一点。

4.3 顺手把逆序对也数了

归并排序有个别的算法很难替代的用途：统计逆序对。所谓逆序对，就是满足i < j但arr[i] > arr[j]的元素对。这个概念在推荐系统（衡量排序结果与理想排序的差异）、风控（衡量行为序列的异常程度）里都用得上。

关键在于合并那一步。当right[j]小于left[i]时，说明left中从i到末尾的所有元素都比right[j]大，也就是说它们各自与right[j]构成一个逆序对，一次就能加上len(left) - i个。

def count_inversions(arr): if len(arr) <= 1: return arr, 0 mid = len(arr) // 2 left, cnt_left = count_inversions(arr[:mid]) right, cnt_right = count_inversions(arr[mid:]) merged = [] i = j = 0 cross = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) cross += len(left) - i j += 1 merged.extend(left[i:]) merged.extend(right[j:]) return merged, cnt_left + cnt_right + cross

这段代码的价值在于：如果你用两层 for 循环去数逆序对，复杂度是 O(n²)，一万条数据就要一亿次比较；而归并版本是 O(n log n)，同样的数据量快了接近三个数量级。这类"排序过程中顺带完成统计"的思路值得记住，很多看似需要暴力枚举的问题，套上归并或分治的骨架就能降一个复杂度量级。

4.4 内存和 GC 的坑

归并排序最大的成本是空间。如果你在 Python 里对超大列表（比如几千万条）做归并，辅助数组会占用和原数组等量的内存——由于 Python 的列表存的是对象引用而不是值，实际内存占用要看元素类型，但至少在引用层面是翻倍的。加上切片和中间列表，峰值可能是原数据的三倍。

我踩过一次内存爆掉的坑，场景是对一批大对象做排序，对象本身占内存，切片复制的是引用还好，但递归的每一层都持有各自的列表，直到返回才释放，峰值比理论值高很多。解决办法是改用索引区间版本，并且提前分配好一个 buffer 对象反复复用——这样无论递归多深，辅助内存都只有一份。

注意：复用一个 buffer 时，要保证每次合并前把对应区间从原数组拷贝进 buffer，而不是依赖上一轮残留数据。这个细节写漏了，代码在小数据上完全正常，数据量一大就会出现部分元素诡异的错位，排查起来非常折磨人。

5. 性能实测与常见问题排查

代码写完不等于事情结束，接下来这一步才是区分"能跑"和"能用"的地方。我习惯写一个简单的压测脚本，把三份实现放在同一批数据上跑，观察趋势而不是绝对数值。绝对数值跟机器、Python 版本、GC 状态都有关系，趋势才说明问题。

5.1 压测脚本与数据生成

import random import time import sys sys.setrecursionlimit(100000) def bench(func, data, repeat=3): best = float('inf') for _ in range(repeat): arr = data.copy() start = time.perf_counter() func(arr) best = min(best, time.perf_counter() - start) return best * 1000 sizes = [500, 1000, 2000, 4000] for n in sizes: random.seed(42) base = [random.randint(0, 10000) for _ in range(n)] print(f"n={n}") print(f" bubble_opt {bench(bubble_sort_optimized, base):>9.2f} ms") print(f" quick_iter {bench(quick_sort_iterative, base):>9.2f} ms") print(f" merge_v2 {bench(merge_sort_inplace, base):>9.2f} ms") print(f" builtin {bench(sorted, base):>9.2f} ms")

几个关键的测试设计原则。取三次最小值，而不是平均值——排序的耗时受 GC、CPU 频率波动影响，最差值往往是被环境噪声污染的，最小值最接近真实算法成本。用random.seed固定数据，否则每次跑出来的数据不同，对比就没有意义了。测之前先 copy，因为快排和插入排序是原地修改的，不复制的话第一次跑完数据就变成有序的，第二次测的完全是另一回事。用perf_counter而不是time.time，后者的精度在某些平台上只有十几毫秒，测短耗时完全不可靠。

实测下来的典型结果大概是：n=4000 时，优化冒泡在一千二百毫秒上下，迭代快排在六到八毫秒，原地归并在一到两毫秒，sorted()在零点六毫秒左右。归并比快排快这件事，一开始我也觉得反常——毕竟快排平均更优。原因在 Python 上很具体：快排的交换次数多，每次交换都是 Python 层的字节码操作；归并的主要工作是切片和buffer[low:high+1] = ...，那是 C 层实现的批量复制，效率高一个量级。这又是一个"语言实现细节压过理论排名"的例子。

5.2 常见问题速查表

表格里最后一条值得展开说。Python 里arr.__len__()这种属性查找是要走字典查找的，虽然 CPython 做了优化，但在百万次循环里累积起来仍然可观。常见做法是n = len(arr)提前取好，或者append = result.append把方法绑定到局部变量。这类微优化在使用 C 扩展时没必要，但在纯 Python 手写排序里，收益是实打实能测出来的，有时候能省两三成时间。

5.3 一些从坑里爬出来的经验

最后分享几条我认为最有价值、但常规资料里不太会写的经验。

第一条，测试用例的构造比算法本身更值得花时间。我现在的标准测试集至少包含这几类：完全随机、已升序、已降序、全部相同、只有两种取值、包含大量重复的随机、长度为 0/1/2/奇数/2 的幂/2 的幂加一。这十几种输入能覆盖绝大多数边界问题。前面提到的自底向上归并的边界 bug，就是因为当时偷懒只用 2 的幂做测试才漏掉的。

第二条，不要迷信"最优实现"，要迷信"你的数据下的最优实现"。理论上归并比快排慢一点，但在 Python 里因为切片是 C 层操作，归并常常反超。理论上快排原地省内存，但如果你开了buffer列表，归并的内存开销也就是多一份引用数组，在现代机器上未必是问题。真正的判断依据只能来自压测。

第三条，sorted()是你要挑战的对象，不是你可以忽略的背景。Timsort 是经过十几年打磨的工业级实现，在真实数据上几乎总是最快的。手写这三种排序的意义在于理解原理、应对特殊需求（定制比较、边排边统计、受限环境），而不是替代内置函数。想清楚这一点，你就不会在项目里写出"性能敏感的地方用自己手写的快排"这种自我感动但毫无收益的代码。

第四条，关于递归，我个人在 Python 里写分治算法的默认选择是：能用迭代就用迭代，实在不能再用递归，并且一定要在递归版写好后立刻写一个迭代版对照测试。两份实现互相验证，能揪出大量的边界错误。而且当你需要处理大数据量时，迭代版往往不需要任何改动就能上。

第五条，如果你真的要在一个项目里放排序代码，把它封装成一个函数，参数带key或者比较器，而不是把arr[j] > arr[j+1]硬编码进循环。我在一个数据清洗脚本里就因为硬编码了数字比较，后来要按时间戳排序时只能整段重写。那次之后，所有手写排序我都统一成带key参数的形式，虽然多一点间接调用开销，但可维护性的提升完全值得。

6. 三份实现放在一起看，到底该学哪个

写到这里我想说一个可能有点反共识的看法：这三种排序里，最值得反复动手的其实是归并排序。原因是它能衍生出的东西最多——合并有序流、求逆序对、外部排序的分块合并、多路归并，这些在真实工程里都有对应场景。快排的价值在于理解"分治 + 原地分区"这个模式，它的思想会反复出现在选择算法、Top-K 问题里。冒泡排序的价值是理解"局部操作累积成全局有序"，以及优化的思路，但它本身确实没什么工程价值。

如果你刚开始学，我的建议顺序是：先写冒泡，把两层循环和边界搞扎实；再写归并，理解"分治 + 合并"这个最干净的模板；最后写快排，因为它边界最多、最需要小心，放在有一定调试经验之后更合适。如果你已经有基础，直接跳到 3.3 和 4.4 那两节看，那里面关于递归转迭代、buffer 复用、短路优化的内容，是我认为实战中最有用但最容易缺失的部分。

代码写完一定要自己跑一遍压测，别只在脑子里推演。排序这类算法的特性是：小数据几乎全对，大数据才暴露问题；随机数据几乎全对，特定分布才暴露问题。这两条规律让我吃过太多次亏——每次都是"看起来没问题"，然后在真实数据上翻车。现在我的习惯是，任何排序实现写完，立刻拿那十几种边界输入跑一遍，通过了才敢往项目里放。这个习惯本身，比任何一条具体技巧都更能省下排查时间。