编辑代码

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

// 获取元素在指定位数上的数字
int get_digit(int num, int digit) {
    int i;
    for (i = 0; i < digit - 1; i++) {
        num /= 10;
    }
    return num % 10;
}

// 基数排序
void radix_sort(int arr[], int n, int max_digit) {
    int i, j, k;
    int *count, *temp;
    // 每个桶的计数器
    count = (int *)malloc(sizeof(int) * 10); 
     // 临时数组
    temp = (int *)malloc(sizeof(int) * n); 

    for (i = 1; i <= max_digit; i++) {
        // 初始化每个桶的计数器
        for (j = 0; j < 10; j++) {
            count[j] = 0;
        }
        // 统计每个桶中的元素个数
        for (j = 0; j < n; j++) {
            k = get_digit(arr[j], i);
            count[k]++;
        }
        // 计算每个桶的右边界索引
        for (j = 1; j < 10; j++) {
            count[j] += count[j - 1];
        }
        // 将元素放入对应的桶中
        for (j = n - 1; j >= 0; j--) {
            k = get_digit(arr[j], i);
            temp[count[k] - 1] = arr[j];
            count[k]--;
        }
        // 将桶中的元素复制回原数组
        for (j = 0; j < n; j++) {
            arr[j] = temp[j];
        }
    }

    free(count);
    free(temp);
}

int main() {
    int arr[] = {47, 4, 19, 370, 53, 15, 198, 72, 1,72,19,66};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_digit = 3; // 数组中最大值的位数

    radix_sort(arr, n, max_digit);

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

    return 0;
}