基数排序

基数排序（Radix Sort）是一种非比较的排序算法，是分配排序的一种。它不通过比较关键字来排序，而是通过分配和收集的方式，按位对关键字进行排序。

核心思想

• 将关键字拆分为若干个位（个位、十位、百位……）
• 按照从低位到高位（或从高位到低位）的顺序，依次对每一位进行排序
• 每一位的排序使用稳定的排序算法（如计数排序）
• 最终得到有序序列

基数的定义

• 假设关键字由 $d$ 元组 $(k^{(d-1)}, k^{(d-2)}, \ldots, k^{1}, k^{0})$ 组成
• 其中 $0 \leq k^{i} \leq r-1$
• $r$ 称为基数（如十进制的基数为 10）

两种方法

• 最低位优先（LSD）：从个位开始，逐位向高位排序（常用）
• 最高位优先（MSD）：从最高位开始，逐位向低位排序

关键特性

• 基数排序不是基于比较的排序算法
• 元素的移动次数与关键字的初始排列次序无关
• 基数排序是稳定的
• 通常使用链式存储（而不是顺序存储）
• 只能对整数进行排序

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

1. 初始化：设置 $r$ 个空辅助队列 $Q_0, Q_1, \ldots, Q_{r-1}$
2. 分配：按照关键字位权重递增的次序（个、十、百……），对 $d$ 个关键字位分别做分配和收集
   • 顺序扫描各个元素
   • 若当前处理的关键字位为 $x$，就将元素插入 $Q_x$ 队尾
3. 收集：把 $Q_0, Q_1, \ldots, Q_{r-1}$ 各个队列的结点依次出队并链接在一起
4. 重复步骤 2-3，共处理 $d$ 趟
5. 最终得到有序序列

MSD（最高位优先）基数排序

1. 按照最高位进行分配和收集
2. 对每个队列中的元素，按照次高位递归进行分配和收集
3. 重复直到最低位

// 基数排序（LSD，链式实现）
#define MAX_DIGIT 10  // 最大位数
#define RADIX 10      // 基数（十进制）

// 链表结点
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 获取整数 x 的第 d 位数字（从个位开始，d=0 表示个位）
int GetDigit(int x, int d) {
    for (int i = 0; i < d; i++)
        x /= 10;
    return x % 10;
}

// 基数排序
void RadixSort(int A[], int n) {
    // 创建 r 个队列（用链表实现）
    Node *bucket[RADIX];  // 桶数组
    Node *tail[RADIX];    // 每个桶的尾指针

    // 计算最大位数 d
    int maxVal = A[0];
    for (int i = 1; i < n; i++)
        if (A[i] > maxVal) maxVal = A[i];
    int d = 0;
    while (maxVal > 0) { d++; maxVal /= 10; }

    // 创建链表
    Node *head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    Node *p = head;
    for (int i = 0; i < n; i++) {
        p->next = (Node *)malloc(sizeof(Node));
        p = p->next;
        p->data = A[i];
        p->next = NULL;
    }

    // LSD 基数排序
    for (int i = 0; i < d; i++) {
        // 初始化桶
        for (int j = 0; j < RADIX; j++) {
            bucket[j] = (Node *)malloc(sizeof(Node));
            bucket[j]->next = NULL;
            tail[j] = bucket[j];
        }
        // 分配
        p = head->next;
        while (p != NULL) {
            int digit = GetDigit(p->data, i);
            tail[digit]->next = p;
            tail[digit] = p;
            p = p->next;
        }
        tail[digit]->next = NULL;  // 最后一个桶的尾部置空

        // 收集
        head->next = NULL;
        p = head;
        for (int j = 0; j < RADIX; j++) {
            if (bucket[j]->next != NULL) {
                p->next = bucket[j]->next;
                p = tail[j];
            }
            free(bucket[j]);
        }
        p->next = NULL;
    }

    // 将排序结果写回数组
    p = head->next;
    for (int i = 0; i < n; i++) {
        A[i] = p->data;
        Node *temp = p;
        p = p->next;
        free(temp);
    }
    free(head);
}

对序列 {329, 457, 657, 839, 436, 720, 355} 进行 LSD 基数排序。

初始：329, 457, 657, 839, 436, 720, 355

第一趟（按个位分配和收集）

Q_0: 720
Q_1:
Q_2:
Q_3:
Q_4:
Q_5: 355
Q_6: 436
Q_7: 457, 657
Q_8:
Q_9: 329, 839

收集：720, 355, 436, 457, 657, 329, 839

第二趟（按十位分配和收集）

Q_0:
Q_1:
Q_2: 720, 329
Q_3: 436, 839
Q_4:
Q_5: 355, 457, 657
Q_6:
Q_7:
Q_8:
Q_9:

收集：720, 329, 436, 839, 355, 457, 657

第三趟（按百位分配和收集）

Q_0:
Q_1:
Q_2:
Q_3: 329, 355
Q_4: 436, 457
Q_5:
Q_6: 657
Q_7: 720
Q_8: 839
Q_9:

收集：329, 355, 436, 457, 657, 720, 839

最终结果：329, 355, 436, 457, 657, 720, 839

空间复杂度为 $O(n+r)$。

• 需要 $r$ 个辅助队列（桶）
• 如果使用链式存储，还需要 $n$ 个结点空间
• 总空间复杂度 $= O(r) + O(n) = O(n + r)$