5.3 堆排序与线性排序：比较流派的尽头与破局

5.3 堆排序与线性排序：比较流派的尽头与破局

本节摘要：比较排序存在 n log n 的理论下界——n 个元素有 n! 种排列，每次比较只能二分可能性，判定树高度至少 log₂(n!)，约 n log n。堆排序以原地、最坏 O(n log n) 立于比较流派之巅（代价是不稳定）；计数排序与基数排序干脆不做比较，靠"数格子"与"逐位装箱"打出线性时间，但要求数据分布配合。承接 3.4 节的堆与 5.2 节的下界伏笔。

比较流派的天花板

冒泡、快排、归并、堆排千差万别，却共享同一个动作：两两比较。比较流派的效率上限因此可以被抽象地证明：把排序过程画成一棵判定树，每个内部节点是一次比较（两种结果），每个叶子是一种最终排列。n 个元素有 n!（n 的阶乘）种可能排列，树至少要有 n! 片叶子；二叉树要容纳 n! 片叶子，高度至少是 log₂(n!)。用斯特林近似展开，log₂(n!) ≈ n·log₂n − 1.44n，渐近就是 n log n。无论招式多巧，只靠比较，谁也快过这条线——归并排序与堆排序恰好贴线飞行。

堆排序的两步走：先 3.4 节的方法把数组原地建最大堆（O(n)），然后反复"堆顶与末位交换、堆规模减一、新堆顶下沉"。每轮把当前最大者送到数组尾部，n 轮后整体升序：

