基数排序(多关键字排序)

是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。可以将每个关键字 K 看成由四个单关键字组成，即 K= k 1,k 2,k 3,k 4 每个关键字的取值范围为 0≤k i≤9，所以每个关键字可取值的数目为 10。通常将关键字取值的数目称为基数，用 r 表示，下例中 r =10。

链式基数排序（Radix Sort）是一种基于数位的排序算法。(这里使用LSD法进行排序)具体实现方法如下：

1. 取得链表中的最大数，并取得位数
2. 从最低位开始，依次对每个数位进行排序，将排序结果存储到桶(辅助空间)中
3. 将桶(辅助空间)中的结果存回原链表中
4. 重复步骤2-3，直到最高位排序完毕

以下是实现20个四位数的链式基数排序的代码：

#include <stdio.h>
#include <stdlib.h>
// 定义链表结点
typedef struct Node
{
    int data;
    struct Node* next;
} Node;
// 定义队列结构
typedef struct Queue
{
    Node* front;  // 队列前端
    Node* rear;   // 队列后端
} Queue;

Queue queue[10];  // 10 个队列，用于分配和收集数据
int divisior = 1;  // 用于按位取数的除数，初始为1

// 初始化队列
void initQueue(Queue* que)
{
    Node* p = malloc(sizeof(Node));
    if (p != NULL) {
        p->data = 0;  // 初始化结点数据为0
        p->next = NULL;
        (*que).front = p;
        (*que).rear = p;
    }
    else {
        printf("node apply error!\n");
    }
}

// 入队操作
void push(Queue* que, int e)
{
    Node* p = malloc(sizeof(Node));
    if (p != NULL) {
        p->data = e;
        p->next = NULL;
        (*que).rear->next = p;  // 将新结点插入队尾
        (*que).rear = p;
    }
    else {
        printf("node apply error!\n");
    }
}

// 清空队列
void clear(Queue* que)
{
    (*que).front->next = NULL;
    (*que).rear = (*que).front;
}

// 获取最大数的位数
int maxBit(Queue* que)
{
    Node* p = (*que).front->next;
    int maxData = p->data;
    while (p != NULL) {
        if (maxData < p->data) {
            maxData = p->data;
        }
        p = p->next;
    }
    int b = 0;
    while (maxData > 0) {
        maxData /= 10;
        b++;
    }
    return b;
}

// 根据当前位数获取关键字
int getKey(Node* q)
{
    int k = 0;
    k = ((*q).data / divisior) % 10;
    return k;
}

// 分配数据到各个队列中
void distributeRadix(Queue* que)
{
    for (int i = 0; i < 10; i++) {
        initQueue(&queue[i]);  // 初始化10个队列
    }
    Node* p = (*que).front->next;
    while (p != NULL) {
        int k = getKey(p); 
        queue[k].rear->next = p;  // 将当前结点放入对应队列中
        queue[k].rear = p;  // 更新队列尾结点
        p = p->next;
        queue[k].rear->next = NULL;
    }
    clear(que);  // 清空原队列
}

// 将数据收集到原队列中
void collectRadix(Queue* que)
{
    int index = 0;
    for (index = 0; index < 10; index++) {
        if (&queue[index].front->next->data != NULL) {  // 找到第一个非空队列
            break;
        }
    }
    Node* p = queue[index].front->next;
    while (p != NULL) {
        (*que).rear->next = p;  // 将队列中的数据接入原队列
        (*que).rear = p; 
        p = p->next;
        (*que).rear->next = NULL;
    }
    for (index++; index < 10; index++) {
        Node* q = queue[index].front->next; 
        while (q != NULL) {
            (*que).rear->next = q; 
            (*que).rear = q;
            q = q->next;
            (*que).rear->next = NULL;
        }
    }
    for (int i = 0; i < 10; i++) {
        clear(&queue[i]);  // 清空各个队列
    }
    divisior *= 10;  // 更新除数
}

// 基数排序
void radix(Queue* que)
{
    int b = maxBit(que);  // 获取最大位数
    for (int i = 0; i < b; i++) {
        distributeRadix(que);  // 按当前位数分配到各个队列
        collectRadix(que);  // 将数据收集到原队列
    }
}

// 打印队列
void print(Queue* que)
{
    Node* p = (*que).front->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main()
{
    Queue que;
    initQueue(&que);
    int arr[] = { 1234, 5678, 9101, 2345, 6789, 1011, 1213, 1415, 1617, 1819,
        2021, 2223, 2425, 2627, 2829,3032, 3233, 3435, 3637, 3839 };
    int len = sizeof(arr) / sizeof(int);
    for (int i = 0; i < len; i++) {
        push(&que, arr[i]);  // 将数据入队
    }
    printf("排序前序列：\n");
    print(&que);
    radix(&que);  // 进行基数排序
    printf("排序后序列：\n");
    print(&que);  // 打印排序后的队列
    return 0;
}

时间复杂度：

待排序列为n个记录，d个关键字，关键字的取值范围为 r，其中，一趟分配时间复杂度为 O(n)，一趟收集时间复杂度为O(rd)，共进行 d 趟分配和收集，所以链式基数排序的时间复杂度为 O( d·(n+rd) ) 。

空间复杂度：

O(rd + n )，因为一个桶本质是一个链式队列，一共 r 个桶，每个队列有队头和队尾两个指针，就是2 rd 个队列指针。又原来的待排序列是一个单链表，那么需要 n 个next指针。

执行结果：