ZBLOG

基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。对于正整数来说,是将整数按位数切割成不同的数字,然后按每个位数分别比较。 以数组{288 371 260 531 287 235 56 299 18 23}为例。 第一趟收集以个位排序,个位相同的数字按其原本的顺序排序,得到结果:{260 371 531 23 235 56 287 288 18 299}; 第二趟收集以十位排序,十位相同的数字按其原本的顺序排序,得到结果:{18 23 531 235 56 260 3...

以下是使用C++语言编写的基数排序算法代码:

  1. #include <iostream>
  2. #include <vector>
  3. // 获取指定数字的位数
  4. int getDigit(int num, int digit) {
  5. for (int i = 1; i < digit; i++) {
  6. num /= 10;
  7. }
  8. return num % 10;
  9. }
  10. // 基数排序函数
  11. void radixSort(std::vector<int>& arr) {
  12. // 找出最大值确定循环次数
  13. int maxVal = *std::max_element(arr.begin(), arr.end());
  14. int digits = 0;
  15. while (maxVal > 0) {
  16. maxVal /= 10;
  17. digits++;
  18. }
  19. // 创建10个桶,用于存放每个位上的数字
  20. std::vector<std::vector<int>> buckets(10);
  21. // 对每一位进行排序,从个位到最高位
  22. for (int d = 1; d <= digits; d++) {
  23. // 将元素按照当前位放入对应的桶中
  24. for (int num : arr) {
  25. int digitVal = getDigit(num, d);
  26. buckets[digitVal].push_back(num);
  27. }
  28. // 按照桶中的顺序收集元素,并清空桶
  29. int index = 0;
  30. for (auto& bucket : buckets) {
  31. for (int num : bucket) {
  32. arr[index++] = num;
  33. }
  34. bucket.clear();
  35. }
  36. // 输出当前趟的结果
  37. std::cout << "第" << d << "趟收集结果为,顺序表一共" << arr.size() << "个元素:" << std::endl;
  38. for (int num : arr) {
  39. std::cout << num << " ";
  40. }
  41. std::cout << std::endl;
  42. }
  43. // 输出最终排序结果
  44. std::cout << std::endl << "顺序表进行基数排序后,结果为:" << std::endl;
  45. std::cout << "顺序表一共" << arr.size() << "个元素:" << std::endl;
  46. for (int num : arr) {
  47. std::cout << num << " ";
  48. }
  49. std::cout << std::endl;
  50. }
  51. int main() {
  52. int n;
  53. std::cin >> n;
  54. // 输入n个元素
  55. std::vector<int> arr(n);
  56. for (int i = 0; i < n; i++) {
  57. std::cin >> arr[i];
  58. }
  59. // 输出初始顺序表
  60. std::cout << "顺序表一共" << n << "个元素:" << std::endl;
  61. for (int num : arr) {
  62. std::cout << num << " ";
  63. }
  64. std::cout<<std::endl;
  65. // 调用基数排序函数
  66. radixSort(arr);
  67. return 0;
  68. }

注意:以上代码是一个简单的基数排序实现示例,仅供参考。在实际使用中可能需要进行边界检查、异常处理和性能优化等操作。


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=10414

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?