基数排序中 LSD 和 MSD 有什么区别？分别适合什么场景？

简化版

基数排序按位排序，常见方向有 LSD 和 MSD。

LSD 从最低位开始排，依赖每一轮稳定排序，适合固定长度整数。MSD 从最高位开始排，更像按字典树分桶，适合字符串、变长 key 和需要尽早按高位区分的场景。

二者都不是通用比较排序，通常要求 key 能拆成位或字符。

详细版

LSD，Least Significant Digit，从低位到高位。

MSD，Most Significant Digit，从高位到低位。

类型	排序方向	特点
LSD	低位到高位	实现相对简单，要求每轮稳定
MSD	高位到低位	可以提前分组，适合字符串

LSD 示例：

先按个位排
再按十位排
再按百位排

只要每一轮是稳定排序，高位排序时就能保留低位已经建立的顺序。

完整版教学

1. 基数排序的核心思想

基数排序不是直接比较两个完整 key。

它把 key 拆成若干位：

329 -> 3, 2, 9

然后按位分多轮排序。每一位的取值范围通常较小，比如十进制数字是 0..9，二进制字节是 0..255。

基数排序利用了 key 的结构，所以它不受比较排序 O(n log n) 下界限制。

2. LSD 是怎么排的

LSD 从最低位开始。

例如三位数排序：

第 1 轮：个位
第 2 轮：十位
第 3 轮：百位

每一轮通常用稳定的计数排序完成。

低位先排好后，高位再分组；稳定性保证高位相同的元素仍保持低位顺序。

3. 为什么 LSD 必须稳定

假设按个位排完后，再按十位排。

如果十位相同，个位顺序应该保留，否则低位信息就丢了。

例如：

21, 22

按十位看它们都属于 2，此时应该保持个位排出的 21 在 22 前。

所以 LSD 的每一轮必须是稳定排序。

4. MSD 是怎么排的

MSD 从最高位开始。

它先按最高位分桶，然后在每个桶内递归处理下一位。

按首字符分桶
再在每个桶里按第二字符分桶

这和 Trie 的思想很像，先用高位决定大方向。

5. MSD 为什么适合字符串

字符串比较天然从第一个字符开始。

如果首字符不同，后面字符根本不用看。

MSD 可以利用这一点：先按首字符分组，只有同组字符串才继续比较下一位。

数据	更自然的方向
固定长度整数	LSD 常见
字符串	MSD 常见
前缀差异明显的 key	MSD 有优势

6. 变长 key 怎么处理

变长字符串需要处理「字符串结束」。

可以把结束符看成比其他字符更小的特殊字符。

例如：

"app" < "apple"

因为 app 到第三个字符后结束，应该排在更长的同前缀字符串前面。

7. 复杂度怎么分析

如果有 n 个 key，每个 key 长度为 d，每位基数为 R，常见复杂度是：

O(d * (n + R))

空间通常需要桶或计数数组。

参数	含义
n	元素数量
d	位数或字符长度
R	每位取值范围

8. 常见误区与追问

• 误区：基数排序就是从个位开始。 LSD 从低位开始，MSD 从高位开始，两者都属于基数排序。
• 误区：LSD 每轮排序不需要稳定。 LSD 依赖稳定性保留低位顺序。
• 误区：基数排序适合所有对象。 它要求 key 能拆成有限位或字符。
• 追问：为什么 MSD 适合字符串？ 字符串比较从首字符开始，高位差异能尽早分组。
• 追问：基数排序复杂度为什么不是 O(n log n)？ 它不是比较排序，而是按位计数或分桶。