内容简介：推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。基数排序(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 倍，改动了什么？
- 图形化排序算法比较：快速排序、插入排序、选择排序、冒泡排序
- 算法之常见排序算法-冒泡排序、归并排序、快速排序
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
白帽子讲Web安全（纪念版）
吴翰清 / 电子工业出版社 / 2014-6 / 69.00元
互联网时代的数据安全与个人隐私受到前所未有的挑战，各种新奇的攻击技术层出不穷。如何才能更好地保护我们的数据？《白帽子讲Web 安全（纪念版）》将带你走进Web 安全的世界，让你了解Web 安全的方方面面。黑客不再神秘，攻击技术原来如此，小网站也能找到适合自己的安全道路。大公司如何做安全，为什么要选择这样的方案呢？在《白帽子讲Web 安全（纪念版）》中都能找到答案。详细的剖析，让你不仅能“知其然”，......一起来看看 《白帽子讲Web安全（纪念版）》 这本书的介绍吧!
