DS-07-07 基数排序

408 > ### 数据结构 > #### 基数排序（Radix Sort）

一、定位信息

维度	内容
章节归属	第7章排序
知识单元编号	DS-07-07
前置知识	DS-07-01 排序基本概念（非比较类排序）
后续衔接	DS-07-09 排序算法综合对比
考试大纲要求	掌握基数排序的算法思想、实现及性能分析
预计学习时长	35分钟

二、知识点讲解

1. 基本思想

基数排序（Radix Sort）是一种非比较类排序算法。其核心思想是：

按关键字的各个位（个位、十位、百位…）依次进行排序，从最低位到最高位（LSD）或从最高位到最低位（MSD），每一趟使用稳定的排序算法（通常用计数排序或桶排序）。

关键性质：每一趟的排序必须是稳定的，这样才能保证高位排序后，相同高位的元素内部仍保持低位排序的顺序。

2. LSD 基数排序（最低位优先）

LSD（Least Significant Digit first）是考试中最常考的方式：

先按个位排序
再按十位排序
再按百位排序
……
最后按最高位排序

每一趟使用稳定的分配-收集过程。

3. 分配-收集过程

假设关键字为 d 位 r 进制数（r 为基数，即桶的个数）：

// 基数排序（LSD），对关键字为 d 位的 r 进制数排序
void RadixSort(ElementType A[], int n, int d, int r) {
    // A[0..n-1]：待排序数组
    // d：关键字位数（最大位数）
    // r：基数（桶的个数，十进制时 r=10）
    // 每一趟对第 k 位（k = 0, 1, ..., d-1）进行分配和收集

    // 创建 r 个桶（链表或队列）
    Queue bucket[r];
    for (int k = 0; k < d; k++) {  // 从最低位到最高位
        // 分配：将每个元素按第 k 位的值放入对应桶中
        for (int i = 0; i < n; i++) {
            int digit = GetDigit(A[i], k);  // 取第 k 位的值
            Enqueue(bucket[digit], A[i]);    // 放入对应桶
        }
        // 收集：按桶的顺序依次取出元素
        int idx = 0;
        for (int j = 0; j < r; j++) {
            while (!IsEmpty(bucket[j])) {
                A[idx++] = Dequeue(bucket[j]);
            }
        }
    }
}

4. 过程示例

对序列 (329, 457, 657, 839, 436, 720, 355) 进行 LSD 基数排序（r=10, d=3）：

第 1 趟（个位）：

桶 0: 720
桶 5: 355
桶 6: 436
桶 7: 457, 657
桶 9: 329, 839
收集后：[720, 355, 436, 457, 657, 329, 839]

第 2 趟（十位）：

桶 2: 329, 720
桶 3: 436, 839
桶 5: 355, 457, 657
收集后：[329, 720, 436, 839, 355, 457, 657]

第 3 趟（百位）：

桶 3: 329, 355
桶 4: 436, 457
桶 6: 657
桶 7: 720
桶 8: 839
收集后：[329, 355, 436, 457, 657, 720, 839]

排序完成！

5. 时间复杂度分析

方面	复杂度	说明
趟数	d	d 为关键字位数
每趟分配	O(n)	每个元素放入一个桶
每趟收集	O(n + r)	遍历所有桶取出元素
总时间	O(d(n + r))	d 趟 × 每趟 O(n + r)

当 d 为常数、r 为常数时，时间复杂度为 O(n)，可以突破比较排序的 Ω(n log n) 下界。

关键条件：

d（位数）和 r（基数）相对于 n 较小时，基数排序效率高
当 d ≈ log_r(n) 时，O(d(n+r)) ≈ O(n log n)，与比较排序相当

6. 空间复杂度

O(r + n) = O(n)（当 r 为常数时）

r 个桶，每个桶需要空间
辅助数组

7. 稳定性

稳定。每一趟的分配-收集过程使用的是稳定排序（如计数排序），保证了相同关键字的相对顺序不变。

关键：基数排序的稳定性不是算法本身的特性，而是要求每一趟必须使用稳定排序。如果某一趟使用不稳定排序，基数排序的结果将出错。

8. LSD vs MSD 对比表

对比维度	LSD（最低位优先）	MSD（最高位优先）
排序方向	个位 → 十位 → 百位 → …	百位 → 十位 → 个位 → …
是否需要递归	不需要	需要（对每个桶递归）
实现复杂度	简单	复杂
适用场景	定长关键字	不等长关键字
408 考查频率	高频	低频

三、记忆辅助