# 堆排序：建堆 + 逐个摘顶，比较全程计数
def heapsort(a):
    a = list(a)
    n = len(a)
    cmp = [0]
    def sift(i, size):                     # 下沉：父与较大孩子比
        while True:
            l, r, m = 2*i + 1, 2*i + 2, i
            if l < size:
                cmp[0] += 1
                if a[l] > a[m]: m = l
            if r < size:
                cmp[0] += 1
                if a[r] > a[m]: m = r
            if m == i:
                return
            a[i], a[m] = a[m], a[i]
            i = m

    for i in range(n // 2 - 1, -1, -1):    # 建堆：从最后父节点倒着下沉
        sift(i, n)
    print("建堆后：", a)

    for end in range(n - 1, 0, -1):        # 排序：堆顶最大者送末尾
        a[0], a[end] = a[end], a[0]
        sift(0, end)                       # 堆规模缩为 end，修复堆顶
    return a, cmp[0]

data = [4, 10, 3, 5, 1]
out, c = heapsort(data)
print("排序结果：", out, "，共比较", c, "次")
# 输出：
# 建堆后： [10, 5, 3, 4, 1]
# 排序结果： [1, 3, 4, 5, 10] ，共比较 12 次
# 全程原地：无辅助数组，只有交换；最坏也是 O(n log n)——轴选歪的快排做不到这点
​

堆排序的定位：最坏保证 + 零额外空间，但跳跃式访问缓存不友好、且不稳定（远距离交换打乱相等键）。它是内省排序的"保险丝"——快排一露退化苗头就切堆排。

破局一：计数排序，数格子不做比较

比较下界封死了"比大小"的路，那就不比。键是 0 到 k 之间的整数时，开 k+1 个格子数出现次数，再做一遍前缀和确定每个键的落位区间，最后倒序回填保证稳定：

# 计数排序：计数 → 前缀 → 稳定回填
def counting_sort(a, k):
    counts = [0] * (k + 1)
    for x in a:
        counts[x] += 1                     # 第一步：数格子
    print("计数数组：", counts)
    for i in range(1, k + 1):
        counts[i] += counts[i - 1]         # 第二步：前缀和 = 落位边界
    print("前缀和：", counts)
    out = [0] * len(a)
    for x in reversed(a):                  # 第三步：倒序回填保稳定
        counts[x] -= 1
        out[counts[x]] = x
    return out

data = [4, 2, 2, 8, 3, 3, 1]
print("排序结果：", counting_sort(data, 8))
# 输出：
# 计数数组： [0, 1, 2, 2, 1, 0, 0, 0, 1]
# 前缀和： [0, 1, 3, 5, 6, 6, 6, 6, 7]
# 排序结果： [1, 2, 2, 3, 3, 4, 8]
​

时间账：三趟分别是 O(n)、O(k)、O(n)，合计 O(n + k)。k 与 n 同量级（比如百万考生的百分制分数）时就是漂亮的线性。前缀和数组的含义：值 v 的元素应落在下标 counts[v-1] 到 counts[v]-1 这一段——回填从右往左扫，相等元素的后到者放段尾，原序保持，稳定。

破局二：基数排序，逐位装箱

键是多位数（或等长字符串）时，从低位到高位逐位做稳定排序（通常用计数排序）：低位排好后，高位排序时同高位者内部的低位序已被保留。每轮 O(n + k)，共 d 轮（d 为位数），总量 O(d·(n + k))——对固定位数的整数就是线性：

# 基数排序：低位到高位，逐轮稳定装箱
def radix_sort(a):
    a = list(a)
    exp = 1
    while max(a) // exp > 0:
        buckets = [[] for _ in range(10)]  # 十个箱子
        for x in a:
            buckets[(x // exp) % 10].append(x)   # 按当前位装箱（稳定）
        a = [x for b in buckets for x in b]      # 依序倒出
        print(f"按 {exp} 位装过：", a)
        exp *= 10
    return a

print("最终结果：", radix_sort([329, 457, 657, 839, 436, 720, 355]))
# 输出：
# 按 1 位装过： [720, 355, 436, 457, 657, 329, 839]
# 按 10 位装过： [720, 329, 436, 839, 355, 457, 657]
# 按 100 位装过： [329, 355, 436, 457, 657, 720, 839]
# 最终结果： [329, 355, 436, 457, 657, 720, 839]
# 验证中间轮：按十位装箱时，720 与 329 同为 2，装进同箱保持上一轮先后——这就是稳定性的兑现
​

桶排序是计数的推广：格子换成"桶"（每桶一个列表），分布均匀时期望线性，分布倾斜时退化。

⚠️ 常见坑：拿计数排序处理大范围稀疏键。键是 32 位整数就直接开四十多亿个格子，内存当场崩塌。计数排序的世界属于"小范围整数"：分数、年龄、字符编码、像素值。范围先于代码。

💡 关键直觉：线性排序不是更快地比较，而是根本不比较——它们把"次序信息"藏在键的数值结构里（值即下标、位即轮次）。信息从哪来，效率就从哪来。

走火入魔：下界没读透的两种误用

**误用一：宣称"我的比较排序突破了 n log n"。**常见于快排实测跑赢归并——那是常数与缓存的优势，渐近上谁也没破线。判定树论证对一切比较排序成立，包括你没听说过的那些。

**误用二：基数排序不等长键直接上。**位数 d 不一致（混合长度的字符串、变长编号）时，要么补齐要么按最高位分组处理，直接跑会把短键与长键的位对错位。工程上先归一化键长，再装箱。

本节要点回顾

• 比较下界 n log n：n! 种排列、判定树二叉分叉，log₂(n!) 渐近即 n log n，比较流派无人幸免；
• 堆排序：建堆 O(n) 加 n 轮摘顶，最坏 O(n log n)、原地，代价是不稳定与缓存跳跃；
• 计数排序 O(n + k)：数格子、前缀定界、倒序稳定回填；前提键为小范围整数；
• 基数排序 O(d·(n+k))：低位到高位逐轮稳定装箱，位间的顺序由稳定性传递；
• 选型口诀：可比较看下界（快排/归并/堆排按稳定与空间取舍），整数小范围上计数，多位定长上基数。

数据有序之后，查找的春天才刚开始。下一节：从线性扫到二分砍半，一把尺子量出对数级查找。