数据结构与算法 / 系统课时

基数排序

基数排序

基数排序不直接比较两个元素的大小,而是按个位、十位、百位等“数字位”重复整理数据。本课使用最低位优先的 LSD 方法完成非负整数排序,并说明位数、基数与稳定排序之间的关系。

学习目标

  • 理解 LSD 基数排序按位处理的执行顺序。
  • 掌握稳定计数排序在每一位上的作用。
  • 能够根据最大位数和基数分析时间、空间复杂度。

核心原理与执行流程

设待排序整数使用基数 bb 表示,最大值共有 dd 位。LSD 基数排序从最低位开始,依次按第 11 位、第 22 位直到第 dd 位排序。每一轮都必须使用稳定排序,使上一轮已经建立的低位顺序在处理高位时不会被破坏。

例如,数组 170、45、75、90、802、24、2、66 先按个位分组,再按十位分组,最后按百位分组。完成全部轮次后,数字会按整体大小有序。

LSD 基数排序按位处理流程

一轮按位计数排序可以分为四步:统计每个数字出现次数;把次数转换为累计位置;从右向左扫描原数组并写入输出数组;将本轮结果复制回原数组。从右向左写入是保证稳定性的关键。

复杂度与边界

当数组长度为 nn、基数为 bb、最大数字位数为 dd 时,时间复杂度为 O(d(n+b))O(d(n+b)),额外空间复杂度为 O(n+b)O(n+b)。在固定宽度整数且 b 固定的成本模型中,位数有固定上界,因此时间对 n 为线性。对 Python 的任意精度整数,除法和求余也要按位宽分析。

增大基数可以减少轮数,却会扩大计数数组。若基数从 10 改为 256,每轮处理的桶更多,但位数通常更少。工程中需要在轮数、缓存占用和实现复杂度之间权衡。

本课示例只处理非负整数。处理带符号键时可以统一按最小键平移,平移前后次序一致。固定宽度语言需要为差值选足够宽的类型。若按绝对值处理负键,整体逆序会把等键记录也翻转,必须单独保留组内次序。

完整可运行示例

将下面代码保存为 radix_sort_demo.py。内部按位函数使用累计位置稳定回填。入口一次缓存键并检查键和基数,返回原列表。上限 65536 是本例的桶数预算。全为 0 时无需按位扫描,但仍要验证和保留顺序。

python
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]))

运行命令如下。

bash
python radix_sort_demo.py

预期输出

text
排序前: [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 基数排序从低位到高位处理,每一轮都依赖稳定排序保留之前的顺序。
  • 复杂度由元素数量、基数和最大位数共同决定,并非只取决于数组长度。
  • 基数排序适合位数有限、取值结构明确的整数或字符串键,不适合直接处理任意比较规则。

下一课预告

下一课将学习“桶排序”,重点理解如何根据数据分布把元素分散到多个桶中,并分析均匀分布假设对性能的影响。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

基数排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通