C++ 基数排序的实现实例代码
C++ 基数排序
大家好,今天带来的是自己实现的用C++完成基数排序.在数据结构,算法分析和程序设计的学习过程中,我们经常也无法避免的要学到排序的算法.排序算法是程序设计过程中使用频率极高的算法之一,其输入是一组无序的序列,要求以升序或者降序的方式输出一组有序的序列.对于如二分查找等算法,要求输入是有序的序列,也就是要先排序后查找,由此可见排序算法的重要性.
广为人知的排序算法有冒泡排序,还有选择排序,插入排序.高级一些的有快速排序,希尔排序,堆排序,归并排序,基数排序等. 其中时间复杂度为O(n*logn)的算法有快速排序,归并排序和堆排序等,其中快速排序的使用最为广泛.时间复杂度为O(n2)的算法有冒泡排序,选择排序和插入排序等.
基数排序是一种非比较的排序算法,它是以桶排序为基础的.它们在现代计算机出现之前,一直被用于老式穿孔卡的排序.
基数排序的基本思想是:一共有10个"桶",代表各个数位为0~9.在每个桶上,组织一个优先队列,对于输入的一系列正整数和0,按照个位的大小关系分别进入10个"桶"中.然后遍历每个"桶",按照十位的大小关系进行调整,紧接着是百位,千位.......直到到达最大数的最大位数.结合图例,我们可以理解这个算法:
在C++实现中,我用到了队列这一数据结构作为每个"桶"的组织方式,因为取数总是从最下方取,而放入数这是放入"桶"的顶部,这与队列的队头出对,队尾入队的方式相似.对10个"桶"的组织,则采用向量vector.这个程序支持,输入序列一定范围内不限个数,且在int数据类型表示范围内的非负数排序,根据最大数的位数来决定排序趟数.将数据类型从int改为long或者long long ,则可对更大的整数排序.
排序函数如下:
1 vector<int> radix_sort(vector<int> in) 2 { 3 vector<queue<int>> bucket(10); //十个桶为一个向量,每个桶又是一个队列 4 int max_value = in.at(0); 5 6 for (auto &i : in) 7 { 8 if ( i > max_value) 9 max_value = i; 10 } //找出输入的最大元素 11 12 int n = 0; 13 14 for (; max_value != 0; max_value /= 10, ++n) 15 ; //得到最多位数,也即排序趟数 16 17 for (auto &i : in) 18 bucket.at(0).push(i); //全部放入第一个桶 19 20 int i = 0; //趟数控制变量 21 int m = 0; //提取各个位数有关的控制变量 22 int k = 0; //桶数控制变量 23 int x = 0; //桶的大小,因动态改变了容器,迭代器会失效,不使用迭代器 24 int y = 0; //桶内部控制变量 25 int j = 0; 26 int item = 0; //桶内元素 27 28 for (; i < n ; ++i) //趟数循环 29 { 30 for ( k = 0; k < 10 ; ++k) //遍历每个桶 31 { 32 x = bucket.at(k).size(); 33 34 if ( !x ) 35 continue; 36 37 for (y = 0; y < x ; ++y) //遍历桶中队列的元素 38 { 39 item = j = bucket.at(k).front(); 40 41 for (m = i; m > 0; --m) //提取出各个位 42 j /= 10; 43 44 switch (j % 10) //进入相应的桶 45 { 46 case 0: 47 bucket.at(0).push(item); 48 break; 49 50 case 1: 51 bucket.at(1).push(item); 52 break; 53 54 case 2: 55 bucket.at(2).push(item); 56 break; 57 58 case 3: 59 bucket.at(3).push(item); 60 break; 61 62 case 4: 63 bucket.at(4).push(item); 64 break; 65 66 case 5: 67 bucket.at(5).push(item); 68 break; 69 70 case 6: 71 bucket.at(6).push(item); 72 break; 73 74 case 7: 75 bucket.at(7).push(item); 76 break; 77 78 case 8: 79 bucket.at(8).push(item); 80 break; 81 82 case 9: 83 bucket.at(9).push(item); 84 break; 85 86 default: //异常检测,捕捉与处理 87 try 88 { 89 throw runtime_error("Error!"); 90 } 91 catch (runtime_error err) 92 { 93 cout << err.what() << endl; 94 exit(EXIT_FAILURE); 95 } 96 } 97 98 bucket.at(k).pop(); 99 } 100 } 101 } 102 103 vector<int> out; //定义一个新的向量,将所有桶的数据收集起来作为最后结果 104 105 for ( i = 0; i < 10; ++i ) 106 { 107 int num = bucket.at(i).size(); 108 109 for (int ai = 0; ai < num; ++ai) 110 { 111 out.push_back( bucket.at(i).front() ); 112 bucket.at(i).pop(); 113 } 114 } //排序结果到一个向量中 115 116 return out; //返回这个有序的序列 117 118 }
算法要得到正确结果,要注意的是同一个桶的元素的顺序,是从下至上递增的,这是由遍历时从代表0的"桶"开始和从桶中取 元素时是从下取保证的.再有,最后从桶中取出元素时也要注意顺序.
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25