排序算法完全拆解：从冒泡排序到基数排序

这篇文章是一份”算法论文式”的排序算法全拆解：先从生活中的排序场景引出问题，再给出严格的定义与工具（大 O、稳定性、原地性），然后逐个拆解 19 种经典排序与 21 种恶搞排序。每个算法都遵循同一条讲解路径：生活比喻 → 规则 → 手算例子 → 公式推导 → 优缺点与适用场景。文中的每一个关键数字都经过了真实脚本验算，不是凭空写出来的。

如果你喜欢一边读一边动手，可以打开我的 疯狂排序实验室：它把下面讲到的几乎所有算法都做成了彩虹柱状图动画，还带音效、单步调试和恶搞演出。强烈建议读完一个算法，就切到实验室里看一遍它的动画。

1 引言：把”乱”变成”序”

先想三个生活场景。

第一，整理书架。书架上有几十本书，全都按”最近看完就随手塞回去”的方式摆放。你想找一本《三体》，只能一本一本地翻。可如果所有书都按拼音或类别排好，你就能直接走到”科幻”那一格，几秒找到。第二，运动会发奖。裁判手里有一沓成绩单，只有按分数从高到低排好，才能确定金牌、银牌、铜牌分别是谁。第三，打扑克。每个人摸完牌的第一件事往往是把牌按大小理一理，因为理完牌之后，“有没有顺子""哪张最大”一眼就能看出来。

这三个场景的共同点是：杂乱的数据让人难以使用，有序的数据让一切查询和决策都变快。把”杂乱”变成”有序”的过程，在计算机科学里就叫排序（Sorting）。

排序为什么重要？因为它是几乎所有高级算法的地基：

• 查找更快：在 $n$ 个无序元素里找一个值，最坏要检查全部 $n$ 个；排好序之后可以用二分查找，只需要 $\lfloor\log_2 n\rfloor+1$ 次比较。
• 去重更容易：无序数组去重要两两比较，排好序之后相等的元素必然相邻，扫一遍就能去重。
• 数据分析更直观：统计最高分、最低分、中位数、出现频率，都建立在有序的基础上。
• 它是算法思想的教科书：插入、分治、递归、堆、哈希思想（桶）、位权思想（基数），几乎每一种重要算法范式都能在排序里找到最干净的样例。

所以算法课上第一课往往是排序，面试里最常考的也是排序。这篇文章的目标，是让一个刚接触算法的初中生，也能从零开始理解：排序到底在解决什么问题、每种算法是怎么想的、为什么复杂度是这样、什么时候该用哪一种。

2 排序问题的形式化

在讲算法之前，先把问题说清楚。

排序问题的严格定义：给定一个长度为 $n$ 的数组 $A=[a_0,a_1,\dots,a_{n-1}]$，以及一个”比较规则”（比如数值大小、字典序），我们要输出一个排列 $B$，使得 $B$ 中的元素与 $A$ 完全相同（一个不多、一个不少），并且满足：

$$B[0] \le B[1] \le \cdots \le B[n-1]$$

换句话说，排序要做两件事：一是不增不减（元素集合不变），二是重排顺序（让相邻元素都满足 $\le$ 关系）。

举个例子。输入：

$$A=[5,2,8,1,9]$$

那么合法的输出是 $B=[1,2,5,8,9]$。为什么 $[1,2,5,9,8]$ 不合法？因为最后两个元素 $9>8$，违反了”相邻元素 $\le$“的要求。

注意，排序针对的可以不只是数字。字符串可以按字典序排，学生可以按成绩排，订单可以按时间排。只要我们能回答”两个元素谁该排在前面”，就能排序。这个”谁前谁后”的规则，称为全序关系，它满足三条公理：

1. 自反性：$a \le a$；
2. 反对称性：若 $a \le b$ 且 $b \le a$，则 $a=b$；
3. 传递性：若 $a \le b$ 且 $b \le c$，则 $a \le c$。

这三条看似废话，却是排序算法正确性的地基。任何需要“把元素分到两边再分别处理”的算法，都依赖传递性：如果 $x\le y$、$y\le z$，那么 $x\le z$ 必然成立，分完两边之后才能放心地认为“左边整体都不大于右边”。

2.1 循环不变量：怎么证明一个算法是对的

光看几个例子就相信算法正确，在数学上是不够的——例子只能证明“这几个输入没问题”，不能证明“所有输入都没问题”。计算机科学里证明循环类算法正确性，最常用的工具叫循环不变量（Loop Invariant）。

循环不变量是一条“每一轮循环开始前都成立”的性质。它配合三个步骤构成完整证明：

1. 初始化：循环开始前，性质成立；
2. 保持：如果某一轮开始前性质成立，那么这一轮结束后性质依然成立；
3. 终止：循环结束后，性质能推出我们想要的结论。

先用一个与排序无关、但人人都能看懂的简单例子来理解它：在数组 $A$ 里找最大值。

算法只有两行核心逻辑：

best = A[0]
for i = 1 到 n-1:
    如果 A[i] > best，就把 best 更新为 A[i]

这个循环的不变量是：每次循环开始前，best 已经是 $A[0..i-1]$ 这个前缀里的最大值。

• 初始化：$i=1$ 时，前缀只有 $A[0]$，而 best=A[0]，显然成立；
• 保持：第 $i$ 轮只看 $A[i]$。如果 $A[i]$ 比 best 大，就更新；否则不更新。所以一轮结束后，best 变成 $A[0..i]$ 的最大值，不变量继续成立；
• 终止：$i=n$ 时，best 已经是整个数组的最大值，结论成立。

这个证明没有依赖任何“排序算法知识”，只用了“最大值”的定义。为什么文章要先讲它？因为后面每一个排序算法都可以用同一套“初始化 → 保持 → 终止”的模板来证明正确性。先把工具学会，后面看算法证明就不会懵。

3 基本功：大 O、稳定性、原地性与比较排序

3.1 什么是时间复杂度：先学会数操作次数

在讲”快慢”之前，先解决一个更基本的问题：怎么衡量一个算法用了多少时间？

最直接的办法是让程序在真实电脑上跑，用秒表计时。但同一段代码在不同电脑上速度差很多，而且输入不同，耗时也不同。所以计算机科学家更愿意数”操作次数”——比如比较两次、交换一次、赋值一次，各算一个操作。操作次数只和算法本身有关，和电脑快慢无关。

我们通常用 $n$ 表示输入规模。对排序来说，$n$ 就是待排序元素的个数。

先看三个与排序无关的小例子，感受”数操作次数”是什么意思：

例子 1：在 $n$ 个数里找最大值。 第 2.1 节写过：从第 2 个数开始，每个数都要和当前最大值比一次。所以无论数据怎么排，比较次数都是：

$$n-1$$

例子 2：检查 $n$ 个数里有没有重复。 一个朴素做法是把所有”两个人”的组合都检查一遍。第 1 个数要和后面 $n-1$ 个数比，第 2 个数要和后面 $n-2$ 个数比……总比较次数是：

