基数排序步骤及c++代码

基数排序是一种按照位数进行排序的算法，适用于非负整数的排序。下面是基数排序的步骤及C++代码示例：

步骤：
1. 找到待排序数组中的最大值，并确定最大值的位数，记为max_digits。
2. 创建10个桶数组，用于存储每个位数上的元素，初始化为空。
3. 从低位到高位，对每个位数进行排序：
- 将待排序数组中的元素按照当前位数的值放入对应的桶中。
- 将每个桶中的元素按顺序合并到一个临时数组中。
- 将临时数组复制回待排序数组。
4. 重复第3步，直到对max_digits位数进行排序完成。

C++代码示例：

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

int getMax(int arr[], int n) {
    int max_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }
    return max_val;
}

void countingSort(int arr[], int n, int exp) {
    vector<int> output(n);
    int count[10] = {0};

    // 统计当前位数上各个元素的出现次数
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    // 对count[]进行累加
    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[]复制回原数组arr[]
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

void radixSort(int arr[], int n) {
    int max_val = getMax(arr, n);

    // 对每个位数进行排序
    for (int exp = 1; max_val / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

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] << " ";
    }
    cout << endl;

    return 0;
}

这段代码实现了基数排序算法，对给定的非负整数数组进行排序。运行后输出排序后的数组：2 24 45 66 75 90 170 802。