排序算法——基数排序

概述

基数排序(radix sort)算法,就是按照整数的个位、十位、百位...等依次排列元素,局部最优排列最终可以获得全局最优。

基数排序可以分为LSD和MSD两种,LSD就是从低位往高位排(个十百...),MSD是从高位往低位排(...百十个)。

基数排序的时间复杂度为\(O(n*k)\),其中\(n\)为元素数量,\(k\)为最大元素的最高位(个位为1,十位为2......),当元素不是很大时(即\(k\)很小)可认为时间复杂度为\(O(n)\).


实现过程

算法步骤:

  1. 取得数组中的最大数,并取得位数;

  2. 对数位较短的数前面补零;

  3. 分配,先从个位开始,根据位值(0-9)分别放到0~9号桶中;

  4. 收集,再将放置在0~9号桶中的数据按顺序放到数组中;

  5. 重复3~4过程,直到最高位,即可完成排序。

对如下序列进行基数排序:[345,21,342,786,55,2,453,66,98,145,46,76,5,674].

采用LSD的方式来进行基数排序。

  • 第一步,按照个位分组
个位 分组
0 -
1 21
2 342,2
3 453
4 674
5 345,55,145,5
6 786,66,46,76
7 -
8 98
9 -

依次连接后新的数组:[21, 342, 2, 453, 674, 345, 55, 145, 5, 786, 66, 46, 76, 98]

  • 第二步,按照十位分组
十位 分组
0 2,5
1 -
2 21
3 -
4 342,345,145,46
5 453,55
6 66
7 674,76
8 786
9 98

依次连接后的新数组:[2, 5, 21, 342, 345, 145, 46, 453, 55, 66, 674, 76, 786, 98]

  • 第三步,按照百位分组
百位 分组
0 2,5,21,46,55,66,76,98
1 145
2 -
3 342,345
4 453
5 -
6 674
7 786
8 -
9 -

连接后的最终排序数组:[2, 5, 21, 46, 55, 66, 76, 98, 145, 342, 345, 453, 674, 786]

实例代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def radix(nums):
factor = 1
max_num = max(nums)
n = 1
while max_num >= 10: # 获取最高位
max_num //= 10
n += 1
while factor < 10 ** n:
temp = [[] for _ in range(10)]
for i in nums:
temp[i // factor % 10].append(i) # 元素归并到相应位的相应位置
nums = []
for i in temp:
nums += i
factor *= 10
return nums


if __name__ == '__main__':
print(radix([345, 21, 342, 786, 55, 2, 453, 66, 98, 145, 46, 76, 5, 674]))

[out]:
[2, 5, 21, 46, 55, 66, 76, 98, 145, 342, 345, 453, 674, 786]

尾记

基数排序思想也较为巧妙,时间复杂度达到了线性。但其应用受到限制,常用于非负整数序列的排序。