编辑代码

#include <stdio.h>
#include <stdlib.h>
void printArray(int arr[], int len);
int findMax(int arr[], int len) {
    int max = arr[0];
    for (int i = 1; i < len; ++i)
        if (max < arr[i])
            max = arr[i];
    return max;
}


int calBitCount(int max) {
    int count = 0;
    for (; max /= 10; ++count);
    return count + 1;
}


int getBitValue(int value, int bit) {
    for (; bit > 0; --bit)
        value /= 10;
    return value % 10;
}

void radixSort(int arr[], int len) {

    int max = findMax(arr, len);
    int bitCount = calBitCount(max);


    int radixCount = 10;
    int *count = (int *)malloc(radixCount * sizeof(int));
    int *tempArray = (int *)malloc(len * sizeof(int));


    for (int b = 0; b < bitCount; ++b) {

        for (int i = 0; i < radixCount; ++i)
            count[i] = 0;
        for (int i = 0; i < len; ++i)
            tempArray[i] = 0;


        for (int i = 0; i < len; ++i)
            ++count[getBitValue(arr[i], b)];


        for (int c = 1; c < radixCount; ++c)
            count[c] += count[c - 1];


        for (int i = len - 1; i >= 0; --i)
            tempArray[--count[getBitValue(arr[i], b)]] = arr[i];

        // 3.5 临时数组数据拷贝回原数组
        for (int i = 0; i < len; ++i)
            arr[i] = tempArray[i];
    }

    free(count);
    free(tempArray);
}

void printArray(int arr[], int len) {
    for (int i = 0; i < len; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {67,68,20,11,66,89,5,2,33};
    int len = sizeof(arr) / sizeof(int);
    printArray(arr, len);
    radixSort(arr, len);
    printArray(arr, len);
    return 0;
}