终于来到了八大排序的收尾之作~基数排序!之前补充了快排和堆排序的代码与总结,不要忘记补课哦~
基数排序(Radix Sort)
算法思想
基数排序的原理相对于其它方法来说,比较新颖有趣。它将数字按照位数(个十百)切分,然后按每个位数分别比较。对于数字长度不一致情况,将高位(前面)补零。该方法为最低位优先法LSD(Least sgnificant digital)。
举个例子:随机生成一个array: [23, 34, 38, 17, 16, 26, 12, 26, 14, 43]
从0-9,一共10个桶,首先,从左到右,按照个位把它们放到对应桶里:
0:
1:
2: 12
3: 23,43
4: 34,14
5:
6: 16,26,26
7: 17
8: 38
9:
然后把这些数字串起来:[12,23,43,34,14,16,26,26,17,38]
根据串起来后的顺序,按照十位把它们放到对应桶里:
0:
1: 12,14,16,17
2: 23,26,26
3: 34,38
4:43
5:
6:
7:
8:
9:
然后把这些数字串起来:[12,14,16,17,23,26,26,34,38,43]
由于数字最大只到十位,所以到此完成排序。
动图示例来自网络。
算法步骤
LSD基数排序
- 统计数字最大位数,将不满最大位数的数字高位补0;
- 从最低位开始,根据位数数字,将对应元素分配至对应桶中;
- 从0-9,串起桶中数字,形成新序列;
- 位数前进一位,根据新序列继续排序,直到遍历结束最高位,结束。
代码实现
def Radix_Sort(array):
i = 0 # 当前位数
max_len = len(str(max(array)))
while i < max_len:
bucket_list =[[] for x in range(10)]
for x in array:
bucket_list[int(x / (10**i)) % 10].append(x) # 把数字放到对应桶
print(bucket_list)
array.clear()
for x in bucket_list: # 再串起来
for y in x:
array.append(y)
i += 1
改进思路
经典LSD默认基数为10,就是从个位十位依次往上数。但是当数字范围跨度很大得时候,会增大复杂度。这个时候可以选择较大的基数,效果更好。
总结
基数排序时间复杂度为
,k是数字位数,n是序列元素个数。
- 这个比较好理解,对每一趟排序,都需要遍历待排序序列每个数字,放到桶中。而一共需要经历k趟排序;
- 这也和选的基数大小有关。
基数排序空间复杂度为 :
,k是数字位数,n是序列元素个数。
- 这里也比较好理解,创建了k个临时桶,用于存放n个元素。
由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
下期考虑补充一下计数排序和桶排序~ 然后更新一下排序算法合集,有兴趣的同学可以继续关注哦!下期再见!