$$(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$$

例子 3：不断把 $n$ 除以 2，直到变成 1。 需要约 $\log_2 n$ 次。比如 $n=1024$ 时，只需要 10 次。

同一个算法，可能在不同输入下操作次数不同，于是我们区分三种情况：

• 最好情况：最顺利的输入，操作次数最少；
• 最坏情况：最倒霉的输入，操作次数最多；
• 平均情况：所有输入”平均下来”的操作次数。

比如”检查有没有重复”的朴素做法，最好情况可能第 1 次就发现重复；最坏情况要检查完全部组合才发现没有重复。我们最关心的是最坏情况，因为它给出”无论输入多坏，算法都不会超过多少操作”的保证。

3.2 大 O 记号：给算法”估时间”

同一个排序，数据量翻倍之后要多久？我们真正关心的不是”3 秒还是 5 秒”，而是”数据量 $n$ 变大时，操作次数以什么速度增长”。

大 O 记号的定义：如果存在常数 $c>0$ 和 $n_0>0$，使得对所有 $n\ge n_0$ 都有：

$$f(n) \le c\cdot g(n)$$

那么就说 $f(n)=O(g(n))$，读作”$f$ 的增长阶不超过 $g$”。

直觉上，$O(n^2)$ 表示”操作次数大约和 $n^2$ 成正比”，$O(n\log n)$ 表示”大约和 $n$ 乘以 $n$ 的对数成正比”。当 $n$ 很大时，它们的差距非常悬殊：

数据规模 $n$	$n$	$n\log_2 n$	$n^2$	$2^n$
10	10	33	100	1024
100	100	664	10,000	$1.27\times 10^{30}$
1000	1000	9966	1,000,000	天文数字

这里先不举任何具体排序算法的名字，只看两个抽象的量级。处理 10 万个元素时：

• $n^2$ 量级意味着约 $10^{10}=100$ 亿次操作；
• $n\log_2 n$ 量级意味着约 $10^5\times 16.6\approx 166$ 万次操作；

两者相差约 6000 倍。这就是为什么”量级”比”具体的秒数”更重要：数据一变大，不同量级的算法会拉开天文数字般的差距。

3.3 稳定性与原地性

稳定排序（Stable Sort）：如果两个元素关键字相等，排序后它们的相对顺序保持不变。比如按成绩排序时，两个 90 分的学生，排序前谁在前面，排序后谁还在前面。

为什么稳定很重要？因为我们可以先按次要关键字排序，再按主要关键字稳定排序，实现”多级排序”。例如先按学号排，再按成绩稳定排，那么同分的同学内部仍然按学号有序。一个算法到底稳不稳定，取决于它在遇到相等元素时会不会把它们的相对顺序弄反。文章后面介绍每个算法时，都会在”性质”里明确告诉你它稳不稳定，并用一个小例子说明原因。

举一个具体的多级排序例子。假设有四个学生：$A(90,3)$、$B(90,1)$、$C(85,2)$、$D(85,4)$，括号里分别是成绩和学号。先按学号排序得到 $B,A,C,D$；再按成绩稳定排序，同分的 $B,A$ 保持学号序，$C,D$ 也保持学号序，最终结果是 $C(85,2),D(85,4),B(90,1),A(90,3)$——成绩优先、同分按学号。如果第二步用的是不稳定排序，$B$ 和 $A$ 的相对顺序可能被打乱，多级排序就失效了。这个”先排次要关键字，再稳定地排主要关键字”的技巧，后面会反复出现。

原地排序（In-Place Sort）：只需要 $O(1)$ 额外空间（最多几个临时变量），直接在原数组上交换。判断标准只有一个：它是否只使用少量临时变量、直接在原数组上操作。后面每个算法都会标注”原地 / 非原地”。

3.4 比较排序与非比较排序

比较排序只通过”$a$ 和 $b$ 谁大”这样的二元比较来获取信息。非比较排序则利用元素本身的结构（值域、位数、分布），不需要两两比较；这类方法会在后面的章节详细介绍。

比较排序有一个惊人的理论下限：任何比较排序最坏情况下至少要 $\Omega(n\log n)$ 次比较。这个结论可以用”决策树”证明：算法执行过程中，每次比较都像在树上走一条分支（“是”或”否”），$n$ 个不同元素共有 $n!$ 种可能的排列，决策树至少要 $n!$ 个叶子才能区分它们。一棵深度为 $d$ 的二叉树最多有 $2^d$ 个叶子，所以：

$$2^d \ge n! \quad\Longrightarrow\quad d \ge \log_2(n!)$$

再用斯特林公式 $n!\approx\sqrt{2\pi n}\,(n/e)^n$ 展开：

$$\log_2(n!) \approx n\log_2 n - 1.44n + O(\log n)$$

所以 $d=\Omega(n\log n)$。这就是为什么任何只靠比较的排序，最坏都不可能低于这个量级；想突破它，必须利用额外的数据结构。等你看完第 4、5、7 章的算法后，再回头看这个结论，会理解得更具体。

4 O(n²) 朴素排序家族

这一章的算法都简单直观，适合作为理解排序的起点。它们的共同弱点是：当 $n$ 变大时，比较次数按 $n^2$ 增长。

4.1 冒泡排序：大数像气泡一样往上冒

生活比喻：碳酸饮料里的气泡。小气泡轻，会不断往上浮；大气泡重，沉在下面。冒泡排序每一轮都把当前区域里最大的数”冒”到数组最后面，就像气泡浮到水面。

规则：从左到右依次比较相邻两个数，如果左边比右边大，就交换它们。这样一轮下来，最大的数一定到了最后。下一轮只需要处理前 $n-1$ 个数，如此重复。

逐步例子：对 $[5,2,8,1,9]$。

轮次	数组变化	说明
第 1 轮	$[2,5,1,8,9]$	5 与 2 换；5 与 8 不换；8 与 1 换；8 与 9 不换，9 到位
第 2 轮	$[2,1,5,8,9]$	2 与 1 换；5 与 8 不换，8 到位
第 3 轮	$[1,2,5,8,9]$	2 与 1 换，5 到位
第 4 轮	$[1,2,5,8,9]$	没有再交换，提前结束

伪代码：

for i = 1 to n-1:
    swapped = false
    for j = 0 to n-1-i:
        if A[j] > A[j+1]:
            交换 A[j] 和 A[j+1]
            swapped = true
    if not swapped:  # 这一轮没有任何交换，说明已经有序
        break

复杂度推导：最坏情况（数组完全逆序）下，第 $i$ 轮要比较 $n-i$ 次，总比较次数为：

$$C_{\text{bubble}} = \sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2} = O(n^2)$$

交换次数在最坏情况下同样是 $n(n-1)/2$。最好情况（数组已经有序）下，第一轮扫描 $n-1$ 次后没有交换，立即退出，复杂度是 $O(n)$。

性质：稳定（相等元素不交换）、原地。

优缺点与场景：实现最简单，代码几乎不可能写错；但对大规模数据太慢，只适合教学和 $n$ 很小的场景。工程上几乎不用它排序，但”相邻比较交换”的思想是奇偶排序、鸡尾酒排序、梳排序的基础。

下面是冒泡排序一轮完整扫描的流程图：

4.2 选择排序：每次挑最小的放前面

生活比喻：体育老师让全班同学按身高排队。老师不用反复比较相邻两个人，而是”找出最矮的，让他站到第一位；再在剩下的人里找最矮的，站到第二位……”

规则：第 $i$ 轮从 $A[i..n-1]$ 中选出最小元素，与 $A[i]$ 交换。

逐步例子：对 $[5,2,8,1,9]$。

1. 在 $[5,2,8,1,9]$ 中最小的是 1（下标 3），与 5 交换：$[1,2,8,5,9]$；
2. 在 $[2,8,5,9]$ 中最小的是 2，位置不变：$[1,2,8,5,9]$；
3. 在 $[8,5,9]$ 中最小的是 5，与 8 交换：$[1,2,5,8,9]$；
4. 剩下 $[8,9]$ 已经有序。

伪代码：

for i = 0 to n-2:
    minIdx = i
    for j = i+1 to n-1:
        if A[j] < A[minIdx]: minIdx = j
    交换 A[i] 与 A[minIdx]

复杂度推导：无论数据怎样，第 $i$ 轮都要比较 $n-1-i$ 次，所以：

