2009-10-27

基数排序算法深度解析：多关键字排序的高效实现

基数排序是一种非比较排序算法，它通过将数据按照数字的每一位进行排序来实现整体排序。基数排序可以看作是多关键字排序的一种实现方式。

1. 算法原理

1.1 基本思想

基数排序的核心思想：

按位处理：将每个数字按位分解
稳定排序：对每一位使用稳定的排序算法
从低位到高位：LSD方法，从个位开始
从高位到低位：MSD方法，从最高位开始

1.2 LSD基数排序步骤

输入数组: [170, 45, 75, 90, 2, 802, 24, 66]

按个位排序: [170, 90, 2, 802, 24, 45, 75, 66]
按十位排序: [2, 802, 24, 45, 66, 170, 75, 90]
按百位排序: [2, 24, 45, 66, 75, 90, 170, 802]

最终结果: [2, 24, 45, 66, 75, 90, 170, 802]

2. C语言实现

2.1 LSD基数排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>

// 获取数字的指定位数值
int get_digit(int num, int pos) {
    return (num / (int)pow(10, pos)) % 10;
}

// 获取数组中最大值的位数
int get_max_digits(int arr[], int n) {
    int max_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }
    
    int digits = 0;
    while (max_val > 0) {
        digits++;
        max_val /= 10;
    }
    return digits == 0 ? 1 : digits;
}

