C++中的基数排序法
基数排序是一种非比较性质的排序算法，它将待排序的元素分配到各个“桶”中，再按照每个桶中元素的顺序依次取出来，从而实现排序的过程。这个算法的核心思想是：先按照元素的个位数字进行排序，然后按照十位、百位、千位等高位数字进行排序，最终就能够得到一个有序的序列。
下面是基数排序的详细步骤：
找出待排序数组中最大的数字，并确定它的位数，即最高位数。
对每一位上的数字进行排序。从最低位开始，对于每一个位上的数字，将待排序数组中的元素分配到对应的桶中。例如，对于个位数字为1的元素，将其放入编号为1的桶中。然后，按照桶的顺序，将所有桶中的元素依次取出来，放回到待排序数组中。这样就完成了对个位数字的排序。
重复步骤2，对十位、百位、千位等高位数字进行排序。每一轮排序完成后，将所有元素放回到待排序数组中。
最终，待排序数组就变成了一个有序的序列。
下面是使用C++语言实现基数排序的示例代码：
#include <iostream>
#include <vector>
using namespace std;
// 获取一个数字的第pos位上的数字
int getDigit(int num, int pos) {
int div = 1;
for (int i = 0; i < pos - 1; i++) {
div *= 10;
}
return (num / div) % 10;
}
void radixSort(vector<int>& arr) {
// 获取待排序数组中的最大值
int maxVal = arr[0];
for (int i = 1; i < arr.size(); i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
// 计算最大值的位数
int maxDigits = 0;
while (maxVal != 0) {
maxVal /= 10;
maxDigits++;
}
// 对每一位进行排序
for (int pos = 1; pos <= maxDigits; pos++) {
// 初始化桶
vector<vector<int>> buckets(10);
// 将元素分配到桶中
for (int i = 0; i < arr.size(); i++) {
int digit = getDigit(arr[i], pos);
buckets[digit].push_back(arr[i]);
}
// 将桶中的元素放回到数组中
int idx = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < buckets[i].size(); j++) {
arr[idx++] = buckets[i][j];
}
}
}
}
int main() {
vector<int> arr = {23, 67, 3,6, 34, 56, 89, 44, 12, 78};
cout << "排序前的数组：";
for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << endl;
radixSort(arr);
cout << "排序后的数组：";
for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}输出结果：
排序前的数组：23 67 3 6 34 56 89 44 12 78 排序后的数组：3 6 12 23 34 44 56 67 78 89
在这个示例代码中，我们首先实现了一个`getDigit`函数，用于获取一个数字的第pos位上的数字。然后，我们实现了`radixSort`函数，其中对每一位上的数字进行排序，并将排序后的元素放回到原数组中。最终，我们在`main`函数中调用`radixSort`函数，对一个包含10个元素的数组进行排序，并输出排序前后的结果。
需要注意的是，基数排序的时间复杂度为O(d*(n+k))，其中d是数字的最高位数，n是待排序数组的长度，k是桶的个数。虽然基数排序的时间复杂度较低，但是由于它需要使用较多的空间来存储桶，所以在实际应用中可能会存在一定的局限性。
在基数排序中，我们需要创建一个包含10个桶的数组，用来存放当前位上数字为0~9的元素。具体过程如下：
对于当前需要排序的位数，比如个位、十位、百位等，我们需要遍历待排序的数组，取出每个元素的该位数字。比如，如果当前需要按个位数字排序，那么我们需要取出23、67、3、6和45的个位数字，分别是3、7、3、6和5。
将取出的数字对应放入相应的桶中。比如，将个位数字为3的元素放入编号为3的桶中，将个位数字为7的元素放入编号为7的桶中，以此类推。最终，我们就可以得到10个桶，分别存放了待排序数组中所有元素当前位数字相同的元素。
将桶中的元素按照顺序取出，放回到原数组中。这个过程需要注意的是，对于一个桶中的元素，它们在原数组中的顺序可能不是按照该位数字升序排列的。因此，我们需要依次取出每个桶中的元素，并按照从编号0到9的顺序依次放回到原数组中。
重复上述过程，直到对所有位数都进行过排序。这样，我们就可以得到一个有序的数组。