$$C_{\text{selection}} = \sum_{i=0}^{n-2}(n-1-i) = \frac{n(n-1)}{2} = O(n^2)$$

交换次数最多只有 $n-1$ 次。这一点很关键：选择排序的写操作极少，适合”交换代价极高”的场景（比如移动超大对象）。

性质：常见实现不稳定。反例：$[5_a, 8, 5_b, 2]$，第一轮找到 2，与 $5_a$ 交换，数组变成 $[2,8,5_b,5_a]$，两个 5 的相对顺序被反转。它是原地排序。

优缺点与场景：比较次数固定、与输入无关；适合数据量小且”比较便宜、交换昂贵”的场合。

4.3 插入排序：像整理扑克牌一样把牌插进去

生活比喻：打扑克时，你从左到右一张张摸牌，每摸到一张新牌，就把它插到手里已经排好序的牌中正确的位置。你手里的牌永远是”前缀有序”的。

规则：从 $i=1$ 开始，把 $A[i]$ 存到临时变量，然后把它与前面的元素依次比较，凡是比它大的都往后挪一位，最后把 $A[i]$ 放到空出来的位置。

逐步例子：对 $[5,2,8,1,9]$，竖线左边表示已经排好的前缀。

步骤	数组	动作
初始	$5\mid2,8,1,9$	前缀 $[5]$ 天然有序
插入 2	$2,5\mid8,1,9$	5 后移，2 放到最前
插入 8	$2,5,8\mid1,9$	8 比 5 大，不动
插入 1	$1,2,5,8\mid9$	8、5、2 依次后移
插入 9	$1,2,5,8,9$	9 比 8 大，不动

伪代码：

for i = 1 to n-1:
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = key

复杂度推导。最坏情况（逆序）下，第 $i$ 个元素要挪 $i$ 次，总移动次数：

$$C_{\text{insertion,worst}} = \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = O(n^2)$$

最好情况（已经有序）下每轮只比较 1 次，一共 $n-1$ 次，是 $O(n)$。平均情况下，第 $i$ 个元素大约要挪 $i/2$ 次，所以：

$$C_{\text{insertion,avg}} \approx \frac{1}{2}\sum_{i=1}^{n-1} i = \frac{n(n-1)}{4} = O(n^2)$$

性质：稳定、原地。因为”相等不移动”，插入排序是少数几个既稳定又原地的排序。

优缺点与场景：对”接近有序”的数据非常快（$O(n)$）；实现简洁，常数小。归并排序和快速排序在递归到小规模子数组时，往往会改用插入排序收尾。它也是希尔排序的基础。

4.4 鸡尾酒排序：双向冒泡

生活比喻：鸡尾酒需要上下摇匀，而不是只往一个方向冒泡。鸡尾酒排序是冒泡排序的改进版：第一轮从左往右把最大值送到末尾，第二轮从右往左把最小值送到开头，第三轮再从左往右……像摇酒杯一样来回。

逐步例子：对 $[5,2,8,1,9]$。

1. 从左往右：$[2,5,1,8,9]$（9 到位）；
2. 从右往左（只看前 4 个）：$[1,2,5,8,9]$（1 到位）；
3. 已经有序，结束。

复杂度：最坏仍是 $O(n^2)$，最好 $O(n)$。它的优势是能同时处理”大的在左边、小的在右边”这种双向错位，比普通冒泡稍微快一点，但渐进复杂度不变。稳定、原地。

4.5 地精排序：走一步，退一步

生活比喻：花园里的小矮人（Gnome）整理一排花盆。他向右走，如果相邻两个花盆顺序正确就继续走；如果顺序错了，就交换它们并后退一步重新检查，直到前方有序。

伪代码：

pos = 0
while pos < n:
    if pos == 0 or A[pos-1] <= A[pos]:
        pos = pos + 1
    else:
        交换 A[pos-1] 与 A[pos]
        pos = pos - 1

复杂度：最坏 $O(n^2)$（逆序数组每次交换都要退一步），最好 $O(n)$。它本质上是一种”带记忆的插入排序”，代码非常短，常被用来玩”最小代码竞赛”。稳定、原地。

4.6 奇偶排序：奇数位和偶数位轮流比较

生活比喻：两排人面对面。先让下标 (0,1)、(2,3)、(4,5) 这些”偶数对”比较交换，再让 (1,2)、(3,4) 这些”奇数对”比较交换，反复进行。

规则：交替执行两轮扫描：一轮比较所有偶数下标与它的右邻居，一轮比较所有奇数下标与它的右邻居。只要某一轮没有任何交换，就结束。

复杂度：最坏 $O(n^2)$。它的价值在于极度适合并行：每一轮中所有”对”之间互不干扰，可以在不同处理器上同时比较交换。因此奇偶排序常用于 GPU 排序的入门讲解。稳定、原地。

4.7 梳排序：先拉开距离再冒泡

问题背景：冒泡排序有个著名弱点——小乌龟问题。大的数一轮就能”冒”到末尾，但小的数要一格一格往前挪，慢得离谱。

生活比喻：梳头时，先用大间距的梳齿把打结的头发粗略梳开，再换细齿梳子精细整理。

规则：比较距离从 $gap=\lfloor n/1.3\rfloor$ 开始，每轮缩小为 $\lfloor gap/1.3\rfloor$，直到 $gap=1$ 退化为普通冒泡。每个距离下做一轮”相距 $gap$ 的两个元素比较交换”。

复杂度：经验上约为 $O(n^2/2^p)$，其中 $p$ 与收缩因子有关；工程上常写作 $O(n^2)$，但常数比冒泡小很多。1.3 这个收缩因子来自经验研究，太小收敛慢，太大又退化。不稳定、原地。

4.8 朴素排序家族小结

把这七个算法放在一起看，它们其实对应着三种完全不同的”排序哲学”：

交换哲学（冒泡、鸡尾酒、奇偶、梳）：反复比较相邻元素，发现逆序就交换。它们的区别只在于”扫描方向”（单向还是双向）和”比较距离”（1 还是逐步缩小的 $gap$）。

选择哲学（选择排序）：每次锁定”第 $i$ 小的元素”，一次到位。它把比较次数做满，但交换次数压到最低。

插入哲学（插入、地精）：维护一个有序前缀，把新元素”塞”进正确位置。它们在”接近有序”的数据上表现最好，因为几乎不需要移动。

记住这三条哲学。它们各自的”加速版”会在接下来的章节里出现：有的靠间隔跳跃，有的靠分治，有的靠树形结构。等你看完下一章再回头看这句话，会理解得更深。排序算法不是一个孤立的列表，而是一棵从朴素思想长出来的树。

5 分治与进阶比较排序

这一章的所有算法都突破了 $O(n^2)$，思路核心是分治或数据结构。

5.1 希尔排序：插入排序的”间隔升级版”

核心思想：插入排序慢，是因为每次只能把元素移动一位。希尔排序先按大间隔分组做插入排序，让元素”大步”接近最终位置，再逐步缩小间隔，最后间隔为 1 时做一次普通插入排序——此时数组已经基本有序，插入排序会非常快。

逐步例子：对 $[5,2,8,1,9,3,7,4,6]$，取间隔序列 $gap=4,2,1$。

1. $gap=4$：下标差 4 的元素分成 5 组：$(5,9,6)$、$(2,3)$、$(8,7)$、$(1,4)$，组内插入排序后数组变为 $[5,2,7,1,6,3,8,4,9]$；
2. $gap=2$：分成两组，排序后变为 $[5,1,6,2,7,3,8,4,9]$；
3. $gap=1$：普通插入排序得到 $[1,2,3,4,5,6,7,8,9]$。

复杂度：与间隔序列有关。使用 Hibbard 间隔 $1,3,7,15,\dots$ 时，最坏复杂度为：

