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为什么这个方法成立
- 一轮后按最低位有序。
- 假定前 k 位已排序,稳定地按第 k+1 位分组,则组内仍保持低 k 位顺序。
- 归纳到全部位数后得到完整数值顺序。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
[10,2,1] 第一轮得到什么?
需要一点提示
缺失十位按零处理。
查看解析与答案
个位排序后 [10,1,2];十位排序后 [1,2,10]。
可否先排最高位再用同样方式反复全局排序?
需要一点提示
最后一次排序会成为主键。
查看解析与答案
不能照搬。MSD 需要在相同高位的桶内递归处理低位,而不是每轮重新全局分组。
基数从 10 改为 256 的取舍?
需要一点提示
轮数与桶数同时变化。
查看解析与答案
轮数减少,桶初始化与内存成本增大;适合字节表示时还便于位运算,效果需按数据规模判断。