排序算法
排序先定义顺序,再选择实现。订单列表可能按优先级降序、创建时间升序排列;同样优先级和时间的记录是否保留到达顺序,决定是否需要稳定性。仅把整数排对,不能证明业务记录没有丢失、重复或在平分时乱序。
大多数工程代码应先使用语言或数据库提供的排序入口。学习基础算法的价值在于理解比较次数、写入、稳定性和内存的来源,判断特定实现是否满足合同,而不是按固定数据量阈值手写替换标准库。
比较键与稳定性
假设订单 A 的键为“优先级 2、时间 10”,B 为“1、5”,C 为“2、10”,D 为“2、8”。按优先级降序、时间升序后是 D、A、C、B;A 与 C 的完整排序键相同,稳定排序保留 A 先于 C。
若把编号也加入排序键,就主动定义了第三层顺序,不再依赖这两个记录的稳定性。反过来,稳定排序也不能凭空保证多次数据库查询返回相同顺序:原始输入本身变化时,平分结果可能变化。分页或跨次导出通常需要唯一的最终排序键及一致快照。
Python 中可写 sorted(orders, key=lambda x: (-x.priority, x.created)),返回新列表;orders.sort(key=...) 修改列表并返回 None。负号适用于数值字段,不适用于任意字符串或对象。比较关系必须一致并具传递性,NaN、混合类型和有副作用的比较器需在入口处理。
完整实现:稳定归并与一次取键
下面的 Python 3 教学实现把记录与排序键配对,递归过程中不重复调用 key。它接收可迭代记录,返回新列表,不改变输入;要求 key 返回可一致比较的值,且排序期间记录和排序键不发生修改。
python
from dataclasses import dataclass
def merge_sort_by(records, key):
entries = [(key(record), record) for record in records]
buffer = [None] * len(entries)
def solve(lo, hi):
if hi - lo <= 1:
return
mid = lo + (hi - lo) // 2
solve(lo, mid)
solve(mid, hi)
i, j, out = lo, mid, lo
while i < mid and j < hi:
if entries[j][0] < entries[i][0]:
buffer[out] = entries[j]
j += 1
else:
buffer[out] = entries[i]
i += 1
out += 1
while i < mid:
buffer[out] = entries[i]
i += 1
out += 1
while j < hi:
buffer[out] = entries[j]
j += 1
out += 1
for out in range(lo, hi):
entries[out] = buffer[out]
solve(0, len(entries))
return [record for _, record in entries]
@dataclass(frozen=True)
class Order:
order_id: str
priority: int
created: int
orders = (
Order("A", 2, 10), Order("B", 1, 5),
Order("C", 2, 10), Order("D", 2, 8),
)
ordered = merge_sort_by(orders, key=lambda x: (-x.priority, x.created))
assert tuple(x.order_id for x in ordered) == ("D", "A", "C", "B")
assert tuple(x.order_id for x in orders) == ("A", "B", "C", "D")
assert merge_sort_by((), key=lambda x: x) == []
print(tuple(x.order_id for x in ordered))输出 ('D', 'A', 'C', 'B')。合并时仅当右键严格更小时取右边;其余情况先取左边,因此相同键的原顺序得以保留。只比较缓存键,不会在平分时继续比较业务对象。key 抛异常会中断排序,程序不把它吞成空结果。
按取键与比较近似常数计,时间为 Θ(n log n),取键 n 次;若单次取键成本为 K,总成本还包含 O(nK)。记录、缓存键、缓冲区、结果列表均与 n 成正比,递归深度 O(log n)。它通过共享缓冲区减少重复分配,仍需 O(n) 辅助空间;“修改原数组”与“只用常量辅助空间”不是同一个含义。
常见算法各在维护什么
| 算法 | 运行过程与不变量 | 时间与空间边界 |
|---|---|---|
| 冒泡 | 相邻逆序交换,每轮固定一个末端位置 | 有提前停止时最好 Θ(n),最坏 Θ(n²),迭代版 O(1)空间 |
| 插入 | 已处理前缀有序,把下一项插到正确位置 | 已有序时 Θ(n),最坏 Θ(n²),迭代版 O(1)空间 |
| 选择 | 从未处理部分找最小项,与前端交换 | Θ(n²)比较、O(n)交换;常见交换版不稳定 |
| 快排 | 按基准分区,只递归未确定顺序的区间 | 平衡或随机期望 Θ(n log n),最坏 Θ(n²);普通递归最坏栈 O(n) |
| 归并 | 分别排序两半,再线性合并 | 常见数组版 Θ(n log n),O(n)辅助空间 |
| 堆排 | 最大堆顶与末端交换,缩小堆并下沉 | 建堆 O(n),全排序 O(n log n);迭代下沉可 O(1)辅助空间 |
| 计数 | 统计有限整数键,利用累计位置分配输出 | O(n+R),R为键范围;稳定记录版通常需 O(n+R)空间 |
| 桶 | 按范围分桶,各桶内部排序,再合并 | 依赖分布与桶内算法,不能无条件承诺线性 |
| 基数 | 按位或字符组分轮排序 | 常见 LSD 版本每轮必须稳定,O(d(n+b)),d为轮数、b为基数 |
稳定性取决于实现。相等时不交换的冒泡、不越过相等项的插入、相等先取左侧的归并通常稳定;选择、堆排、常见原地快排通常不稳定。计数、桶和基数也需要正确保存原记录相对顺序,不能仅凭算法名称保证稳定。
插入排序的移动量与逆序对相关,适合小区间或部分有序数据;冒泡也能提前停止,但不应据此默认选择它处理“几乎有序”的工程集合。标准库往往组合多种策略,具体实现和合同要区分,不能统一声称所有语言都使用同一种混合算法。
分区与内存容易算错的地方
三路快排可维护 [lo,lt)<pivot、[lt,i)==pivot、[i,gt) 未检查、[gt,hi)>pivot。循环结束 i=gt,递归区间应是 [lo,lt) 和 [gt,hi)。如果把 gt 当成最后一个等值位置,再从 gt+1 开始,会漏排第一个大值。区间闭开约定必须从分区一直贯穿递归调用。
固定末项作基准,在已排序或大量重复输入上可能反复得到极不平衡分区,时间与递归栈都会退化。随机基准降低特定输入导致退化的风险,但不消除最坏界;三路分区能减少相等键上的无效递归。工程实现还可只递归较短侧、迭代处理较长侧以限制栈深,或设置深度阈值切换算法。
堆排序常被称为原地,但用递归 heapify 会额外占 O(log n) 调用栈;表中的 O(1)空间对应迭代下沉。归并即使最后把结果写回原数组,也可能分配左右切片和临时数组。讨论内存时应分别算输入、输出、缓存键、递归栈和临时副本,不能只看函数是否返回同一个对象。
非比较排序何时合算
计数排序的成本依赖 R=max-min+1。只有两个值 [0, 10**12] 也不应分配一万亿个计数槽;入口应限定整数、合理范围和可用内存。允许负数时可减去最小值作为偏移,不能直接当数组下标。
桶排序的期望线性通常依赖分布较均匀、桶数与 n 的关系,以及桶内排序成本。本来就集中到一个桶时,退化到桶内算法成本:插入排序可能 O(n²),使用 O(n log n) 排序则是另一种上界。桶数必须为正,全部相等、无穷与 NaN 都需要明确定义,浮点分桶还要防边界误差。
十进制最低位优先的基数排序示例通常只支持非负整数,不能直接拿负数做相同除法取位。每轮稳定才能保留已处理低位的顺序。固定宽度、编码方式、符号位与文本字符顺序会改变实现,不能把“整数版本可跑”扩展为任意字符串都适用。
大文件排序与分页
文件不能装入内存时,可以按内存预算生成有序段,再用堆进行多路归并。若有 r 段,总计 n 项,单轮合并通常 O(n log r),堆中每段最多放一个当前项;文件缓冲、句柄和输出编码也是资源成本。
不能一次打开任意数量的临时文件。设置合并扇入上限,必要时多轮合并;用上下文管理保证异常也关闭句柄、清理临时段。输出先写到目标文件同一文件系统中的临时路径,完成后再替换,防止读取与写入同一路径时截断输入。空文件、非法行、磁盘满和中断恢复都应有明确结果。
只需要前 k 项时可以评估堆选择,避免全量排序;使用 heapq.nsmallest 等现成入口时仍需考虑 k 与 n 的关系。数据库分页则应在查询层明确 ORDER BY 和稳定的唯一边界,不能先任意取一页再排序,声称它就是全局第一页。
验证顺序、完整性与稳定性
正确性至少包含三个方面:排序键单调,输出是输入的排列,相等键的记录满足稳定性合同。只验证升序可能漏掉记录丢失;只比较值也看不到重复键之间的顺序变化。
本例可与 sorted(records, key=...) 对照,并给每条记录保留独立编号。测试空输入、单项、相等键、逆序、部分有序与负数键,同时检查 key 每条记录只调用一次、原输入未修改。性能测量应统一数据副本、取键和输出的计时范围,不能用一次运行或固定“50/10000项”阈值宣布哪种算法永远最好。