$$T_{\text{shell}} = O(n^{3/2})$$

使用某些精心构造的间隔序列可以达到 $O(n\log^2 n)$，但精确最优间隔至今没有定论。

性质：不稳定（间隔分组会跨越相等元素）、原地。

场景：中等规模数据、对稳定性没有要求时，希尔排序常数小、代码短，曾经是实用的选择；现在多数场合被快速排序或归并排序取代，但在嵌入式等资源受限环境仍有价值。

5.2 归并排序：先拆到底，再合并成序

核心思想：分治三步骤——

1. 分解：把数组从中间一分为二；
2. 递归：分别排序左半和右半；
3. 合并：两个已经有序的子数组，用”双指针”线性合并成一个有序数组。

逐步例子：对 $[3,1,4,1,5,9,2,6]$。

先递归分解：$[3,1,4,1]$ 与 $[5,9,2,6]$；再分解为 $[3,1]$、$[4,1]$、$[5,9]$、$[2,6]$；再分解为 8 个单元素。然后自底向上合并：

1. $[3]\cup[1]\to[1,3]$，$[4]\cup[1]\to[1,4]$，$[5]\cup[9]\to[5,9]$，$[2]\cup[6]\to[2,6]$；
2. $[1,3]\cup[1,4]\to[1,1,3,4]$，$[5,9]\cup[2,6]\to[2,5,6,9]$；
3. $[1,1,3,4]\cup[2,5,6,9]\to[1,1,2,3,4,5,6,9]$。

合并时”双指针”的规则是：两个指针分别指向两个子数组的开头，谁小谁先进入结果数组；相等时优先取左半边，所以归并排序是稳定的。

复杂度推导：设 $T(n)$ 为排序 $n$ 个元素的代价。分解与合并各花 $O(n)$，递归两次规模 $n/2$，于是：

$$T(n)=2T(n/2)+O(n),\qquad T(1)=O(1)$$

展开递归树：第 $k$ 层有 $2^k$ 个子问题，每个规模 $n/2^k$，每层总代价 $O(n)$，共 $\log_2 n+1$ 层：

$$T(n)=\sum_{k=0}^{\log_2 n} O(n)=O(n\log n)$$

递归树总节点数也可以精确计算。对 $n=8$ 的完美二分树，节点数：

$$1+2+4+8=15=2n-1$$

其中 8 个是叶子（单元素），7 个是内部节点（一次 merge）。我后面会用脚本实际数一遍。

性质：稳定，但需要 $O(n)$ 辅助数组，不是原地排序。

优缺点：最坏情况也保证 $O(n\log n)$，适合链表排序（合并不需要随机访问）、外存排序（数据太大无法进内存时，可以分块归并）。缺点是额外空间和常数较大。

这张树图把复杂度从公式变成了可数的结构：每一层合并的总代价都是 O(n)，树高约 log₂ n，所以总代价是 O(n log n)；节点总数 15 也正好验证了 2n−1 的精确公式。

5.3 快速排序：选个基准，两边开花

核心思想：也分三步——

1. 选一个基准（pivot）；
2. 分区：把所有比基准小的放到左边，比基准大的放到右边；
3. 递归排序左右两部分。

注意，快速排序的”分”发生在”递归”之前，而归并排序的”合”发生在”递归”之后。

逐步例子：对 $[5,2,8,1,9]$，取第一个元素 5 为基准。

1. 分区后：$[2,1]\;5\;[8,9]$；
2. 对左半 $[2,1]$ 取基准 2：$[1]\;2\;[]$；
3. 对右半 $[8,9]$ 取基准 8：$[]\;8\;[9]$；
4. 结果 $[1,2,5,8,9]$。

复杂度推导。最坏情况：每次基准恰好是最大或最小元素，一边为空，一边有 $n-1$ 个：

$$T_{\text{worst}}(n)=T(n-1)+O(n)=O(n^2)$$

平均情况：基准大致把数组对半分，递推式与归并相同：

$$T_{\text{avg}}(n)=2T(n/2)+O(n)=O(n\log n)$$

严格的平均分析要考虑所有 $n!$ 种输入，结论是平均比较次数约为 $2n\ln n\approx 1.39n\log_2 n$，常数比归并排序小。

这个结论值得推导一遍，因为它展示了”随机化平均分析”的标准套路。假设所有输入排列等概率出现，基准落在任何位置的概率都是 $1/n$。分区本身要比较 $n-1$ 次，然后左右两侧递归，于是期望比较次数满足：

$$T(n)=(n-1)+\frac{1}{n}\sum_{k=0}^{n-1}\bigl[T(k)+T(n-1-k)\bigr]=(n-1)+\frac{2}{n}\sum_{k=0}^{n-1}T(k)$$

两边乘以 $n$，再减去 $n-1$ 时的对应方程：

$$nT(n)-(n-1)T(n-1)=2n-2+2T(n-1)$$

整理得 $nT(n)=(n+1)T(n-1)+2n-2$，两边除以 $n(n+1)$：

$$\frac{T(n)}{n+1}=\frac{T(n-1)}{n}+\frac{2(n-1)}{n(n+1)}\approx \frac{T(n-1)}{n}+\frac{2}{n}$$

从 $n=1$ 一路累加，得到 $\frac{T(n)}{n+1}\approx 2\sum_{i=1}^{n}\frac{1}{i}=2H_n$，其中 $H_n$ 是调和数。由于 $H_n\approx \ln n$，最终：

$$T_{\text{avg}}(n)\approx 2n\ln n\approx 1.39n\log_2 n$$

推导里最妙的一步是”相减消去求和号”：两个相邻规模的递推式做差，把 $\sum T(k)$ 全部消掉，只剩下 $T(n)$ 和 $T(n-1)$ 的关系，这就是数学归纳与差分思想的结合。

性质：常见实现不稳定；原地（递归栈 $O(\log n)$ 除外）。

优化手段：随机选基准或三数取中，避免对有序数组退化；小规模子数组改用插入排序；三路分区处理大量重复元素。工程上（C 的 qsort、Java 的 Arrays.sort、Python 的 Timsort 混合体）几乎都以快速排序或归并的变体为核心。

优缺点：常数小、缓存友好，是”实践中最快的通用比较排序”；但最坏 $O(n^2)$，需要防范恶意构造的输入（随机化可以解决）。

5.4 堆排序：用”最大堆”反复取最大值

核心思想：先把数组建成一个最大堆——一种完全二叉树，父节点总是不小于子节点，所以树根就是最大值。然后反复执行：把根与最后一个元素交换（最大值”出堆”），再把剩下的部分重新调整成堆。

堆的数学结构：对下标 $i$ 的元素，它的左孩子下标是 $2i+1$，右孩子是 $2i+2$，父节点是 $\lfloor(i-1)/2\rfloor$。高度为 $h$ 的堆从根到叶子有 $h+1$ 层：

$$h=\lfloor\log_2 n\rfloor$$

建堆复杂度推导：这是堆排序最精彩的结论——建堆只需 $O(n)$。从最后一个非叶节点开始逐个”下沉”（sift down）。高度为 $h$ 的节点下沉最多 $h$ 次，而高度为 $h$ 的节点大约有 $\lceil n/2^{h+1}\rceil$ 个，所以总代价：

$$\sum_{h=0}^{\lfloor\log_2 n\rfloor} \lceil n/2^{h+1}\rceil\cdot h \;\le\; n\sum_{h=0}^{\infty}\frac{h}{2^{h+1}} \;=\;n\cdot 1 \;=\;O(n)$$

其中用到了几何级数求和 $\sum_{h\ge0} h/2^{h+1}=1$。之后每次取出最大值需要 $O(\log n)$ 的下沉，共 $n-1$ 次，所以排序阶段：

