基数排序博文
https://blog.csdn.net/yabber0914/article/details/52279537
基数排序的实现思路
1.创建一个大桶
用于存放所有的待排序元素的大数组
2.分配元素
从每个元素的最大位或最小位开始依次获取这个元素的小桶下标,并把这个元素放到大桶
中的指定下标的小桶中
其实就是获取每个元素的个位数值,并以个位数值作为要存放的小数组的下标,并找到那个
小数组,然后把这个元素放进去
3.收集元素
遍历大桶的每个小桶,从第一个小桶或者最后一个小桶开始遍历。
从最后一个开始遍历为降序的方式把排序完的元素放回原数组
从第一个开始遍历为升序的方式把排序的完的元素放回原数组
其实就是把放完的每个元素从各个小数组依次取出并删除,然后放回原数组。
4.重复第二步和第三步
直到排序完成,排序完成就是从最小位排到最大位的时候
比如从个位作为下标排到最大位百位作为下标时并循环已结束,这时就是排序完成。
升序思想
收集元素时,把元素从第一个桶开始遍历,然后依次取出
降序思想
收集元素时,把元素从最后一个桶开始遍历,然后依次取出
MSD 分配法
通过元素最高位数开始依次遍历元素并把这个获取到的位数作为元素要存的小桶下标
LSD 分配法
通过元素最小位开始依次遍历元素位数并把这个获取到的位数作为元素要存的小桶下标
注:
元素是升序排序还是降序排序的关键不在于 MSD 分配或 LSD 分配,关键在于收集元素时是
从最后一个桶开始收集还是从第一个桶开始收集
LSD 和 MSD 的主要区别
LSD 不需要递归,LSD 最多分配次数为最大位数
MSD 需要递归,MSD 最多分配次数为从大到小依次分配的次数+每个小桶里只有一个元素为
止的次数
执行效率与稳定性
LSD 和 MSD 相同