排序算法——基数排序

发表于 更新于 分类于 ， ， ，

概述

基数排序(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]

尾记

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