很多算法教材都会给出一个重要结论：基于比较的排序算法，在最坏情况下需要执行至少 Ω(n log n) 次比较。于是，一个常见但不严谨的推论出现了：排序不可能突破 O(n log n)。
问题在于，这个下界只约束“通过比较两个元素来获得顺序信息”的算法。如果输入不是任意对象，而是一定范围内的整数、定长字符串或可以拆分为若干位的键，算法就可能利用数组随机访问、整数位或键空间结构，不再只从比较结果中获取信息。
计数排序、桶排序和基数排序并没有推翻复杂度下界，而是改变了计算模型。理解这一区别，比背诵几个复杂度公式更重要。它能帮助我们回答实际问题：面对用户编号、时间戳、状态码或定长编码，应该继续使用通用比较排序，还是利用数据约束换取更低的渐进复杂度？
比较排序的下界从哪里来
考虑 n 个互不相同的元素。它们可能形成 n! 种排列。一个只允许比较两个元素的确定性排序算法，每次比较最多产生“小于”和“大于”两种有效结果，因此执行过程可以表示为一棵二叉决策树。
决策树至少需要 n! 个叶子，才能区分所有可能的输入排列。若树高为 h，则叶子数最多为 2^h，因此：
2^h >= n!
h >= log2(n!)
根据 Stirling 公式，log2(n!) 属于 Θ(n log n)，所以任何确定性的比较排序在最坏情况下都需要 Ω(n log n) 次比较。允许相等元素会改变具体路径，却不会让通用比较排序摆脱这一渐进下界。
这里有三个关键前提：
- 输入的顺序信息只能通过比较获得。
- 算法必须正确处理一般输入，而不是只处理很小的键空间。
- 衡量的是比较次数，实际运行时间还会受到内存访问、缓存、对象创建和语言运行时影响。
归并排序、堆排序能达到 O(n log n) 的最坏时间复杂度，因此在比较模型内已经达到渐进意义上的最优。快速排序平均为 O(n log n)，但具体最坏复杂度及其出现条件取决于枢轴策略和实现方式。
非比较排序改变了什么
假设输入是非负整数，并且最大值为 k。计数排序可以建立长度为 k + 1 的计数数组，把整数 x 直接映射到下标 x。扫描输入和计数数组后即可恢复有序结果，时间复杂度为 O(n + k)，额外空间为 O(k)。
它之所以可能快于 O(n log n)，是因为一次数组寻址携带的信息不再局限于一个二元比较结果。算法直接使用了整数值与内存位置之间的映射。
不过，O(n + k) 不等于无条件优于 O(n log n)。如果只有一万个元素，键值却可能接近数十亿，分配与扫描巨大计数数组通常并不合理。计数排序适合键空间相对紧凑、范围可以提前确定或安全推导的场景。
基数排序则把整数拆成多个“位”。以十进制为例，可以依次按个位、十位、百位排序。若每一轮使用稳定的计数排序，并从低位到高位处理，前面低位建立的次序会在后续轮次中被保留。设基数为 b，最大值需要 d 位，复杂度通常写作 O(d(n + b))。
这同样带有条件：d 是否可视为常数，取决于整数位宽或输入上界。在固定宽度整数模型下，位数有固定上限；在任意精度整数或无限增长的字符串键上，位数不能被无条件忽略。
实现三个可对照的排序算法
下面的程序只依赖 Python 标准库，包含归并排序、计数排序和面向非负整数的 LSD 基数排序。代码主动校验输入约束，避免把不支持的负数或异常参数静默处理成错误结果。
from __future__ import annotations
from collections.abc import Sequence
def merge_sort(values: Sequence[int]) -> list[int]:
if len(values) <= 1:
return list(values)
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result: list[int] = []
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
def counting_sort(values: Sequence[int]) -> list[int]:
if not values:
return []
if any(value < 0 for value in values):
raise ValueError("counting_sort only accepts non-negative integers")
maximum = max(values)
counts = [0] * (maximum + 1)
for value in values:
counts[value] += 1
result: list[int] = []
for value, count in enumerate(counts):
result.extend([value] * count)
return result
def radix_sort(values: Sequence[int], base: int = 256) -> list[int]:
if base < 2:
raise ValueError("base must be at least 2")
if any(value < 0 for value in values):
raise ValueError("radix_sort only accepts non-negative integers")
if not values:
return []
result = list(values)
maximum = max(result)
factor = 1
while maximum // factor > 0:
counts = [0] * base
output = [0] * len(result)
for value in result:
digit = (value // factor) % base
counts[digit] += 1
for index in range(1, base):
counts[index] += counts[index - 1]
# 逆序放置使本轮计数排序保持稳定。
for value in reversed(result):
digit = (value // factor) % base
counts[digit] -= 1
output[counts[digit]] = value
result = output
factor *= base
return result
归并排序不依赖整数范围，因而适用于能够定义全序关系的对象。这里的计数排序为了突出核心原理，只恢复整数值；如果要排序带有附属数据的记录，应先计算前缀和，再按稳定顺序把完整记录放入输出数组。
建立可执行的正确性验证
性能测试之前必须先验证结果。否则，一个遗漏边界情况但运行很快的函数没有比较价值。把以下代码追加到同一文件中：
import random
def verify() -> None:
fixed_cases = [
[],
[0],
[2, 1],
[5, 5, 5],
[0, 255, 256, 65535, 1, 256],
list(range(100)),
list(range(99, -1, -1)),
]
rng = random.Random(20260803)
random_cases = [
[rng.randrange(0, 10_000) for _ in range(size)]
for size in (3, 10, 101, 1000)
]
for case in fixed_cases + random_cases:
expected = sorted(case)
assert merge_sort(case) == expected
assert counting_sort(case) == expected
assert radix_sort(case) == expected
if __name__ == "__main__":
verify()
print("all checks passed")
执行步骤如下：
python3 sorting_models.py
固定随机种子是为了让失败用例可复现，不表示这些样本能够证明算法对所有输入都正确。完整正确性仍需要基于循环不变量、递归结构和输入约束进行证明；测试用于发现实现错误和回归。
设计不误导的性能实验
若要观察键空间对算法的影响，可以使用 timeit 分别生成“范围紧凑”和“范围稀疏”的整数。不要预先写死预期耗时，也不要根据一次运行宣布某种算法绝对更快。
from timeit import repeat
import random
def benchmark(label: str, values: list[int]) -> None:
algorithms = {
"builtin": lambda: sorted(values),
"merge": lambda: merge_sort(values),
"counting": lambda: counting_sort(values),
"radix": lambda: radix_sort(values),
}
print(f"\n{label}: n={len(values)}, max={max(values, default=0)}")
for name, operation in algorithms.items():
samples = repeat(operation, number=1, repeat=5)
print(f"{name:>8}: min={min(samples):.6f}s")
def run_benchmarks() -> None:
rng = random.Random(20260803)
compact = [rng.randrange(0, 10_000) for _ in range(100_000)]
sparse = [rng.randrange(0, 100_000_000) for _ in range(100_000)]
benchmark("compact key space", compact)
benchmark("sparse key space", sparse)
可以在主入口的 verify() 之后调用 run_benchmarks()。实验应在同一台机器、同一 Python 解释器和近似空闲的环境中进行，并记录输入规模、键范围和重复次数。
需要特别注意：Python 内置 sorted 是经过高度优化的通用排序实现，而示例算法运行在 Python 字节码层。即使某个手写算法拥有更好的渐进表达式，也可能因为解释器开销、内存分配和缓存局部性而更慢。因此，这个实验用于观察输入分布和计算模型的影响，不能替代特定生产环境下的基准测试。
工程选型的判断顺序
选择排序方法时，可以依次检查以下条件：
- 键是否具有可利用结构：任意对象通常需要比较；整数、定长字节串和有限枚举可能支持直接寻址或分位处理。
- 键空间是否足够紧凑：计数排序需要考虑最大值、最小值以及二者之差，而不只是元素数量。
- 内存上限是否明确：来自外部的最大键值不能未经检查就用于数组分配，否则可能导致内存耗尽。
- 是否要求稳定排序：多字段排序、按时间保持同优先级记录原顺序等场景通常需要稳定性。
- 数据是否已经部分有序：成熟标准库可能针对现实输入分布做了优化，不能只凭渐进复杂度替换它。
- 数据是否放得进内存：外部排序、数据库索引扫描和分布式排序属于另一组约束，不能直接套用内存排序结论。
在大多数业务代码中，标准库排序仍应作为默认选择。只有当分析或测量表明排序确实是瓶颈，并且键范围、稳定性和内存预算都清晰时，专用整数排序才值得引入。
常见问题
有负整数还能使用计数排序吗？
可以。设最小值为 m、最大值为 k，把值 x 映射到下标 x - m，数组长度变为 k - m + 1。实现前必须检查这个差值，避免极端输入触发过大的内存分配。
基数越大，算法一定越快吗？
不一定。增大基数可以减少轮数，却会扩大计数数组，并增加初始化和缓存访问成本。适合的基数与数据位宽、实现语言、缓存结构和输入规模有关，需要在目标环境中测量。示例使用 256，只代表每轮处理一个八位数字的实现选择。
哈希表能否让任意对象实现线性排序？
哈希表可以聚合相同键，但哈希值本身不提供全序关系。要按大小输出任意对象，仍需获得键之间的顺序信息。只有键空间可以按顺序枚举，或键能被结构化拆分时，才可能绕开通用比较排序的模型限制。
O(n) 是否一定比 O(n log n) 快？
不是。大 O 表示输入增长时的渐进行为，会隐藏常数、内存访问和预处理成本。对于有限规模数据，高度优化的 O(n log n) 实现完全可能快于解释型语言中手写的 O(n) 算法。
为什么不能直接用最大整数创建计数数组？
输入值可能来自文件、网络或用户请求。若攻击者提交一个极大整数，maximum + 1 的数组分配可能耗尽内存。生产实现应限制可接受的键跨度，并在超限时回退到通用排序或拒绝处理。
总结
Ω(n log n) 是比较排序的下界，不是所有排序问题的统一下界。计数排序和基数排序通过利用整数键、随机访问和稳定分位处理，改变了信息获取方式，因此可以在满足特定约束时获得 O(n + k) 或 O(d(n + b)) 的复杂度。
这种优势并非免费：键空间、位数、额外内存、稳定性、安全边界和运行时常数都会影响最终结果。可靠的工程决策应先确认输入模型，再证明实现正确，最后在真实数据分布与目标环境中测量。复杂度分析负责排除不合适的方向，基准测试负责决定具体实现。
