数据结构与算法 / 系统课时
基数排序
基数排序
基数排序不直接比较两个元素的大小,而是按个位、十位、百位等“数字位”重复整理数据。本课使用最低位优先的 LSD 方法完成非负整数排序,并说明位数、基数与稳定排序之间的关系。
学习目标
- 理解 LSD 基数排序按位处理的执行顺序。
- 掌握稳定计数排序在每一位上的作用。
- 能够根据最大位数和基数分析时间、空间复杂度。
核心原理与执行流程
设待排序整数使用基数 表示,最大值共有 位。LSD 基数排序从最低位开始,依次按第 位、第 位直到第 位排序。每一轮都必须使用稳定排序,使上一轮已经建立的低位顺序在处理高位时不会被破坏。
例如,数组 170、45、75、90、802、24、2、66 先按个位分组,再按十位分组,最后按百位分组。完成全部轮次后,数字会按整体大小有序。

一轮按位计数排序可以分为四步:统计每个数字出现次数;把次数转换为累计位置;从右向左扫描原数组并写入输出数组;将本轮结果复制回原数组。从右向左写入是保证稳定性的关键。
复杂度与边界
当数组长度为 、基数为 、最大数字位数为 时,时间复杂度为 ,额外空间复杂度为 。在固定宽度整数且 b 固定的成本模型中,位数有固定上界,因此时间对 n 为线性。对 Python 的任意精度整数,除法和求余也要按位宽分析。
增大基数可以减少轮数,却会扩大计数数组。若基数从 10 改为 256,每轮处理的桶更多,但位数通常更少。工程中需要在轮数、缓存占用和实现复杂度之间权衡。
本课示例只处理非负整数。处理带符号键时可以统一按最小键平移,平移前后次序一致。固定宽度语言需要为差值选足够宽的类型。若按绝对值处理负键,整体逆序会把等键记录也翻转,必须单独保留组内次序。
完整可运行示例
将下面代码保存为 radix_sort_demo.py。内部按位函数使用累计位置稳定回填。入口一次缓存键并检查键和基数,返回原列表。上限 65536 是本例的桶数预算。全为 0 时无需按位扫描,但仍要验证和保留顺序。
def _counting_sort_by_digit(records, exponent, base):
output = [None] * len(records)
counts = [0] * base
for number, _ in records:
counts[(number // exponent) % base] += 1
for i in range(1, base):
counts[i] += counts[i - 1]
for entry in reversed(records):
digit = (entry[0] // exponent) % base
counts[digit] -= 1
output[counts[digit]] = entry
return output
def radix_sort(values, base=10, key=lambda value: value):
if type(base) is not int or not 2 <= base <= 65536:
raise ValueError("本例要求整数基数在 2 到 65536 之间")
records = [(key(value), value) for value in values]
if any(type(number) is not int or number < 0 for number, _ in records):
raise ValueError("键必须为非负整数")
maximum = max((number for number, _ in records), default=0)
exponent = 1
while maximum // exponent > 0:
records = _counting_sort_by_digit(records, exponent, base)
exponent *= base
values[:] = [value for _, value in records]
return values
if __name__ == "__main__":
numbers = [170, 45, 75, 90, 802, 24, 2, 66]
print("排序前:", numbers)
print("排序后:", radix_sort(numbers))
tagged = [(21, "A"), (11, "B"), (21, "C"), (11, "D")]
print("带标签:", radix_sort(tagged, key=lambda row: row[0]))运行命令如下。
python radix_sort_demo.py预期输出
排序前: [170, 45, 75, 90, 802, 24, 2, 66]
排序后: [2, 24, 45, 66, 75, 90, 170, 802]
带标签: [(11, 'B'), (11, 'D'), (21, 'A'), (21, 'C')]若结果在某一轮后看似“局部有序”但最终错误,应优先检查按位排序是否稳定,以及写入输出数组时是否从右向左扫描。
本课总结
- LSD 基数排序从低位到高位处理,每一轮都依赖稳定排序保留之前的顺序。
- 复杂度由元素数量、基数和最大位数共同决定,并非只取决于数组长度。
- 基数排序适合位数有限、取值结构明确的整数或字符串键,不适合直接处理任意比较规则。
下一课预告
下一课将学习“桶排序”,重点理解如何根据数据分布把元素分散到多个桶中,并分析均匀分布假设对性能的影响。