基数排序

1. 基数排序的基本思想

基数排序是一种非比较型的排序算法，它根据数据的各个位上的数字来进行排序。核心思想是：

• 按位排序：从最低位到最高位（LSD，Least Significant Digit），或从最高位到最低位（MSD），依次对每一位进行排序
• 稳定性：每一轮的排序必须是稳定的，即相同数字的元素在排序后保持原有相对顺序
• 桶的使用：使用0-9这10个桶来临时存放数据

2. 数据结构视角分析

2.1 主要数据结构组件

// 基数排序涉及的主要数据结构
#define RADIX 10  // 基数，十进制为10

// 1. 桶结构（队列实现）
typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* front;  // 队首
    Node* rear;   // 队尾
    int size;     // 当前元素个数
} Queue;

// 2. 排序过程中的临时存储结构
Queue buckets[RADIX];  // 0-9号桶

2.2 数据结构关系图

输入数组 → 按位分配到桶中 → 从桶中收集 → 重复直到最高位 → 有序数组
         ↓
        [0] [1] [2] ... [9]  (10个队列结构的桶)

3. C语言完整实现

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define RADIX 10  // 十进制基数

// 队列节点
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 队列结构（用作桶）
typedef struct {
    Node* front;
    Node* rear;
    int size;
} Queue;

// 队列操作函数
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    q->size = 0;
    return q;
}

int isEmpty(Queue* q) {
    return q->front == NULL;
}

void enqueue(Queue* q, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    
    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    q->size++;
}

int dequeue(Queue* q) {
    if (isEmpty(q)) return -1;
    
    Node* temp = q->front;
    int data = temp->data;
    q->front = q->front->next;
    
    if (q->front == NULL) {
        q->rear = NULL;
    }
    
    free(temp);
    q->size--;
    return data;
}

void freeQueue(Queue* q) {
    while (!isEmpty(q)) {
        dequeue(q);
    }
    free(q);
}

// 获取数字的某一位（从最低位开始，第0位是个位）
int getDigit(int number, int digitPosition) {
    int divisor = 1;
    for (int i = 0; i < digitPosition; i++) {
        divisor *= RADIX;
    }
    return (number / divisor) % RADIX;
}

// 获取数组中最大数字的位数
int getMaxDigits(int arr[], int n) {
    int max = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    int digits = 0;
    while (max > 0) {
        digits++;
        max /= RADIX;
    }
    return digits;
}

// 基数排序主函数
void radixSort(int arr[], int n) {
    if (n <= 1) return;
    
    // 创建10个桶（队列）
    Queue* buckets[RADIX];
    for (int i = 0; i < RADIX; i++) {
        buckets[i] = createQueue();
    }
    
    int maxDigits = getMaxDigits(arr, n);
    
    // 从最低位到最高位依次排序
    for (int digitPos = 0; digitPos < maxDigits; digitPos++) {
        // 分配到桶中
        for (int i = 0; i < n; i++) {
            int digit = getDigit(arr[i], digitPos);
            enqueue(buckets[digit], arr[i]);
        }
        
        // 从桶中收集（保持稳定性）
        int index = 0;
        for (int i = 0; i < RADIX; i++) {
            while (!isEmpty(buckets[i])) {
                arr[index++] = dequeue(buckets[i]);
            }
        }
    }
    
    // 释放桶内存
    for (int i = 0; i < RADIX; i++) {
        freeQueue(buckets[i]);
    }
}

// 测试函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {170, 45, 75, 90, 2, 802, 24, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前: ");
    printArray(arr, n);
    
    radixSort(arr, n);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

4. 执行过程示例

以数组 [170, 45, 75, 90, 2, 802, 24, 66]为例：第1轮（个位排序）：

• 按个位数字分配到桶：0→[170,90], 2→[2,802], 4→[24], 5→[45,75], 6→[66]
• 收集：170, 90, 2, 802, 24, 45, 75, 66

第2轮（十位排序）：

• 按十位数字分配到桶
• 收集后数组部分有序

第3轮（百位排序）：

• 按百位数字分配到桶
• 最终得到完全有序数组

5. 复杂度分析

时间复杂度：O(d × (n + k))

• d：最大数字的位数
• n：数组元素个数
• k：基数（这里k=10）

空间复杂度：O(n + k)

• 需要k个桶，每个桶最多可能存储n个元素

6. 数据结构选择的意义

1. 队列结构：保证先进先出，维持稳定性
2. 桶数组：提供O(1)时间的元素分配
3. 位操作：高效提取数字的各个位

7. 适用场景

• 整数排序：特别适合整数范围已知的情况
• 字符串排序：可以按字符位置排序
• 多关键字排序：如先按年份、再按月份排序

基数排序通过巧妙的数据结构设计，避免了元素间的直接比较，在特定场景下能达到线性时间复杂度。