基数排序详细说明及实现 |
您所在的位置:网站首页 › python将数字按大小排列for › 基数排序详细说明及实现 |
说明: 基数排序使用多关键字排序:基数排序和桶排序一样都用到了桶,但是基数排序是分固定10个桶就行。每个桶分别代表0-9这10个数字,那么对于很多数的序列这只有10个数字是如何排序的呢,其实当数字分到桶中时就完成了一次排序,0-9这10个桶就相当于间接排序了。 关键字排序:一个数字有个位,十位,百位...每一位都是关键字,对多个关键字分别进行排序,第一次序列中个位上的数字保持有序、第二次十位上的数字保持有序、第三次百位上的数字保持有序......直到最高位数字有序,此时排序完成。 当数字范围在0-9之间,那么一次分桶就能完成排序。 当数字范围在0-99之间,需要两次分桶完成排序。第一次分桶按照个位数字分桶,这样序列整体在个位上就是有序的。然后再次分桶,按照十位数字分桶,因为个位从小到大有序,所以第二次每个桶中的个位还是有序的,又因为每个桶是按照从小到大排序的,所以依次输出到原序列即可。 当数字范围在0-999之间,需要三次分桶完成排序。第一次分桶以个位为关键字、第二次分桶以十位为关键字、第三次分桶以百位为关键字。在第三次分桶时,十位和个位均已按顺序排序,只有百位数字无序,此时将百位置为关键字,分桶完成后,百位数字也就按照桶的顺序有序排列,所有数字位都有序,排序完成。 . . . . . . 总结: 遍历序列,先按照个位数字进行分桶,将数字分到其个位数字对应的桶中,完成后依次将桶中数字写回原序列。再次遍历序列,这次按照十位数字为关键字进行分桶,将数字分到其十位数字对应的桶中,完成后依次将桶中数字写回原序列。直到序列中数字最高位分桶完毕,序列整体有序,排序完成。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |