介绍
前面解释堆排序花费不少力气, 今天介绍很容易理解的一种排序 -- 基数排序. 算法逻辑:
1. 将所有数统一为同位数, 即里面最大的数的位数 (如最大为 1893, 即所有数都写成四位数). 不够位数的前面用 0 补齐 (如 32 补齐四位数为 0032), 当然用更大位数也可以, 只不过会浪费更多存储空间;
2. 依次从低位开始按第 1 位排序, 第 2 位排序... 直到所有位都已排序.
为什么不从高位开始排?
因为具有决定大小的位数是在最高位, 如果放到前面排, 后续低位的排序会把大小顺序打乱.
基数排序
时间复杂度
时间复杂度: O(d(n+r)), 其中: d 为待排列数字的最大位数, n 为待排序列的长度, r 为进制数 .
来源: http://www.jianshu.com/p/cf076f190622