基数排序算法：按位排序的线性算法

算法原理

基数排序（Radix Sort）是一种非比较排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机上的贡献。

基本思想

1. 确定位数：找出最大数，确定最大位数
2. 从低位开始：从最低位开始排序
3. 逐位排序：使用稳定排序算法对每一位排序
4. 完成排序：所有位排序完成后，数组有序

C语言实现

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

// 获取数字的第d位（从右开始，d=0是个位）
int get_digit(int num, int d) {
    for (int i = 0; i < d; i++) {
        num /= 10;
    }
    return num % 10;
}

// 计数排序（用于基数排序的子程序）
void counting_sort_for_radix(int arr[], int n, int digit_pos) {
    int output[n];
    int count[10] = {0}; // 0-9的计数
    
    // 统计当前位数字的出现次数
    for (int i = 0; i < n; i++) {
        count[get_digit(arr[i], digit_pos)]++;
    }
    
    // 计算累积计数
    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], digit_pos);
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    
    // 复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 基数排序主函数
void radix_sort(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];
        }
    }
    
    // 对每一位进行计数排序
    for (int digit_pos = 0; max_val / pow(10, digit_pos) > 0; digit_pos++) {
        counting_sort_for_radix(arr, n, digit_pos);
    }
}

int main() {
    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");
    
    radix_sort(arr, n);
    
    printf("排序后: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

复杂度分析

• 时间复杂度：O(d×(n+k))，d为位数，k为基数
• 空间复杂度：O(n+k)
• 稳定性：稳定

版权所有，如有侵权请联系我