$$T_{\text{heapSort}}=O(n)+O(n\log n)=O(n\log n)$$

逐步例子：对 $[5,2,8,1,9]$。

1. 建堆：交换得到最大堆 $[9,5,8,1,2]$，根为 9；
2. 9 与末尾 2 交换：$[2,5,8,1,\mathbf{9}]$，下沉调整得 $[8,5,2,1,\mathbf{9}]$；
3. 8 与 1 交换：$[1,5,2,\mathbf{8,9}]$，调整得 $[5,1,2,\mathbf{8,9}]$；
4. 5 与 2 交换：$[2,1,\mathbf{5,8,9}]$，调整得 $[2,1,\dots]$；
5. 2 与 1 交换：$[1,\mathbf{2,5,8,9}]$，完成。

堆排序的反复动作就发生在这棵树上：根与末尾交换（最大值“出堆”），再把换到根的小元素一层层下沉，直到重新满足“父不小于子”。

性质：不稳定（堆内相同值可能越过对方）、原地、最坏也是 $O(n\log n)$。

优缺点：没有快速排序最坏退化的风险，也没有归并排序的额外空间；但缓存不友好（跳着访问），常数比快速排序大。适合对”最坏时间有硬要求”的场景，比如实时系统。

5.5 锦标赛排序：像世界杯一样淘汰

核心思想：把元素排成二叉树，两两比赛（比较大小），胜者晋级，直到决出冠军。找最大值只需要 $n-1$ 次比较。关键是：找次大值时，它只可能是”被冠军击败过的选手”，而冠军一路打败了 $\lceil\log_2 n\rceil$ 个人，所以只需在这些败者里再比一轮：

$$C_{\text{tournament}}= (n-1) + (\lceil\log_2 n\rceil - 1) = n + \lceil\log_2 n\rceil - 2$$

对 $n=5$：最大 4 次，次大 2 次，共 6 次。这个”冠军树”思想后来演化为优先队列（堆）的雏形。

逐步例子：对 $[5,2,8,1,9]$。第一轮：5 vs 2 → 5；8 vs 1 → 8；9 轮空。第二轮：5 vs 8 → 8；决赛：8 vs 9 → 9。冠军 9 打败过 8 和 1，次大在 $\{8,1\}$ 中比较得 8。

性质：稳定版本可以实现；空间 $O(n)$（需要败者树）。它是”选择排序的树形优化”，用空间换比较次数。

5.6 进阶排序小结：三条分治主线

归并、快速、堆、锦标赛表面上差别很大，实际上对应着三条不同的优化主线：

均衡拆分（归并、快速）：把问题切成两个差不多大的子问题。归并选择”拆分位置固定、合并时做事”，快速选择”分区时做事、合并无事可做”。两者都靠”两个 $n/2$“把递归深度压到 $\log_2 n$，区别只是把 $O(n)$ 的工作放在递归前还是递归后。

数据结构化（堆、锦标赛）：与其反复扫描找最值，不如预先把数据组织成树，让”取最值”变成 $O(\log n)$ 的操作。锦标赛用败者树记录淘汰历史，堆用完全二叉树实现同样的功能且不浪费空间。这是”用一次预处理换取无数次快速查询”的思想，也是优先队列等许多数据结构的共同根基。

间隔跳跃（希尔）：不改变数据结构，而是改变”比较的距离”。先远距离粗排，再近距离细排，把插入排序的 $O(n)$ 单步移动缩短为 $O(n^{3/2})$ 甚至更少。这条主线启发了后来”先全局后局部”的分层优化思想。

理解这三条主线之后，再看任何新的排序算法，你都可以问一句：它把时间省在了哪一步？是减少了比较次数，减少了移动次数，还是减少了递归深度？ 能回答这个问题，才算真正读懂了算法。

6 怪奇但真实：煎饼、圈、臭皮匠与慢排序

这一章算法都是”真能排好序”的，但要么操作受限、要么慢得离谱。它们很适合用来训练”把规则翻译成算法”的能力。

6.1 煎饼排序：只能用铲子翻

生活比喻：一摞大小不一的煎饼，厨师只能用铲子从某个位置把上面一层整体翻过来，就像翻煎饼一样。一次操作只能翻转前缀。

规则：每一轮先找到当前区间（前 $k$ 个煎饼）中最大饼的位置 $m$，如果 $m$ 不在顶部，先翻转前缀 $m+1$ 把它翻到顶部，再翻转前缀 $k$ 把它翻到底部。

逐步例子：对 $[5,2,8,1,9]$（最大值 9 已经在底部，跳过）；当前区间 $[5,2,8,1]$，最大 8 在下标 2。

1. 翻转前 3 个：$[8,2,5,1,9]$；
2. 翻转前 4 个：$[1,5,2,8,9]$；
3. 当前区间 $[1,5,2]$，最大 5 在下标 1，翻转前 2 个：$[5,1,2,8,9]$；
4. 翻转前 3 个：$[2,1,5,8,9]$；
5. 翻转前 2 个：$[1,2,5,8,9]$。

每轮最多 2 次翻转，共 $n-1$ 轮，所以翻转次数上界：

$$F_{\text{pancake}} \le 2(n-1)$$

更精细的分析给出上界 $\le 2n-3$。性质：不稳定、原地；每轮 $O(n)$ 找最大，所以比较次数 $O(n^2)$。它在 DNA 翻转生物学问题中有真实应用。

6.2 圈排序：写入次数最少

核心思想：每个元素最终都要去一个位置，把”现在的位置 → 目标位置”连起来会形成若干个圈（cycle）。圈排序沿着每个圈移动元素，每个元素只写一次（圈首会写两次），所以总写入次数最小。

规则：对位置 $i$，数一数有多少元素比 $A[i]$ 小，这个数就是 $A[i]$ 最终的下标；把它放到那里，再从被顶出来的位置继续。

逐步例子：对 $[3,2,4,1]$。位置 0 的 3 应该去下标 2（有 2 个元素比它小），把 3 放到下标 2，顶出 4；4 应该去下标 3，顶出 1；1 应该去下标 0，正好回到起点，完成一个圈：$[1,2,3,4]$。

复杂度：比较 $O(n^2)$，但写入次数最多 $2n-1$。对”写操作代价极高”（如闪存磨损均衡）的场景非常合适。不稳定、原地（不含被圈覆盖的临时空间时）。

6.3 臭皮匠排序：三个臭皮匠顶个诸葛亮

规则（递归）：

stoogeSort(A, lo, hi):
    若 A[lo] > A[hi]: 交换
    若 hi - lo < 2: 返回
    t = (hi - lo + 1) / 3 取整
    stoogeSort(A, lo, hi - t)      # 前 2/3
    stoogeSort(A, lo + t, hi)      # 后 2/3
    stoogeSort(A, lo, hi - t)      # 前 2/3 再来一遍

复杂度推导：每次递归处理规模 $2n/3$ 的子问题 3 次，外加常数工作：

$$T(n)=3T(2n/3)+O(1)$$

用主定理或直接展开，设 $n=(3/2)^k$，则 $T(n)=3^k=n^{\log_{3/2}3}$：

$$T_{\text{stooge}}=O(n^{\log_{3/2}3})\approx O(n^{2.7095})$$

它比 $O(n^2)$ 还慢，而且几乎从不实用。它的价值是展示”分治不保证高效”——分治必须保证递归规模之和小于 1，这里 $3\times 2/3=2>1$，问题规模不降反增。

6.4 慢排序：故意慢到极致

规则（递归）：

1. 找出最大值并放到末尾；
2. 递归排序前 $n-1$ 个。

而”找最大值”的方式也很慢：递归排序前一半、后一半，再取两个最大值中较大的那个：

