基数排序C++代码实现

基数排序是一种非比较整数排序算法，它通过将待排序的数字按照位数切割成不同的数字，然后按每个位数分别进行排序。以下是C++实现基数排序的一个简单示例，假设我们对无负整数进行排序：

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

// 计算最大值的位数
int getMaxBit(int arr[], int n) {
    int max_num = *std::max_element(arr, arr + n);
    return (int)log10(max_num) + 1;
}

// 对每一位进行桶排序
void countingSort(int arr[], int exp, int n) {
    std::vector<int> output(n, 0);
    std::vector<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];

    // 将元素从桶中取出并放入output数组
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 将output数组的内容复制回原数组
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

// 主函数：基数排序
void radixsort(int arr[], int n) {
    int m = getMaxBit(arr, n); // 获取最大位数

    for (int exp = 1; m > 0; exp *= 10)
        countingSort(arr, exp, n);
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    radixsort(arr, n);

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";

    return 0;
}

这个程序首先计算出输入数组的最大位数，然后从最低位开始，逐位进行桶排序。在`countingSort`函数中，它创建了一个计数数组来跟踪每个桶（由当前位确定）中的元素数量。