编辑代码

#include <iostream>

using namespace std;

// 在数组 arr 中找出最大值并返回
int findMax(int arr[], int len) {
    int max = arr[0];
    for (int i = 0; i < len; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// 计算整数 max 的位数并返回
int calBitCount(int max) {
    int count = 0;
    while (max > 0) {
        max /= 10;
        count++;
    }
    return count;
}

// 返回整数 value 的第 bit 位的值
int getBitValue(int value, int bit) {
    for (int i = 0; i < bit; ++i) {
        value /= 10;
    }
    return value % 10;
}

// 使用基数排序对数组 arr 进行排序
void radixSort(int arr[], int len) {
    // 1. 找出最大值，计算出需要排序的位 
    int max = findMax(arr, len);
    int bitCount = calBitCount(max);

    // 2. 创建排序数组
    int radixCount = 10;
    int* count = new int[radixCount]();
    int* tempArray = new int[len]();

    // 3. 对每一位进行排序 
    for (int b = 0; b < bitCount; ++b) {
        // 3.1 清空排序数组
        for (int i = 0; i < radixCount; i++) {
            count[i] = 0;
        }

        // 3.2 统计计数数组下标对应元素个数
        for (int i = 0; i < len; ++i) {
            int bitValue = getBitValue(arr[i], b);
            count[bitValue]++;
        } 

        // 3.3 累计算出小于等于计数数组下标对应元素的个数 
        for (int c = 1; c < radixCount; ++c) {
            count[c] += count[c - 1];
        }

        // 3.4 利用累加值和临时数组对对应的位进行排序
        for (int i = len - 1; i >= 0; --i) {
            int bitValue = getBitValue(arr[i], b);
            tempArray[--count[bitValue]] = arr[i];
        } 

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

    delete[] tempArray;
    delete[] count;
}

// 打印数组 arr 中的内容
void printArray(int arr[], int len) {
    for (int i = 0; i < len; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {20, 23, 96, 52, 34, 17, 55, 64, 31};
    int len = sizeof(arr) / sizeof(int);
    
    printArray(arr, len);
    radixSort(arr, len);
    printArray(arr, len);
    
    int arr1[] = {231, 150, 234, 987, 211, 985, 996, 300};
    int len1 = sizeof(arr1) / sizeof(int);
    
    printArray(arr1, len1);
    radixSort(arr1, len1);
    printArray(arr1, len1);
}