1.概念
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
2.基本思想
假如待排序的序列中最大元素有d位，而有的数没有d位那么多，则在其欠缺的高位补0，将元素先按最低位（设最右边的位为最低位）的值进行排序，然后按次低位进行排序......以此类推，最后进行最高位的排序。
3.排序过程
图1
图2
图3
4.程序展示(python3)
图4
5.稳定性
基数排序在排序过程中，是将当前位数上的相同元素放置于预设的桶中，而不需要元素间进行交换，所以基数排序是稳定性的。
6.时间复杂度
O(nlog(r)m)
n为待排序列的记录
r为所采取的基数
m为堆数
扩展：基数排序分为LSD(最低优先法)与MSD(最高优先法)两类，上述将的都是LSD最低优先法，而MSD与上述大同小异，大家有兴趣可以研究下。
参考文献：
上述概念参考百度百科点击这里查看
有什么问题请留言，大家一起探讨学习😊😊😊。
网友评论