$$T(n)=2T(n/2)+T(n-1)+O(1)$$

解这个递推式需要一点技巧。猜测 $T(n)=\Omega(n^{\log_2 n})$：归纳地代入 $T(n/2)\ge c(n/2)^{\log_2(n/2)}$ 和 $T(n-1)\ge c(n-1)^{\log_2(n-1)}$，第一项给出主导项 $2c(n/2)^{\log_2 n}=cn^{\log_2 n}$，足以覆盖第二项的较低阶项，所以：

$$T_{\text{slow}}=\Omega(n^{\log_2 n})$$

$n^{\log_2 n}$ 增长速度介于多项式与指数之间（$n^{10}$ 只是多项式，而 $\log_2 n$ 作为指数会超越任何固定次幂）。慢排序是”算法设计课的反面教材”：它的递推式看上去和归并几乎一样，只多了一个 $T(n-1)$，复杂度就从 $O(n\log n)$ 暴涨到超多项式。

6.5 怪奇排序的启示

煎饼排序提醒我们：操作受限时，问题会变难。同样是排序，一次只能翻转前缀和一次可以交换任意两个元素，难度完全不同——前者需要 $O(n^2)$，后者只需要 $O(n\log n)$。圈排序提醒我们：优化目标不同，最优算法就不同。当我们把”比较次数”换成”写入次数”来衡量，设计出来的算法完全不一样。臭皮匠和慢排序则提醒我们：递归不是免费的午餐。分治要高效，必须满足”子问题规模之和小于 1”，否则递归树会指数膨胀。

这些算法虽然不实用，却是最好的”算法思维显微镜”：它们把某个单一特性放大到夸张的程度，让我们清楚地看到每个设计决策的后果。

7 线性时间排序：计数、基数、桶

比较排序有 $\Omega(n\log n)$ 下限，但如果数据有特殊结构，我们可以”不比较”就排序。

7.1 计数排序：像给试卷按分数分堆

适用条件：所有元素都是 $[0,k]$ 范围内的整数（或可以映射成整数）。

生活比喻：老师要按分数（0~100 分）给 500 张试卷排队。老师不会把试卷两两比较，而是准备 101 个箱子，每张试卷直接丢进对应分数的箱子，最后按箱子编号从小到大把试卷倒出来——这就是计数排序。

规则：三遍扫描——

1. 统计：数出每个值出现多少次，得到计数数组 $C$；
2. 前缀和：把 $C$ 变成”每个值最后一个该出现在哪”的累计位置；
3. 回填：从后往前扫描原数组，把每个元素放到累计位置，位置减一（从后往前是为了保持稳定）。

逐步例子：对 $[4,2,5,2,3,1,4]$，值域 1~5。

1. 计数：$C=[0,1,2,1,2,1]$（值 1 到 5 各出现 1、2、1、2、1 次）；
2. 前缀和：$C'=[0,1,3,4,6,7]$；
3. 回填（从后往前）：4 → 位置 6，2 → 位置 3，1 → 位置 1，3 → 位置 4，2 → 位置 2，5 → 位置 7，4 → 位置 5，得到 $[1,2,2,3,4,4,5]$。

复杂度：

$$T_{\text{counting}}=O(n+k)$$

当 $k=O(n)$ 时就是 $O(n)$。空间同样 $O(n+k)$。性质：可以稳定、非原地。

7.2 基数排序：一位一位地排

适用条件：元素可以拆成 $d$ 位（如十进制数 $d$ 位、字符串 $d$ 个字符）。

核心思想：从最低位到最高位（LSD），每趟用一次稳定的计数排序处理一位。关键依赖是稳定性：高位的顺序不会破坏低一位已经排好的顺序。

逐步例子：对 $[329,457,657,839,436,720,355]$。

1. 按个位排：$[720,355,436,457,657,329,839]$；
2. 按十位排：$[720,329,436,839,355,457,657]$；
3. 按百位排：$[329,355,436,457,657,720,839]$，完成。

复杂度：每趟对 $[0,b-1]$ 做计数排序要 $O(n+b)$，共 $d$ 趟：

$$T_{\text{radix}}=O(d(n+b))$$

当位数 $d$ 是常数时，这就是线性排序。性质：稳定（每趟计数排序都稳定）、非原地。

为什么稳定性对基数排序是”生死攸关”的？看一个反例。数组 $[32,31]$ 按个位排好后是 $[31,32]$，接下来按十位排，两个数的十位都是 3。如果这趟排序不稳定，可能把顺序又变回 $[32,31]$，前面的努力全部白费；稳定排序会保持个位顺序，得到正确结果 $[31,32]$。推广到一般情况：高位的排序只在”低位相同”时才需要做出选择，而低位的相对顺序早已由前一趟排好——这正好是稳定性的定义。所以基数排序的正确性，可以递归地陈述为：第 $i$ 趟结束后，数组按”后 $i$ 位”组成的数有序；而第 $i+1$ 趟的稳定排序，在不破坏”后 $i$ 位有序”的前提下，把第 $i+1$ 位变成主导关键字。

这里再点明一句因果关系：第 i+1 趟稳定排序只是把第 i+1 位变成主导关键字，同时完整保留“后 i 位已有序”的成果；只要任何一趟不稳定，前面的努力就可能前功尽弃。

7.3 桶排序：把元素均匀撒进桶里

适用条件：元素在区间 $[0,1)$ 或某个范围内均匀分布。

核心思想：把值域切成 $n$ 个桶，把元素丢进对应桶，桶内用插入排序，最后按桶顺序拼接。

复杂度推导：若分布均匀，每个桶平均只有 $O(1)$ 个元素，桶内排序总代价线性：

$$T_{\text{bucket,avg}}=O(n)$$

最坏情况所有元素挤进一个桶，退化回插入排序：

$$T_{\text{bucket,worst}}=O(n^2)$$

逐步例子：对 $[0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12]$，取 4 个桶，每个桶覆盖长度为 0.25。丢桶后各桶内容为：桶 0：$[0.17,0.26,0.21,0.12]$，桶 1：$[0.39]$，桶 2：$[0.78,0.72]$，桶 3：$[0.94]$。桶内插入排序后：$[0.12,0.17,0.21,0.26]$、$[0.39]$、$[0.72,0.78]$、$[0.94]$，按桶顺序拼接即得到完整有序数组。

性质：可以稳定、非原地。桶排序是”哈希思想”在排序中的体现：用关键字直接定位桶，而不是两两比较。

7.4 非比较排序的统一视角：用”结构”换时间

计数、基数、桶三个算法看起来差别很大，其实共享同一个思想：不通过比较获取信息，而是利用关键字本身的结构，把元素直接”分发”到正确的位置附近。

计数排序利用的是值域结构（整数可以当数组下标）；基数排序利用的是位权结构（多位数可以按位分解，且低位排序可以被高位继承）；桶排序利用的是分布结构（均匀分布下每个桶元素很少）。三者都是”空间换时间”：计数和基数用 $O(n+k)$ 或 $O(n+b)$ 的辅助空间，桶排序用 $O(n)$ 个桶，换来比较排序无法达到的 $O(n)$ 时间。

这条思路的代价也很明显：它们都对输入有假设。遇到”分布极不均匀”或”值域极大”的数据，三者都会退化（桶排序最坏 $O(n^2)$，计数排序会因为 $k$ 太大而失去意义）。所以正确的用法是：先判断数据形态，再决定要不要放弃”通用性”。

8 珠排序：一本正经的”重力排序”

珠排序常被当成恶搞排序，但它真实存在，而且有严肃的并行计算含义。

核心思想：把每个元素 $a_i$ 想象成一列珠子，珠子在竖直的杆子上受重力下落。比如 $[3,1,4,2]$ 画成四列珠子：

