编辑代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 获取数组中的最大值
int get_max(vector<int>& arr) {
    int max_val = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        max_val = max(max_val, arr[i]);
    }
    return max_val;
}

// 获取最大值的位数
int get_digit(int num) {
    int digit = 0;
    while (num > 0) {
        digit++;
        num /= 10;
    }
    return digit;
}

// 基数排序
void radix_sort(vector<int>& arr) {
    int max_val = get_max(arr); // 获取最大值
    int max_digit = get_digit(max_val); // 获取最大值的位数
    int base = 1; // 基数，从个位开始
    vector<int> tmp(arr.size()); // 临时数组，用于存放排序后的元素
    vector<int> count(10); // 计数数组，用于统计每个桶中的元素个数
    for (int i = 0; i < max_digit; i++) { // 对每一位进行排序
        fill(count.begin(), count.end(), 0); // 清空计数数组
        for (int j = 0; j < arr.size(); j++) { // 统计每个桶中的元素个数
            int index = (arr[j] / base) % 10; // 计算当前位的数字
            count[index]++;
        }
        for (int j = 1; j < 10; j++) { // 计算每个桶的起始位置
            count[j] += count[j - 1];
        }
        for (int j = arr.size() - 1; j >= 0; j--) { // 将元素放入临时数组中
            int index = (arr[j] / base) % 10; // 计算当前位的数字
            tmp[count[index] - 1] = arr[j]; // 放入对应的位置
            count[index]--; // 更新计数数组
        }
        copy(tmp.begin(), tmp.end(), arr.begin()); // 将临时数组复制到原数组中
        base *= 10; // 增加基数
    }
}

// 打印数组
void print_array(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 测试程序
int main() {
    // 使用数组初始化vector，指定数组的首尾地址
    int a[] = {53, 3, 542, 748, 14, 214, 154, 63, 616}; // 定义数组
    vector<int> arr(a, a + 9); // 初始化vector
    cout << "原始数组：" << endl;
    print_array(arr);
    radix_sort(arr); // 基数排序
    cout << "排序后的数组：" << endl;
    print_array(arr);
    return 0;
}