按链式基数排序的方法实现对整数表的排序。用C++写
时间: 2024-03-14 08:42:56 浏览: 22
以下是使用C++实现链式基数排序的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 获取num的第d位数字
int getDigit(int num, int d) {
return (num / d) % 2;
}
// 链式基数排序
void radixSort(vector<int>& nums) {
if (nums.empty()) return;
int maxNum = *max_element(nums.begin(), nums.end());
int d = 1; // 位数
while (maxNum >= d) {
vector<vector<int>> buckets(2); // 桶
for (auto num : nums) {
int digit = getDigit(num, d);
buckets[digit].push_back(num);
}
nums.clear();
for (int i = 0; i < 2; i++) {
for (auto num : buckets[i]) {
nums.push_back(num);
}
}
d *= 2; // 进位
}
}
int main() {
vector<int> nums{ 89, 23, 56, 12, 78, 34 };
radixSort(nums);
for (auto num : nums) {
cout << num << " ";
}
return 0;
}
```
以上代码中,getDigit函数用于获取整数num的第d位数字,buckets是一个大小为2的桶,用于存放num的第d位数字为0或1的数,最后将桶中的数按顺序合并得到排好序的整数表。在主函数中,我们定义一个整数表nums,并调用radixSort函数对其进行排序,最后输出排序结果。