编辑代码

#include <iostream>

using namespace std;

int findMax(int arr[], int len) {
    int max = arr[0];
    for (int i = 1; i < len; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// 输入50，返回2
// 输入100，返回3 
int calBitCount(int max) {
    int count = 0;
    while (max > 0) {
        max /= 10;
        count++;
    }
    return count;
}

// 输入（50，0），返回0
// 输入（50，1），返回5 
int getBitValue(int value, int bit) {
    for (int i = 0; i < bit; ++i) {
        value /= 10;
    }
    return value % 10;
}

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 清空排序数组,把每个值赋予0 
        fill(count, count + radixCount, 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] - 1] = arr[i];
            count[bitValue]--;
        } 
        
        // 3.5 临时数组数据拷贝回原数组 
        copy(tempArray, tempArray + len, arr);
    } 
    delete[] count;
    delete[] tempArray;
}

void printArray(int arr[], int len) {
    for (int i = 0; i < len; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {17, 45, 75, 90, 42, 24, 2, 66};
    int len = sizeof(arr) / sizeof(arr[0]);
    
    cout << "原始数组：" << endl;
    printArray(arr, len);
    
    radixSort(arr, len);
    
    cout << "排序后的数组：" << endl;
    printArray(arr, len);
    
    return 0;
}