专题进阶 · 排序算法推荐总顺序 · 第 33 / 148 课

用稳定性归纳证明 LSD 基数排序,处理位数、基数与非负整数约定。

先学会这些,再进入本课 计数排序
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 排序算法

基数排序Radix Sort

按位进行稳定排序;d 位、基数 b 时常见成本 O(d(n+b))。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用稳定性归纳证明 LSD 基数排序,处理位数、基数与非负整数约定。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

[21,13,11,23] 只按个位排会打乱十位。为什么先排低位,最后却能得到完整顺序?

02一步步得到方法

每一轮只处理一位

LSD 从最低位开始。十进制位可由 (x//exp)%10 提取,exp 依次为 1、10、100。每轮使用稳定排序,使当前位相同的元素保留上一轮建立的低位顺序。

排完个位后低一位有序;再稳定排十位后,先按十位分组,组内保留个位顺序,于是低两位有序。最高位处理完,所有有效位共同决定了整数顺序。

位数与数据模型要写出来

短数字可以视为左侧补零,例如 7 表示 007。负数不能直接套这个数位规则;可分离符号或使用有符号整数的专门映射。本课明确只接受非负整数。

基数越大,每轮处理更多信息、轮数越少,但桶数组更大。真实实现常用 2 的幂作基数,方便位操作;理论成本 O(d(n+b)) 同时包含轮数 d 与基数 b。

稳定性让已处理的低位信息留下来

从个位排到十位时,十位相同的元素必须保持上一轮的个位顺序。这样十位决定主次序,个位决定平局,归纳得到逐位处理后的整体有序。

位数 d、进制 b 和输入长度 n 共同决定 O(d(n+b)) 成本。负数、变长字符串和浮点数需要设计符合目标顺序的编码,不能直接把非负整数版本套过去。

03把一个小例子完全算清楚

[21,13,11,23],按个位再按十位。

步骤计算与状态为什么这样做
个位分桶桶 1:[21,11];桶 3:[13,23]保持原先后
收集[21,11,13,23]个位有序
十位分桶桶 1:[11,13];桶 2:[21,23]保留已建立的个位次序
收集[11,13,21,23]低两位整体有序

窄屏可左右滑动表格,阅读完整计算与理由。

不是低位更重要,而是后处理的高位决定组序,稳定性保留组内低位信息。

04为什么这个方法成立

  1. 一轮后按最低位有序。
  2. 假定前 k 位已排序,稳定地按第 k+1 位分组,则组内仍保持低 k 位顺序。
  3. 归纳到全部位数后得到完整数值顺序。

05把推导翻译成代码

Python · 可独立运行的教学实现

def radix_sort(values):
    a = list(values)
    if any(x < 0 for x in a):
        raise ValueError("nonnegative integers required")
    maximum = max(a, default=0)
    exp = 1
    while maximum // exp:
        buckets = [[] for _ in range(10)]
        for x in a:
            buckets[(x // exp) % 10].append(x)
        a = [x for b in buckets for x in b]
        exp *= 10
    return a

逐个理解关键决定

append(x)
同桶按输入顺序进入,收集时不反转,保证稳定。
maximum // exp
最大值这一位以上为零时停止;空数组和全零数组直接返回。

06时间、空间与实现范围

十进制 d 位,时间 O(d(n+10)),工作存储 O(n+10)。

若整数位数不固定,d 也随数值规模增长,不能无条件写成 O(n)。本 Python 实现按通常字长模型说明循环成本。

07改变条件,检查哪里会出错

某一位使用不稳定排序

会丢失先前低位顺序,例如同十位的 11、13 被反转。

直接套用到负数或浮点数

编码顺序与数值顺序可能不同,需要另外设计保序映射。

用不稳定的单轮排序

高位相等时低位已建立的相对顺序可能丢失,最终结果不再保证有序。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

[10,2,1] 第一轮得到什么?

需要一点提示

缺失十位按零处理。

查看解析与答案

个位排序后 [10,1,2];十位排序后 [1,2,10]。

练习 2 · 边界与辨析

可否先排最高位再用同样方式反复全局排序?

需要一点提示

最后一次排序会成为主键。

查看解析与答案

不能照搬。MSD 需要在相同高位的桶内递归处理低位,而不是每轮重新全局分组。

练习 3 · 变式与迁移

基数从 10 改为 256 的取舍?

需要一点提示

轮数与桶数同时变化。

查看解析与答案

轮数减少,桶初始化与内存成本增大;适合字节表示时还便于位运算,效果需按数据规模判断。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 排序

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。