内容简介：推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。基数排序(Radix Sort)算法是一种非比较的排序算法，早在 1887 年 Herman Hollerith 就已经在打孔卡片制表机中使用该算法。一般多用于对整数的排序，但由于整数与某些字符能互相转换，所以它也能够用于字符串的排序。简单来说，基数排序算法就是将整数或字符串切分成不同的数字或字符，然后按对应位置的数或字符
推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种 排序 等等几十篇的样子。
基数排序
基数排序(Radix Sort)算法是一种非比较的排序算法，早在 1887 年 Herman Hollerith 就已经在打孔卡片制表机中使用该算法。一般多用于对整数的排序，但由于整数与某些字符能互相转换，所以它也能够用于字符串的排序。简单来说，基数 排序算法 就是将整数或字符串切分成不同的数字或字符，然后按对应位置的数或字符分别进行比较。
稳定性
基数排序具备稳定性，即能保证相同值元素之间的相对顺序在排序前后一致。基于计数排序的方式主要是通过对计数数组进行前缀和运算，外加通过额外的辅助数组，最后逆序循环将待排序数组中的所有元素放置到辅助数组中，以达到稳定性效果。而基于桶的方式则是通过在每个桶中控制顺序，从而达到稳定性效果。
时间复杂度
基数排序的时间复杂度为Ο(w(n+k))，其中n为待排序数组长度；k为关键字的取值范围，等于进制数，比如十进制则k=10；w为待排序数组元素最大的字长，比如最大字长元素为 358 ，则字长为3。
当k确定后，时间复杂度其实就是O(wn)，但有时还需要考虑字长w，不能简单将其认定为常数。假如取基数为B(即B进制)，待排序集合最大元素为N，k为大于 的最小整数。所以并不是说基数排序就一定完胜最好的比较排序(O(n * log n))，实际过程中还跟所取的基和待排序集合具体的情况相关。
排序方式
基数排序可以采用最高有效数位(MSD)和最低有效数位(LSD)两种方式，其中LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
在算法过程中，对于LSD，对某个有效数位分配后需要执行一次合并，然后再对下一位分配；而对于MSD，对某个有效数位分配后不执行合并，它将继续对相同高位的元素继续进行分配，直到无法继续分配时执行合并操作。
基于桶实现
基于桶方式是指使用桶作为辅助工具，过程中循环每个有效数位将元素分配到对应的桶中，从而实现基数排序。
基于桶方式的基数排序的操作步骤如下：
- 确定桶的数量，由进制数确定，比如十进制则桶的数量为10，分别代表0到9，并且每个桶内的结构为队列。
- 从最低有效位到最高有效位，针对每个有效位执行步骤3到步骤5。
- 按顺序遍历待排序数组，根据当前有效位将它们分配到对应桶的队列中。
- 按桶编号顺序进行遍历，将每个桶中队列按顺序收集到原数组中。
- 选择下一个有效位执行步骤2到步骤4，直到所有有效位处理完得到的结果即是最终的结果。
同样是对前面的8位小学生的语数英总成绩进行基于桶方式的基数排序操作。一共有8个学生，所以待排序数组长度为8。而且因为使用十进制，所以桶的索引范围是0-9。此外每个桶对应创建一个队列，这里假设队列长度为5，长度也可以为待排序数组长度，但实际中更多使用动态扩展策略。
第一阶段：针对个位数将元素放到对应的桶中。
待排序数组的第一个元素的健值为198，放到编号8的桶中。
第二个元素的健值为248，放到编号为8的桶中。
第三个元素的健值为98，放到编号为8的桶中。
第四个元素的健值为247，放到编号为7的桶中。
类似地，将剩下的元素都放到对应桶中的队列，可以看到每个桶中的队列维护了顺序性。
接着按桶顺序将桶中队列输出到原数组中，先输出编号为0的桶。
接着输出编号为7的桶。
再输出编号为8的桶。
最后输出编号为9的桶。
第二阶段：针对十位数将元素放到对应的桶中。
待排序数组的第一个元素的健值为80，放到编号8的桶中。
第一个元素的健值为247，放到编号4的桶中。
将剩下的元素都放到对应桶中的队列。
将编号为4的桶的队列输出到原数组中。
将编号为8的桶的队列输出到原数组中。
将编号为9的桶的队列输出到原数组中。
第三阶段：针对百位数将元素放到对应的桶中。
第一个元素的健值为247，放到编号2的桶中。
第二个元素的健值为247，放到编号2的桶中。
将剩下的元素都放到对应桶中的队列。
将编号为0的桶的队列输出到原数组中。
将编号为1的桶的队列输出到原数组中。
将编号为2的桶的队列输出到原数组中。
至此，以上完成整个排序过程。
-------------推荐阅读------------
我的开源项目汇总(机器&深度学习、NLP、网络IO、AIML、 mysql 协议、chatbot)
跟我交流，向我提问：
欢迎关注：
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- 排序算法下——桶排序、计数排序和基数排序
- 计数排序vs基数排序vs桶排序
- 小白学数据结构——四、排序算法Python（桶、计数、基数排序）
- Elasticsearch 高基数聚合性能提升 3 倍，改动了什么？
- 图形化排序算法比较：快速排序、插入排序、选择排序、冒泡排序
- 算法之常见排序算法-冒泡排序、归并排序、快速排序
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
The Sovereign Individual
James Dale Davidson、William Rees-Mogg / Free Press / 1999-08-26 / USD 16.00
Two renowned investment advisors and authors of the bestseller The Great Reckoning bring to light both currents of disaster and the potential for prosperity and renewal in the face of radical changes ......一起来看看 《The Sovereign Individual》 这本书的介绍吧!
