基数排序

基数排序（Radix Sort）是一种非比较性的排序算法，它根据元素的每个位上的数字来排序。基数排序常用于整数排序，可以将整数按照各个位数上的数字进行排序，时间复杂度为O(dn)，其中d为位数，n为元素数量。

下面是一个基数排序的C语言实现示例：

#include <stdio.h>

// 获取待排序数组中最大的数
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// 基数排序函数
void radixSort(int arr[], int n) {
    int bucket[10][n]; // 用于存放每个位数上的元素
    int bucketCount[10]; // 用于存放每个位数上的元素数量
    int max = getMax(arr, n);
    int digitCount = 0;

    // 计算最大数的位数
    while (max > 0) {
        digitCount++;
        max /= 10;
    }

    int mod = 10;
    int div = 1;

    // 从个位开始进行排序
    for (int i = 0; i < digitCount; i++, mod *= 10, div *= 10) {
        // 清空桶和桶计数器
        for (int j = 0; j < 10; j++) {
            bucketCount[j] = 0;
        }

        // 将元素放入对应的桶中
        for (int j = 0; j < n; j++) {
            int digit = (arr[j] % mod) / div;
            bucket[digit][bucketCount[digit]] = arr[j];
            bucketCount[digit]++;
        }

        // 将桶中的元素依次放回原数组中
        int k = 0;
        for (int j = 0; j < 10; j++) {
            for (int l = 0; l < bucketCount[j]; l++) {
                arr[k] = bucket[j][l];
                k++;
            }
        }
    }
}

// 测试基数排序
int main() {
    int arr[] = {54, 26, 93, 17, 77, 31, 44, 55, 20};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    radixSort(arr, n);

    printf("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}