10.2 排序对比：从约束到选择

第 10 章 · 排序选型｜前置：基础排序、归并排序、快速、堆与非比较排序｜下一章：二分搜索。本页不再堆算法代码，而把稳定性、最坏界、内存、键域与分布整理成可审计的选择依据。

工具架前先写约束

真正能改变选择的条件有五类：

1. 是否必须稳定，尤其是多字段排序；
2. 能否接受期望界，还是必须限制最坏时间；
3. 可用内存是否容得下 O(n) 缓冲区；
4. 键是否为范围可控的整数或可拆分数位；
5. 输入的已有顺序、重复率和分布是否经过测量。

固定写“n 小于 100 就用插入”不是工程结论。阈值依赖语言、元素大小、比较器成本、硬件和实现，只能用目标环境基准确定。

一份可审计的建议器

这个函数整理候选与理由，不测量输入，也不执行排序。integer_range 是 max_key-min_key+1；counting_range_limit 是调用者根据当前 n、内存预算和基准给出的范围上限，没有默认固定阈值。此建议器还要求 k <= n，保守地保证计数部分为线性规模；更宽范围可以单独评估。未提供上限时，不推荐计数排序。

memory="tight" 在此明确要求排序核心 O(1) 辅助空间；worst_case="bounded" 要求 O(n log n) 级别的最坏界，而非只保证期望界。它们不表示绝对的毫秒或字节预算，也不豁免前页包装层的 Θ(n) 复制成本。

def recommend_sort(
    *,
    stable,
    integer_range,
    item_count=0,
    memory="normal",
    worst_case="expected",
    counting_range_limit=None,
):
    if not isinstance(stable, bool):
        raise TypeError("stable must be a boolean")
    if not isinstance(item_count, int):
        raise TypeError("item_count must be an integer")
    if item_count < 0:
        raise ValueError("item_count must be non-negative")
    for name, value in (("integer_range", integer_range),
                        ("counting_range_limit", counting_range_limit)):
        if value is not None:
            if not isinstance(value, int):
                raise TypeError(f"{name} must be an integer or None")
            if value < 1:
                raise ValueError(f"{name} must be positive")
    if memory not in {"normal", "tight"}:
        raise ValueError("memory must be 'normal' or 'tight'")
    if worst_case not in {"expected", "bounded"}:
        raise ValueError("worst_case must be 'expected' or 'bounded'")
    if item_count == 0:
        return {"algorithm": "no sort", "reasons": ["input is empty"]}

    if (integer_range is not None and counting_range_limit is not None
            and integer_range <= counting_range_limit
            and integer_range <= item_count and memory == "normal"):
        return {
            "algorithm": "counting sort",
            "reasons": [
                "integer keys have a measured range",
                "the range fits the caller's explicit counting-sort limit",
            ],
        }
    if memory == "tight":
        if stable:
            raise ValueError(
                "this shortlist has no stable O(1)-auxiliary sort with an "
                "O(n log n) bound; review algorithms or relax a constraint"
            )
        return {
            "algorithm": "heapsort",
            "reasons": [
                "textbook auxiliary space is O(1)",
                "worst-case time is Θ(n log n)",
            ],
        }
    if stable:
        return {
            "algorithm": ("stable library sort with a documented worst-case bound"
                          if worst_case == "bounded" else "stable library sort"),
            "reasons": [
                "stability is required",
                "verify the requested time bound in the selected library",
            ],
        }
    if worst_case == "bounded":
        return {
            "algorithm": "library sort with a documented worst-case bound",
            "reasons": [
                "stability is not required",
                "the deployment requires a worst-case guarantee",
            ],
        }
    return {
        "algorithm": "library sort; benchmark against randomized quicksort",
        "reasons": [
            "expected time is acceptable",
            "no budgeted integer-domain advantage was established",
        ],
    }

例如，已测得当前十万条记录可承受范围上限 1024 时：

choice = recommend_sort(
    stable=True, integer_range=101, item_count=100_000,
    worst_case="bounded", counting_range_limit=1024,
)
assert choice["algorithm"] == "counting sort"
choice = recommend_sort(
    stable=False, integer_range=None, item_count=100_000,
    memory="tight", worst_case="expected",
)
assert choice["algorithm"] == "heapsort"

第二个选择仍用堆排：即便能接受期望时间，递归快排的 O(log n) 栈也不满足这里严格的 O(1) 空间约束。

保证矩阵

算法	最好/期望/最坏时间	稳定	教科书算法辅助空间	失效条件
插入	Θ(n) / Θ(n²) / Θ(n²)	是	O(1)	逆序对很多时移动量大
归并	Θ(n log n) / 同左 / 同左	是	O(n)	内存预算不容许缓冲区
随机三路快排	期望 O(n log n)，最坏 O(n²)	否	前页实现最坏 O(log n) 栈	不允许最坏退化或要求稳定
堆排	最坏 Θ(n log n)，建堆是 Θ(n)	否	O(1)	需要稳定输出
计数	Θ(n + k)	可稳定	Θ(n + k)	k 远大于 n
LSD 基数	Θ(d(n + b))	每趟稳定则稳定	Θ(n + b)	键无法可靠拆成有限数位
桶	均匀分桶期望 O(n+m+n²/m)，最坏 O(n²+m)	看桶内算法	Θ(n + m)	分布偏斜、桶负载集中

表中插入排序的期望假定互异键均匀随机排列；归并指前页固定二分版本。基数排序 d 至少为 1；桶数 m 也进入时间成本，只有合适负载与 m=Θ(n) 才能得到线性期望。空间不含统一 API 的 Θ(n) 辅助记录与 Θ(n) 输出列表，亦不把“最坏 Θ(n log n)”误读成每个输入都耗费这么多。

三个容易误判的场景

小范围整数

十万条 0 到 100 的成绩记录，其 k 只有 101。内存允许且需要稳定时，计数排序有清晰的数据域优势。若只有十条记录却横跨 64 位键空间，同一个名字不再合适。

内存紧，但又要求稳定

把堆排序当成必然答案，会漏掉稳定性冲突。标准堆排不稳定；稳定插入排序能用 O(1) 辅助空间，但最坏要 Θ(n²)。因此还要问是否要求 O(n log n)：本页候选清单没有同时满足这三项的算法，报错只表示清单不足，不是“不可能”的数学证明。更复杂的原地稳定合并算法需要单独评估；数据本来就放不进内存时，再考虑外部排序和数据流设计。

近似均匀

桶排序的线性期望来自分布模型。先画直方图、看最大桶负载和桶数相对 n 的比例；没有测量，“均匀”只是愿望。

标准库边界

优先使用标准库。Python 文档承诺稳定，并说明 key 每个元素只调用一次；Java SE 25 的 Arrays.sort(Object[]) 文档承诺稳定。具体采用哪种混合算法通常是版本化 implementation note，升级版本时应重查，不要从旧实现名反推永久行为。

来源：

• Python Sorting HOWTO
• Java SE 25 Arrays
• Princeton quicksort
• Princeton heapsort
• Princeton radix sorts

收起排序工具架

排序选型不是背一句“最快”，而是留下可复查的理由：键域从哪里来，稳定性由谁要求，最坏界为何必要，内存预算是多少，基准在哪个目标环境上跑。约束改变，就重新选择；通用库通常是第一基线，专用算法必须用更窄的输入合同换取优势。

前一篇可回看 第 10 章排序实现。下一章进入 二分搜索与边界查找。