列1  ●●●
列2  ●
列3  ●●●●
列4  ●●

所有珠子同时受重力下落，会”落座”到每根杆子的底部。数一数每一行有多少颗珠子，从下往上读，恰好就是排序后的结果：$[1,2,3,4]$。原因是：珠子总量守恒，且”底部从第一行开始逐行堆满”，重力让每行的珠子数自然形成非减序列。

复杂度：抽象模型下，若 $S$ 是元素之和、$n$ 是元素个数，时间 $O(S)$；并行硬件模型下可以快到 $O(\sqrt{S})$ 甚至 $O(n)$。但经典计算机上需要模拟”珠子下落”，通常实现是计数排序的变体，所以实际价值更多在于并行排序的物理直觉。

为什么常被归入恶搞：因为”把数组想象成一堆珠子再让重力排序”的画风太清奇。但它的原理（重量守恒 + 分层计数）完全严谨，是”用物理模型思考算法”的绝佳例子。

9 恶搞排序大赏

恶搞排序不是为了效率，而是为了幽默和思维训练。它们每一款都在讽刺某种”人类解决问题的坏习惯”：赌运气、自我欺骗、暴力、拖延、政治隐喻。下面按实验室里出现的顺序逐个介绍。

1. 猴子排序 / 博戈排序（Bogo Sort）：洗牌 → 检查是否有序 → 没序再洗。$n$ 个元素共有 $n!$ 种排列，每次洗牌成功概率 $1/n!$，期望尝试次数：

$$\mathbb{E}[\text{洗牌次数}]=n!$$

每次洗牌 $O(n)$，所以期望 $O(n\cdot n!)$。$n=10$ 时约 362 万次尝试，$n=15$ 时约 1.3 万亿亿次。它是”赌徒排序”的代表。

2. 灭霸排序（Thanos Sort）：随机消灭一半元素，检查剩余是否有序；不有序就继续消灭。它一定能”排好序”，因为剩下的元素数量会单调减少，最终只剩 1 个或 0 个（必然有序）——代价是数据完整性。它讽刺”解决不了问题就解决提出问题的人”。

3. 睡眠排序（Sleep Sort）：为每个元素开一个”闹钟”，值为 $v$ 的元素睡 $v$ 毫秒后输出。小值先醒，输出自然有序。复杂度依赖调度器，理论上还能工作；但如果值跨度太大（1 和 10 亿），你要等 11 天半。它还无法处理负数（需要偏移）。

4. 斯大林排序（Stalin Sort）：从左到右扫描，只保留非递减的元素，任何”逆序者”直接枪毙（删除）。时间复杂度 $O(n)$，非常快——因为它没有排好序，只是消灭了逆序证据。它讽刺”信息审查”。

5. 仁慈斯大林排序（Merciful Stalin Sort）：改进版——不枪毙逆序者，而是把他们流放到古拉格，最后对”流放队伍”再递归执行仁慈斯大林排序，直到整体有序。它能真正排好序，但最坏复杂度是 $O(n^2)$，且递归层数可能很深。

6. 奇迹排序（Miracle Sort）：检查数组是否有序；不是，就祈祷。只要耐心足够，理论上宇宙热寂前可能等到一次奇迹。实验室版本祈祷 24 次后改快速排序，那是为了节目效果。

7. 量子博戈排序（Quantum Bogo Sort）：先洗牌，同时创建无数个平行宇宙——每个宇宙里数组是一种排列；然后观察：只有”恰好有序”的那个宇宙保留下来，其余宇宙被销毁。若多世界诠释成立，观测到有序数组的概率为 1，复杂度 $O(1)$（宇宙创建成本另计）。它讽刺”先射箭后画靶”。

8. Bogobogosort：递归版博戈排序。对前 $n-1$ 个元素执行 Bogobogosort，检查前 $n$ 个是否有序；无序就重新洗牌重来。它的期望时间比普通博戈排序还要爆炸好几个数量级，是”递归恶搞”的极致。

9. Bozo 排序（Bozo Sort）：随机选两个元素交换，检查是否有序。它比博戈排序稍”有作为”一点，但期望复杂度仍是阶乘级别。

10. 字典序排序（Alphabetical Sort）：把数字转成字符串，按字母顺序排。于是 $10$ 会排在 $2$ 前面（因为字符 “1” < “2”）。它”忠实执行了规则，却弄错了目标”，讽刺只重形式不重语义。

11. 矮人排序（Dwarf Sort）：把第一个元素”扔”到队伍末尾，检查是否有序；不有序就继续扔，直到把所有排列都试过或运气爆发。它是”旋转 + 赌博”的杂交品种。

12. 栈排序（Stack Sort）：把所有元素压入栈，然后祈祷 LIFO（后进先出）弹出的顺序刚好有序。栈是”逆序的队列”，所以它几乎必然失败；实验室版本里它把元素全部压栈、再按弹栈顺序展示，讽刺”数据结构选错了，再多努力也没用”。

13. 乐观排序（Optimistic Sort）：看一眼首尾，宣布”差不多有序”，直接结束。它不保证正确，但保证 $O(1)$ 时间和好心情。

14. 虚无主义排序（Nihilist Sort）：删除所有元素。空数组必然有序（没有元素违反规则），所以算法”正确”地返回空数组——只是丢失了全部数据。它讽刺”什么都没有就什么都不会错”。

15. 民主排序（Democracy Sort）：每轮让所有存活元素两两投票，得票最多的元素被”弹劾”删除，直到只剩一个或数组有序。它比斯大林排序温和，但同样用删除换取有序，复杂度 $O(n^3)$ 量级。

16. 恐慌排序（Panic Sort，出自 xkcd 1185）：随机切牌一万次碰运气，时间一到还没排好就惊慌失措。它讽刺”紧急情况下的随机行为”。

17. 特朗普排序（Trump Sort）：从左到右扫一遍（假装认真比较），然后宣布”已经排好序了，史上最好，BIG WIN！“。它不改变任何元素，直接宣称胜利。

18. 人机验证排序（Captcha Sort）：把排序任务变成”点击相邻交换”的人机验证，倒计时结束没排好就判定你是机器人。它把计算工作外包给人类，讽刺验证码滥用。

19. 洗衣机排序（Washing Machine Sort）：把数组塞进滚筒高速旋转（随机旋转），祈祷衣服自己叠好；转若干圈没叠好就改人工叠衣（插入排序兜底）。

20. 珠排序（Bead Sort / Gravity Sort）：见第 8 章——真实的重力排序，常因其画风被归入恶搞。

21. 智能设计排序（Intelligent Design Sort）：直接声明”本数组由造物主精心排列，天然有序”，不执行任何比较。它讽刺”拒绝证据、信仰先行”。

这 21 款恶搞排序的共同价值是：让你意识到一个排序算法必须回答两个问题——它能不能终止？终止时结果是否正确？ 很多恶搞排序靠删除数据或宣称胜利来”正确”，这就是为什么严谨的算法证明（正确性 + 终止性）如此重要。

10 数字验算：脚本实测

空口说”冒泡排序要做 $n(n-1)/2$ 次比较”不够有说服力。下面这些数字是我用 Node 脚本逐行模拟真实算法得到的，不是手算或估算。

10.1 冒泡、选择、插入的比较次数

$n$	冒泡（已有序）	冒泡（逆序）	选择（任何输入）	插入（最坏逆序）	插入（最好有序）
5	4	10	10	10	4
10	9	45	45	45	9
100	99	4950	4950	4950	99

可以看到：冒泡和插入的”最好情况”都是 $n-1$ 次比较（各发生一次提前退出或每轮只比较一次），而选择排序是唯一”看输入脸色都不变”的算法——它总是做满 $n(n-1)/2$ 次比较。

