每天一点算法-基数排序(Day11)
介绍
前面解释堆排序花费不少力气,今天介绍很容易理解的一种排序——基数排序。算法逻辑:
1.将所有数统一为同位数,即里面最大的数的位数(如最大为1893,即所有数都写成四位数)。不够位数的前面用0补齐(如32补齐四位数为0032),当然用更大位数也可以,只不过会浪费更多存储空间;
2.依次从低位开始按第1位排序、第2位排序...直到所有位都已排序。
为什么不从高位开始排?
因为具有决定大小的位数是在最高位,如果放到前面排,后续低位的排序会把大小顺序打乱。
基数排序
时间复杂度
时间复杂度:O(d(n+r)),其中:d为待排列数字的最大位数,n为待排序列的长度,r为进制数 。
感谢阅读!欢迎关注!持续更新中...
发表评论 (审核通过后显示评论):