C++排序算法之基数排序_基数排序c++

作者：爱喝兽奶帝天荒 | 2024-08-14 03:52:24

踩

基数排序c++

基数排序

基数排序是一种非比较的排序算法，它是以桶排序为基础的，其思想是“多关键字排序”。

基数排序有两种实现方式：

（1）最高位优先：即先按最高位排成若干子序列，在对每个子序列按次高位排序。

举例：扑克牌的例子，就是先按花色排成4个子序列，在对每种花色的13张牌进行排序，最终使所有的扑克牌整体有序。

（2）最低位优先：这种方式不必分成子序列，每次排序全体元素都参与。

举例：扑克牌的例子，就是先按数字将牌分配到13个桶中，然后从第一个桶开始依次收集；再将收集好的牌按花色分配到4个桶中，然后还是从第一个桶开始依次收集。经过两次“分配”和“收集”操作，最终使牌有序。

执行过程：

原始序列： 278 109 063 930 589 184 505 296 008 083

每个元素都是由“数字”组成，数字的范围是0~9，所以准备10个桶来放元素。如果元素不只有数字组成，例如还有一位是英文字母，那么按字母这一位进行排序时，要准备26个桶（假设不区分大小写）。注意这里所说的“桶”，相当于一个先进先出的队列（从上面进，下面出）。

（1）进行第一趟分配和收集，按照最后位。

分配过程如下（注意数据从桶的上面进入࿰

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/977860