// 计数排序（用于基数排序的每一位）
void counting_sort_for_radix(int arr[], int n, int pos) {
    int output[n];
    int count[10] = {0};
    
    printf("  按第%d位排序:\n", pos);
    printf("  排序前: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    // 统计每个数字的出现次数
    for (int i = 0; i < n; i++) {
        count[get_digit(arr[i], pos)]++;
    }
    
    printf("  位数统计: ");
    for (int i = 0; i < 10; i++) {
        if (count[i] > 0) {
            printf("%d:%d ", i, count[i]);
        }
    }
    printf("\n");
    
    // 计算累积计数
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    
    // 构建输出数组（从右到左保证稳定性）
    for (int i = n - 1; i >= 0; i--) {
        int digit = get_digit(arr[i], pos);
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    
    // 复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
    
    printf("  排序后: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}

// LSD基数排序主函数
void lsd_radix_sort(int arr[], int n) {
    printf("开始LSD基数排序...\n");
    
    int max_digits = get_max_digits(arr, n);
    printf("最大位数: %d\n\n", max_digits);
    
    // 对每一位进行计数排序
    for (int pos = 0; pos < max_digits; pos++) {
        counting_sort_for_radix(arr, n, pos);
    }
}

// 测试LSD基数排序
void test_lsd_radix_sort() {
    printf("=== LSD基数排序测试 ===\n");
    
    int arr[] = {170, 45, 75, 90, 2, 802, 24, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
    
    lsd_radix_sort(arr, n);
    
    printf("最终结果: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}

2.2 MSD基数排序

// MSD基数排序实现
void msd_radix_sort_helper(int arr[], int left, int right, int pos) {
    if (left >= right || pos < 0) return;
    
    printf("MSD处理范围[%d,%d]，位置%d\n", left, right, pos);
    
    // 为每个数字创建桶
    int buckets[10][right - left + 1];
    int bucket_sizes[10] = {0};
    
    // 分配到桶中
    for (int i = left; i <= right; i++) {
        int digit = get_digit(arr[i], pos);
        buckets[digit][bucket_sizes[digit]++] = arr[i];
    }
    
    // 从桶中重新收集
    int index = left;
    for (int digit = 0; digit < 10; digit++) {
        if (bucket_sizes[digit] > 0) {
            printf("  数字%d的桶: ", digit);
            for (int i = 0; i < bucket_sizes[digit]; i++) {
                arr[index++] = buckets[digit][i];
                printf("%d ", buckets[digit][i]);
            }
            printf("\n");
        }
    }
    
    // 递归处理每个桶
    index = left;
    for (int digit = 0; digit < 10; digit++) {
        if (bucket_sizes[digit] > 1) {
            msd_radix_sort_helper(arr, index, index + bucket_sizes[digit] - 1, pos - 1);
        }
        index += bucket_sizes[digit];
    }
}

void msd_radix_sort(int arr[], int n) {
    printf("开始MSD基数排序...\n");
    
    int max_digits = get_max_digits(arr, n);
    printf("最大位数: %d\n\n", max_digits);
    
    msd_radix_sort_helper(arr, 0, n - 1, max_digits - 1);
}

// 测试MSD基数排序
void test_msd_radix_sort() {
    printf("=== MSD基数排序测试 ===\n");
    
    int arr[] = {170, 45, 75, 90, 2, 802, 24, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
    
    msd_radix_sort(arr, n);
    
    printf("\n最终结果: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}

2.3 优化版本

// 优化的基数排序：处理负数
void radix_sort_with_negatives(int arr[], int n) {
    if (n <= 1) return;
    
    // 分离正数和负数
    int* positive = (int*)malloc(n * sizeof(int));
    int* negative = (int*)malloc(n * sizeof(int));
    int pos_count = 0, neg_count = 0;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] >= 0) {
            positive[pos_count++] = arr[i];
        } else {
            negative[neg_count++] = -arr[i];  // 转为正数
        }
    }
    
    printf("处理负数的基数排序:\n");
    printf("正数个数: %d, 负数个数: %d\n", pos_count, neg_count);
    
    // 对正数进行基数排序
    if (pos_count > 0) {
        lsd_radix_sort(positive, pos_count);
    }
    
    // 对负数的绝对值进行基数排序，然后逆序
    if (neg_count > 0) {
        lsd_radix_sort(negative, neg_count);
        // 逆序并恢复负号
        for (int i = 0; i < neg_count / 2; i++) {
            int temp = negative[i];
            negative[i] = negative[neg_count - 1 - i];
            negative[neg_count - 1 - i] = temp;
        }
    }
    
    // 合并结果：负数 + 正数
    int index = 0;
    for (int i = 0; i < neg_count; i++) {
        arr[index++] = -negative[i];
    }
    for (int i = 0; i < pos_count; i++) {
        arr[index++] = positive[i];
    }
    
    free(positive);
    free(negative);
}

// 字符串基数排序
void string_radix_sort(char* arr[], int n, int max_len) {
    printf("字符串基数排序:\n");
    
    // 从最后一位开始排序
    for (int pos = max_len - 1; pos >= 0; pos--) {
        // 使用计数排序对当前位置的字符排序
        char* output[n];
        int count[256] = {0};  // ASCII字符范围
        
        // 统计字符频次
        for (int i = 0; i < n; i++) {
            int ch = (pos < strlen(arr[i])) ? arr[i][pos] : 0;
            count[ch]++;
        }
        
        // 计算累积计数
        for (int i = 1; i < 256; i++) {
            count[i] += count[i - 1];
        }
        
        // 构建输出数组
        for (int i = n - 1; i >= 0; i--) {
            int ch = (pos < strlen(arr[i])) ? arr[i][pos] : 0;
            output[count[ch] - 1] = arr[i];
            count[ch]--;
        }
        
        // 复制回原数组
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
        
        printf("按第%d位排序: ", pos);
        for (int i = 0; i < n; i++) {
            printf("%s ", arr[i]);
        }
        printf("\n");
    }
}

// 测试优化版本
void test_optimized_radix_sort() {
    printf("=== 优化版本测试 ===\n");
    
    // 测试包含负数的情况
    int arr1[] = {-170, 45, -75, 90, -2, 802, 24, -66};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    
    printf("包含负数的数组:\n");
    printf("排序前: ");
    for (int i = 0; i < n1; i++) printf("%d ", arr1[i]);
    printf("\n");
    
    radix_sort_with_negatives(arr1, n1);
    
    printf("排序后: ");
    for (int i = 0; i < n1; i++) printf("%d ", arr1[i]);
    printf("\n\n");
    
    // 测试字符串排序
    char* strings[] = {"banana", "apple", "cherry", "date", "elderberry"};
    int n2 = sizeof(strings) / sizeof(strings[0]);
    int max_len = 10;  // 假设最大长度
    
    printf("字符串数组:\n");
    printf("排序前: ");
    for (int i = 0; i < n2; i++) printf("%s ", strings[i]);
    printf("\n");
    
    string_radix_sort(strings, n2, max_len);
    
    printf("排序后: ");
    for (int i = 0; i < n2; i++) printf("%s ", strings[i]);
    printf("\n\n");
}

3. 算法分析

3.1 时间复杂度分析

typedef struct {
    int comparisons;
    int movements;
    double time_taken;
    int max_digits;
} RadixSortStats;

RadixSortStats stats;

void analyze_time_complexity() {
    printf("=== 时间复杂度分析 ===\n");
    
    printf("基数排序的时间复杂度:\n");
    printf("- 对每一位排序: O(n + k)\n");
    printf("- 总共d位: d次排序\n");
    printf("- 总时间复杂度: O(d × (n + k))\n");
    printf("- 其中d是最大位数，k是基数(通常为10)\n\n");
    
    printf("空间复杂度: O(n + k)\n\n");
    
    // 测试不同数据规模
    int sizes[] = {100, 1000, 5000};
    printf("性能测试:\n");
    printf("%-10s %-10s %-15s %-15s\n", "数据量", "最大位数", "时间(秒)", "理论复杂度");
    printf("--------------------------------------------------\n");
    
    for (int s = 0; s < 3; s++) {
        int n = sizes[s];
        int* arr = (int*)malloc(n * sizeof(int));
        
        // 生成随机数据
        srand(42);
        int max_val = 10000;  // 4位数
        for (int i = 0; i < n; i++) {
            arr[i] = rand() % max_val;
        }
        
        int max_digits = get_max_digits(arr, n);
        
        clock_t start = clock();
        lsd_radix_sort(arr, n);
        clock_t end = clock();
        
        double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
        double theoretical = max_digits * (n + 10);  // d * (n + k)
        
        printf("%-10d %-10d %-15.6f %-15.0f\n", 
               n, max_digits, time_taken, theoretical);
        
        free(arr);
    }
    printf("\n");
}

3.2 LSD vs MSD比较

void compare_lsd_msd() {
    printf("=== LSD vs MSD 比较 ===\n");
    
    printf("LSD (Least Significant Digit):\n");
    printf("- 从低位到高位排序\n");
    printf("- 适合固定长度的数据\n");
    printf("- 实现相对简单\n");
    printf("- 必须处理完所有位\n\n");
    
    printf("MSD (Most Significant Digit):\n");
    printf("- 从高位到低位排序\n");
    printf("- 适合变长数据\n");
    printf("- 可以提前终止\n");
    printf("- 递归实现较复杂\n\n");
    
    printf("性能对比:\n");
    printf("%-15s %-15s %-15s\n", "特征", "LSD", "MSD");
    printf("----------------------------------------------\n");
    printf("%-15s %-15s %-15s\n", "实现复杂度", "简单", "复杂");
    printf("%-15s %-15s %-15s\n", "内存使用", "较少", "较多");
    printf("%-15s %-15s %-15s\n", "适用数据", "固定长度", "变长数据");
    printf("%-15s %-15s %-15s\n", "提前终止", "不支持", "支持");
    printf("%-15s %-15s %-15s\n", "缓存性能", "较好", "一般");
    printf("\n");
}

4. 优缺点与应用

4.1 优点

void radix_sort_advantages() {
    printf("=== 基数排序的优点 ===\n");
    
    printf("1. 线性时间复杂度\n");
    printf("   - O(d × (n + k))通常优于O(n log n)\n");
    printf("   - 适合大数据量排序\n\n");
    
    printf("2. 稳定排序\n");
    printf("   - 保持相等元素的相对位置\n");
    printf("   - 适合多关键字排序\n\n");
    
    printf("3. 非比较排序\n");
    printf("   - 不依赖元素比较\n");
    printf("   - 突破比较排序的理论下界\n\n");
    
    printf("4. 适合并行化\n");
    printf("   - 每位的排序可以并行\n");
    printf("   - 桶操作相互独立\n\n");
}

4.2 缺点

void radix_sort_disadvantages() {
    printf("=== 基数排序的缺点 ===\n");
    
    printf("1. 数据类型限制\n");
    printf("   - 仅适用于整数或可转换为整数的数据\n");
    printf("   - 不能直接处理浮点数和复杂对象\n\n");
    
    printf("2. 基数依赖\n");
    printf("   - 性能依赖于基数的选择\n");
    printf("   - 位数多时效率下降\n\n");
    
    printf("3. 空间开销\n");
    printf("   - 需要额外的O(n + k)空间\n");
    printf("   - MSD版本递归深度可能很大\n\n");
    
    printf("4. 常数因子\n");
    printf("   - 虽然是线性但常数因子较大\n");
    printf("   - 小数据集可能不如快排\n\n");
}

4.3 应用场景

void radix_sort_applications() {
    printf("=== 应用场景 ===\n");
    
    printf("1. 大整数排序\n");
    printf("   - ID号码排序\n");
    printf("   - 序列号排序\n\n");
    
    printf("2. 字符串排序\n");
    printf("   - 固定长度字符串\n");
    printf("   - 词典排序\n\n");
    
    printf("3. 多关键字排序\n");
    printf("   - 日期排序(年-月-日)\n");
    printf("   - 坐标排序\n\n");
    
    printf("4. 外部排序\n");
    printf("   - 大文件排序\n");
    printf("   - 分布式排序\n\n");
    
    printf("5. 数据库应用\n");
    printf("   - 索引构建\n");
    printf("   - 查询优化\n\n");
}

5. 主函数

int main() {
    printf("========================================\n");
    printf("       基数排序算法完整演示\n");
    printf("========================================\n\n");
    
    test_lsd_radix_sort();
    test_msd_radix_sort();
    test_optimized_radix_sort();
    analyze_time_complexity();
    compare_lsd_msd();
    radix_sort_advantages();
    radix_sort_disadvantages();
    radix_sort_applications();
    
    printf("========================================\n");
    printf("            测试完成\n");
    printf("========================================\n");
    
    return 0;
}

6. 总结

基数排序是一种重要的非比较排序算法：

核心特点

线性时间: O(d × (n + k))复杂度
稳定排序: 保持相等元素顺序
非比较: 基于分配和收集
多样化: LSD和MSD两种实现

技术价值

基数排序体现了”分而治之”的思想在排序中的应用，通过按位处理将复杂问题简化。理解基数排序有助于：

掌握非比较排序的核心思想
理解多关键字排序的实现
学习桶排序等相关算法

实际意义

在大数据时代，基数排序在处理大量整数数据时展现出独特优势，特别是在数据库、搜索引擎等需要高效排序的系统中有重要应用价值。

编外计划 - 日志

To be or not to be,--that is question.