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

int get_digit(int num, int digit) {
    return (num / digit) % 10;
}

void radix_sort(int arr[], int n, int max_digit) {
    int *count = malloc(sizeof(int) * 10), *temp = malloc(sizeof(int) * n);
    for (int d = 1; d <= max_digit; d *= 10) {
        for (int i = 0; i < 10; i++) count[i] = 0;
        for (int i = 0; i < n; i++) count[get_digit(arr[i], d)]++;
        for (int i = 1; i < 10; i++) count[i] += count[i - 1];
        for (int i = n - 1; i >= 0; i--) temp[--count[get_digit(arr[i], d)]] = arr[i];
        for (int i = 0; i < n; i++) arr[i] = temp[i];
    }
    free(count);
    free(temp);
}

int main() {
    int arr[] = {34, 23, 69, 19, 777, 15, 198, 82, 33, 78, 190, 606};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_digit = 1000;

    radix_sort(arr, n, max_digit);

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

    return 0;
}