10.2 归并排序递归树节点数

用递归函数逐次调用统计：

$n$	递归调用总数	叶子（单元素）	内部节点（合并）
8	15	8	7
16	31	16	15
32	63	32	31

验证了公式：总数 $=2n-1$，内部节点 $=n-1$，叶子 $=n$。

10.3 锦标赛与堆的额外验证

$n$	锦标赛找最大	锦标赛次大额外	合计
5	4	2	6
8	7	2	9
16	15	3	18

堆排序的上界估算（公式 $\sum_{h} \lceil n/2^{h+1}\rceil h + 2n\lfloor\log_2 n\rfloor$）：

$n$	建堆比较上界	排序阶段比较上界	合计上界
5	14	20	34
10	34	60	94
100	398	1200	1598

10.4 计数与基数

• 计数排序对任意值域 $[0,k]$ 的数据只需要 1 趟统计 + 1 趟回填（两遍扫描、一趟回填）；
• 基数排序对 3 位十进制数需要 3 趟（个位、十位、百位），每趟都是一次稳定计数排序；
• 比较排序下界验证：$\log_2(10!)\approx 21.8$，$\log_2(100!)\approx 524.8$，$\log_2(1000!)\approx 8529.4$，与 $n\log_2 n$ 只差约 $1.44n$，印证了斯特林公式的推导。

10.5 家族成员之间的实测差距

同样用脚本跑 $n=100$，四种”冒泡亲戚”的比较次数差距非常有趣：

算法	逆序输入	接近有序输入
鸡尾酒	4950	672
地精	9900	385
奇偶	5049	1683
梳	1102	1201

三个发现：第一，鸡尾酒和奇偶在逆序时和冒泡同级别（约 5000 次），它们的改进主要靠提前退出；第二，地精在逆序时反而比冒泡差（约 9900 次），因为每次交换都要退回去重新比较；第三，梳排序在逆序时只有 1102 次，接近 $n\log_2 n$ 的量级，证明”先拉开距离”确实解决了小乌龟问题。这些数字再次说明：渐进复杂度相同，常数和输入形态也能让实际表现差好几倍。

11 总结对比与选型决策

先把全文讲过的算法放回同一张“复杂度谱系图”，方便你从整体上对比：

11.1 一张总表

算法	平均时间	最坏时间	空间	稳定	原地	一句话评价
冒泡	$O(n^2)$	$O(n^2)$	$O(1)$	是	是	教学入门，双向版为鸡尾酒
选择	$O(n^2)$	$O(n^2)$	$O(1)$	否	是	写次数最少，比较固定
插入	$O(n^2)$	$O(n^2)$	$O(1)$	是	是	近有序无敌，小数组王者
希尔	$O(n^{3/2})$ 左右	与间隔有关	$O(1)$	否	是	插入排序的间隔加速
鸡尾酒	$O(n^2)$	$O(n^2)$	$O(1)$	是	是	双向冒泡
地精	$O(n^2)$	$O(n^2)$	$O(1)$	是	是	一步一退的迷你插入排序
奇偶	$O(n^2)$	$O(n^2)$	$O(1)$	是	是	天生适合并行
梳	$O(n^2/2^p)$	$O(n^2)$	$O(1)$	否	是	解决小乌龟问题
归并	$O(n\log n)$	$O(n\log n)$	$O(n)$	是	否	稳定可靠，适合外排
快速	$O(n\log n)$	$O(n^2)$	$O(\log n)$	否	是	实践最快，需防退化
堆	$O(n\log n)$	$O(n\log n)$	$O(1)$	否	是	最坏也快，缓存不友好
锦标赛	$O(n\log n)$	$O(n\log n)$	$O(n)$	可	否	选择排序的树形升级
煎饼	$O(n^2)$	$O(n^2)$	$O(1)$	否	是	只翻转前缀
圈	$O(n^2)$	$O(n^2)$	$O(1)$	否	是	写入次数最少
臭皮匠	$O(n^{2.71})$	$O(n^{2.71})$	$O(n)$	否	是	分治的反面教材
慢	$\Omega(n^{\log_2 n})$	$\Omega(n^{\log_2 n})$	$O(n)$	否	是	故意慢到极致
计数	$O(n+k)$	$O(n+k)$	$O(n+k)$	是	否	小值域整数
基数	$O(d(n+b))$	$O(d(n+b))$	$O(n+b)$	是	否	定长整数/字符串
桶	$O(n)$	$O(n^2)$	$O(n)$	可	否	均匀分布数据
珠	$O(S)$ 模型	$O(S)$	$O(S)$	可	否	重力模拟，画风清奇

11.2 怎么选：一张决策树

11.3 三条核心规律

读完所有算法，请记住这三句话：

第一，比较排序的极限是 $O(n\log n)$。归并、快速、堆都达到了这个量级，谁也甩不开谁；想更快，只能用非比较排序，但非比较排序对数据有额外要求。

第二，没有”最好的排序”，只有”最合适的排序”。插入排序在小数据上可能比快排还快；归并在稳定性要求下不可替代；堆在最坏时间有保证；基数在定长数字上碾压一切比较排序。选型要看数据规模、数据形态、稳定性要求、内存限制和常数。

第三，复杂度分析要结合常数和场景。$O(n\log n)$ 的快排常数小、缓存友好，所以”平均最快”；但它最坏 $O(n^2)$，所以需要随机化。归并稳定但要多用一倍内存。这些工程细节，和渐进复杂度同样重要。

12 动手实验

光看文字和公式，很难形成直觉。请打开我的 排序算法可视化实验室：

• 在”选择算法”里挑一个刚读完的算法（比如插入排序），点”开始”，观察彩虹柱的移动规律；
• 打开”单步”模式，一步一步看”比较”和”交换”分别发生在哪里；
• 切换”接近有序""完全逆序”数据模式，验证文中说的最好/最坏情况；
• 体验恶搞排序的动画演出：斯大林排序的”枪毙”特效、量子博戈的”宇宙销毁”、民主排序的”弹劾”，都是严肃算法教学的快乐调味剂。

12.1 如何自己验证一个排序算法是对的

写完一个排序算法，怎么知道它没有 bug？光看动画”好像排好了”不够，推荐四步测试法：

1. 随机测试：生成大量随机数组，排序后检查两条性质——结果长度不变、结果非降序；
2. 排列测试：排序前后元素的多重集合完全一致（用计数或再排序一次来验证），防止算法”删元素”作弊；
3. 边界测试：空数组、单元素、全相等、已有序、完全逆序、只有两个元素，这些边界最容易暴露下标错误；
4. 不变量断言：在循环里插入断言，检查”有序前缀”或”最大元素已就位”等循环不变量是否每一轮都成立。

这套方法对恶搞排序尤其有用：你会立刻发现斯大林排序和乐观排序”输出正确却改变了数据”，而虚无主义排序把元素删光了——它们的错误不是”排错序”，而是违反了排序的定义。正确的算法必须同时通过这四步测试，这也是循环不变量思想在工程上的落地。

参考资料

1. Sorting algorithm Wikipedia
2. Comparison sort（比较排序下界） Wikipedia
3. Introduction to Algorithms（CLRS） Thomas H. Cormen 等 · MIT Press
4. Algorithms：sorting and searching Khan Academy
5. Sorting（可视化动画） VisuAlgo
6. Sorting Algorithms GeeksforGeeks
7. Sorting Algorithms Animations Toptal
8. Bogosort Wikipedia
9. Bead sort Wikipedia
10. Panic Sort（恐慌排序出处） xkcd 1185
11. CS50 Week 3：Algorithms Harvard CS50