基数排序 = 按位分配收集：像扑克牌按花色分堆，再按点数分堆，每次分堆都保持之前的顺序
稳定性是前提：每一趟必须用稳定排序，否则高位排序会破坏低位的顺序
O(d(n+r))：d 是位数，r 是基数（桶数），n 是元素个数。当 d 和 r 为常数时就是 O(n)
突破下界的原因：基数排序不比较关键字，而是利用关键字的位信息直接分配，所以不受 Ω(n log n) 限制
LSD 记忆：L = Least = 最低位，先排低位后排高位，像数字排序的自然直觉

四、例题精解

例题 1：基数排序过程模拟

题目：对序列 (278, 109, 638, 984, 525, 369, 721) 进行 LSD 基数排序（r=10），写出每一趟的结果。

第一步：审题 n=7，关键字为 3 位十进制数，需要进行 3 趟分配-收集。

第二步：逐趟模拟

初始序列：[278, 109, 638, 984, 525, 369, 721]

第 1 趟（个位）：

桶 1: 721
桶 4: 984
桶 5: 525
桶 8: 278, 638
桶 9: 109, 369
收集后：[721, 984, 525, 278, 638, 109, 369]

第 2 趟（十位）：

桶 0: 109
桶 2: 721, 525
桶 3: 638
桶 6: 369
桶 7: 278
桶 8: 984
收集后：[109, 721, 525, 638, 369, 278, 984]

第 3 趟（百位）：

桶 1: 109
桶 2: 278
桶 3: 369
桶 5: 525
桶 6: 638
桶 7: 721
桶 9: 984
收集后：[109, 278, 369, 525, 638, 721, 984]

第三步：解答 排序结果：[109, 278, 369, 525, 638, 721, 984]

第四步：总结 基数排序共需 d=3 趟，每趟的分配和收集各需 O(n+r) 时间。注意每趟收集后序列的顺序变化。

例题 2：基数排序的时间复杂度分析

题目：对 n=1000 个 5 位十进制数进行基数排序，使用 r=10 的桶。计算总比较次数并与快速排序对比。

第一步：审题 n=1000, d=5, r=10，计算基数排序的时间代价并与快排对比。

第二步：分析

基数排序：

趟数：d = 5
每趟时间：O(n + r) = O(1000 + 10) = O(1010)
总时间：O(d × (n + r)) = O(5 × 1010) ≈ 5050 次操作

快速排序（平均）：

总时间：O(n log n) = O(1000 × 10) ≈ 10000 次操作

第三步：解答

基数排序：约 5050 次操作
快速排序：约 10000 次操作
基数排序在此场景下更快

但需注意：基数排序需要 O(n+r) = O(1010) 的额外空间，且仅适用于关键字位数有限的情况。

第四步：总结 当关键字位数 d 较小、基数 r 不大时，基数排序可以比 O(n log n) 的比较排序更快。但当 d ≈ log n 时，优势消失。

五、考情分析

年份	题型	考点	难度
中频	选择题	基数排序的时间复杂度	★★☆
中频	分析题	基数排序的过程模拟	★★★
低频	选择题	基数排序的稳定性条件	★★☆

命题趋势：

基数排序考查频率中等，但属于常考知识点
时间复杂度 O(d(n+r)) 的分析是选择题常考点
与比较排序下界结合考查是常见模式

六、易错点

每一趟必须稳定：基数排序的前提是每趟分配-收集使用稳定排序。如果某一趟不稳定，整个排序结果错误
LSD 方向：必须从最低位开始。如果从最高位开始（MSD），需要递归处理，逻辑完全不同
时间复杂度不是 O(n)：只有当 d 和 r 为常数时才是 O(n)。一般情况是 O(d(n+r))
基数排序不是比较排序：它不通过比较关键字大小来排序，所以不受 Ω(n log n) 下界约束
桶的个数 r 的选择：r 太大则空间开销大，r 太小则趟数 d 增加。需要权衡

七、来源标注

《数据结构（C语言版）》严蔚敏，第10.6节基数排序
《数据结构》王道考研，第7章 7.6节基数排序
408考试大纲：数据结构部分-基数排序
《算法导论》Thomas H. Cormen，第8.3节基数排序

DS-07-07 基数排序 ​

408 > ### 数据结构 > #### 基数排序（Radix Sort） ​

一、定位信息 ​

二、知识点讲解 ​

1. 基本思想 ​

2. LSD 基数排序（最低位优先） ​

3. 分配-收集过程 ​

4. 过程示例 ​

5. 时间复杂度分析 ​

6. 空间复杂度 ​

7. 稳定性 ​

8. LSD vs MSD 对比表 ​

三、记忆辅助 ​

四、例题精解 ​

例题 1：基数排序过程模拟 ​

例题 2：基数排序的时间复杂度分析 ​

五、考情分析 ​

六、易错点 ​

七、来源标注 ​