排序算法的下界与进化

1.4 排序算法的下界与进化

本节摘要：排序是算法进化史最完整的标本。本节沿着"交换式平方级、插入式平方级、分治式线性对数级、非比较式线性级"的路线走完全程，解释快排为什么快、归并为什么稳、比较排序为什么撞上 n log n 的理论下界，以及计数排序如何绕开下界，最后给出一套场景化选型表。

一部完整的进化史

前三节我们优化的是查找；本节转向排序——它是第一章的收官，也为第二章的分治递归埋下伏笔。排序好就好在：同个问题存在代际分明的多种解法，恰好构成一条教科书级的进化链。第一代靠交换与选择，第二代靠分治，第三代干脆放弃比较。走完这条链，你对"瓶颈决定进化方向"的理解会上升一个台阶。

一、第一代：平方级的三兄弟

冒泡、选择、插入，思路各不同，复杂度却同为 O(n 的平方)。冒泡排序反复扫描，把相邻的逆序对交换，每趟让当前最大值"浮"到末尾。选择排序每趟从未排序区间挑出最小值，放到已排序区间的末尾。插入排序把每个新元素插入到前面已排序部分的正确位置，像整理手里的扑克牌。

def bubble_sort(a):
    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

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:   # 边比较边右移
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

print(bubble_sort([5, 2, 9, 1, 5, 6]))     # 输出 [1, 2, 5, 5, 6, 9]
print(insertion_sort([5, 2, 9, 1, 5, 6]))  # 输出 [1, 2, 5, 5, 6, 9]
​

三兄弟并非一无是处。插入排序在基本有序的数据上接近线性（内层几乎不移动），小数组上常数极小——这正是许多语言的标准库在快速排序递归到小区间时切换回插入排序的原因。选择排序交换次数最少（至多 n 减一），在"写比读贵"的场景反而占优。冒泡则基本只活在教科书里，提前退出的优化版本偶尔还能一用。

二、第二代：分治带来的飞跃

进化发生在意识到"不必逐对比较全部数对"之后：把数组劈成两半分别排好，再合并。归并排序是最纯正的分治：递归拆到单元素（天然有序），然后两两合并有序段，合并过程用双指针线性归并。稳定、可预测，时间恒为 O(n log n)，代价是 O(n) 的辅助数组。

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # 等号保证稳定性
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

print(merge_sort([5, 2, 9, 1, 5, 6]))    # 输出 [1, 2, 5, 5, 6, 9]
​

快速排序是分治的另一种用法：先选个基准值把数组分区（小的去左、大的去右），基准就位后左右两半递归处理，难处在分区而不在合并。均摊 O(n log n)，原地分区空间 O(log n)（递归栈）。它的阿喀琉斯之踵是固定选端点做基准时，遇到已序输入退化为 O(n 的平方)——每轮分区只切掉一个元素。对策是随机选基准或三数取中。两者的取舍口诀：要稳定、要最坏保证选归并；要原地、平均最快选快排。Python 的 sort 用归并改造出的混合算法保稳定，C++ 的 sort 用内省排序（快排加堆排加插入的混合）防退化——工业实现都是进化链的合流而非单点。

三、天花板与非比较路线

这里出现全章最重要的理论拐点：基于比较的排序存在 O(n log n) 的下界。直觉论证是把排序过程看成决策树——每次比较分叉，n 个元素有 n 的阶乘种排列，二叉树要区分所有排列至少需要 log2(n 的阶乘) 层，由斯特林近似，它就是 n log n 量级。也就是说，只要算法只靠"谁大谁小"获取信息，第二代已经到头了。想更快必须换赛道：不比较，改用"值本身当地址"。计数排序统计每个值出现几次再顺序输出，时间 O(n 加值域)，适用于值域不大的整数；基数排序按位分桶逐位稳定排序，适用于定长关键字；桶排序把值域切桶、桶内再排，适用于均匀分布。

def counting_sort(a):
    if not a:
        return a
    lo, hi = min(a), max(a)
    cnt = [0] * (hi - lo + 1)
    for x in a:
        cnt[x - lo] += 1
    out = []
    for i, c in enumerate(cnt):
        out.extend([i + lo] * c)
    return out

print(counting_sort([5, 2, 9, 1, 5, 6]))   # 输出 [1, 2, 5, 5, 6, 9]
​

面试中的高频追问是："堆排序也是 n log n 且空间 O(1)，为什么工业界不如快排常见？"答案在缓存：快排的分区是顺序扫描，缓存命中率高；堆排序父子下标来回跳跃，缓存极不友好。复杂度相同，常数与硬件行为不同——这提醒我们大 O 之上还有真实机器。

本节要点回顾

• 第一代平方级并非无用：插入排序在小数组与基本有序数据上是工业实现的最后一环；
• 分治是代际跃迁：归并稳定可预测、快排平均最快且原地，取舍看稳定性与最坏保证；
• 快排的退化与对策：固定基准遇已序输入退化到平方级，随机化或三数取中可解；
• 比较排序下界是 n log n：决策树论证要能口头复述，它是"还能再优化吗"的终点；
• 绕开下界靠不比较：计数、基数、桶排序用值当地址换线性时间，代价是值域或分布前提。

本章进化链到此收官。下一章把视角从数据结构翻向算法策略：递归与分治将把归并排序里埋的伏笔正式展开。