用C++实现基数排序

以下是C++实现基数排序的代码示例：

#include <iostream>
using namespace std;

// 获取数组中最大值
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max {
            max = arr[i];
        }
    }
    return max;
}

// 基数排序
void radixSort(int arr[], int n) {
    int max = getMax(arr, n); // 获取最大值
    for (int exp = 1; max / exp > 0; exp *= 10) { // 从个位开始排序
        int output[n]; // 存储排序后的数组
        int count[10] = {0}; // 存储每个数字出现的次数
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++; // 统计每个数字出现的次数
        }
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1]; // 计算每个数字在排序后数组中的位置
        }
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i]; // 将数字放入排序后数组中
            count[(arr[i] / exp) % 10]--; // 更新数字出现的次数
        }
        for (int i = 0; i < n; i++) {
            arr[i] = output[i]; // 将排序后数组复制到原数组中
        }
    }
}

// 测试
int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    radixSort(arr, n);
    cout << "排序后的数组：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}