C语言利用基数排序实现降序

以下是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], bucketCount[10];
    int max = getMax(arr, n);
    int digit = 1;
    while (max / digit > 0) {
        for (int i = 0; i < 10; i++) {
            bucketCount[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            int digitNum = (arr[i] / digit) % 10;
            bucket[digitNum][bucketCount[digitNum]++] = arr[i];
        }
        int index = 0;
        for (int i = 9; i >= 0; i--) {
            for (int j = 0; j < bucketCount[i]; j++) {
                arr[index++] = bucket[i][j];
            }
        }
        digit *= 10;
    }
}

int main() {
    int arr[] = { 53, 3, 542, 748, 14, 214, 154, 63, 616 };
    int n = sizeof(arr) / sizeof(arr[0]);
    radixSort(arr, n);
    printf("降序排序结果：\n");
    for (int i = n - 1; i >= 0; i--) {
        printf("%d ", arr[i]);
    }
    return 0;
}

基数排序的时间复杂度为O(d(n+k))，其中d为位数，k为进制数，因此其时间复杂度与数组中的最大值和进制数都有关系。在实际应用中，基数排序通常用于对大量数据进行排序，比如对1亿个整数进行排序，时间复杂度为O(800000000)。