以下是使用C++语言编写的基数排序算法代码:
#include <iostream>
#include <vector>
// 获取指定数字的位数
int getDigit(int num, int digit) {
for (int i = 1; i < digit; i++) {
num /= 10;
}
return num % 10;
}
// 基数排序函数
void radixSort(std::vector<int>& arr) {
// 找出最大值确定循环次数
int maxVal = *std::max_element(arr.begin(), arr.end());
int digits = 0;
while (maxVal > 0) {
maxVal /= 10;
digits++;
}
// 创建10个桶,用于存放每个位上的数字
std::vector<std::vector<int>> buckets(10);
// 对每一位进行排序,从个位到最高位
for (int d = 1; d <= digits; d++) {
// 将元素按照当前位放入对应的桶中
for (int num : arr) {
int digitVal = getDigit(num, d);
buckets[digitVal].push_back(num);
}
// 按照桶中的顺序收集元素,并清空桶
int index = 0;
for (auto& bucket : buckets) {
for (int num : bucket) {
arr[index++] = num;
}
bucket.clear();
}
// 输出当前趟的结果
std::cout << "第" << d << "趟收集结果为,顺序表一共" << arr.size() << "个元素:" << std::endl;
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
}
// 输出最终排序结果
std::cout << std::endl << "顺序表进行基数排序后,结果为:" << std::endl;
std::cout << "顺序表一共" << arr.size() << "个元素:" << std::endl;
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
}
int main() {
int n;
std::cin >> n;
// 输入n个元素
std::vector<int> arr(n);
for (int i = 0; i < n; i++) {
std::cin >> arr[i];
}
// 输出初始顺序表
std::cout << "顺序表一共" << n << "个元素:" << std::endl;
for (int num : arr) {
std::cout << num << " ";
}
std::cout<<std::endl;
// 调用基数排序函数
radixSort(arr);
return 0;
}
注意:以上代码是一个简单的基数排序实现示例,仅供参考。在实际使用中可能需要进行边界检查、异常处理和性能优化等操作。
内容由零声教学AI助手提供,问题来源于学员提问