基数排序详细说明及实现

您所在的位置:网站首页 python将数字按大小排列for 基数排序详细说明及实现

基数排序详细说明及实现

#基数排序详细说明及实现| 来源: 网络整理| 查看: 265

说明:

        基数排序使用多关键字排序:基数排序和桶排序一样都用到了桶,但是基数排序是分固定10个桶就行。每个桶分别代表0-9这10个数字,那么对于很多数的序列这只有10个数字是如何排序的呢,其实当数字分到桶中时就完成了一次排序,0-9这10个桶就相当于间接排序了。

        关键字排序:一个数字有个位,十位,百位...每一位都是关键字,对多个关键字分别进行排序,第一次序列中个位上的数字保持有序、第二次十位上的数字保持有序、第三次百位上的数字保持有序......直到最高位数字有序,此时排序完成。

        当数字范围在0-9之间,那么一次分桶就能完成排序。

        当数字范围在0-99之间,需要两次分桶完成排序。第一次分桶按照个位数字分桶,这样序列整体在个位上就是有序的。然后再次分桶,按照十位数字分桶,因为个位从小到大有序,所以第二次每个桶中的个位还是有序的,又因为每个桶是按照从小到大排序的,所以依次输出到原序列即可。

        当数字范围在0-999之间,需要三次分桶完成排序。第一次分桶以个位为关键字、第二次分桶以十位为关键字、第三次分桶以百位为关键字。在第三次分桶时,十位和个位均已按顺序排序,只有百位数字无序,此时将百位置为关键字,分桶完成后,百位数字也就按照桶的顺序有序排列,所有数字位都有序,排序完成。

        . . . . . . 

总结:

        遍历序列,先按照个位数字进行分桶,将数字分到其个位数字对应的桶中,完成后依次将桶中数字写回原序列。再次遍历序列,这次按照十位数字为关键字进行分桶,将数字分到其十位数字对应的桶中,完成后依次将桶中数字写回原序列。直到序列中数字最高位分桶完毕,序列整体有序,排序完成。



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3