Python实现基数排序

一、基数排序简介

基数排序(Radix Sort)是一种非比较型的排序算法，与桶排序的思想相似，对数据进行分桶和合并。

基数排序将数据按位进行分桶，然后将桶中的数据合并。每次分桶只关注其中一位数据，其他位的数据不管，最大的数据有多少位，就进行多少次分桶和合并。基数排序除了用于对整数进行排序，也可以用于对浮点数、字符串进行排序。

基数排序可以分为最高位优先法和最低位优先法，两种方法的结果相同。

最高位优先(Most Significant Digit first)法，简称MSD法。先按最高位进行分桶，合并，一直到最低位，依次进行分桶和合并，便得到一个有序序列。

最低位优先(Least Significant Digit first)法，简称LSD法。先按最低位进行分桶，合并，一直到最高位，依次进行分桶和合并，便得到一个有序序列。

二、基数排序原理

基数排序的原理如下：

1. 求出待排序列表中的最大值，并求出最大值的位(个十百千...)数，有多少位就需要进行多少轮分桶和合并。

2. 开辟内存空间，创建用于分配数据的桶。整数排序时，每一位的范围都在0~9之间，所以需要创建10个桶。

3. 从数据的个位开始(从最高位开始也可以，结果一样)，按个位数对数据进行分桶，不考虑其它位的数据大小。

4. 待排序列表中的所有数据都分桶完成后，将所有桶中的数据进行合并，合并时按先进先出的原则取出桶中的数据。

5. 重复步骤3,4，继续按其他位对前面处理过的数据进行分桶和合并。一直到对每一位数据都进行分桶和合并完成，最终得到一个有序序列，列表排序完成。

以列表 [25, 17, 33, 17, 22, 13, 32, 15, 9, 25, 27, 18] 进行升序排列为例。列表的初始状态如下图。

1. 开辟内存空间，创建用于分配数据的桶。创建0~9的10个桶。

2. 走访待排序列表，按个位数对数据进行分桶。25放入数字为5的桶。

3. 继续走访待排序列表按个位数分桶。17放入数字为7的桶。

4. 继续走访待排序列表按个位数分桶。33放入数字为3的桶。

5. 一直走访完整个待排序列表，将所有数据都放入对应的桶中。

6. 从有数据的桶中将数据取出，进行合并。升序排列时先取数字小的桶，降序反之，每个桶中的数据按添加的顺序取出，先进先出。数字为0和1的桶中没有数据，先取出数字为2的桶中的数据。

7. 继续取出数字为3的桶中的数据。

8. 将所有桶中的数据全部取出。以个位数进行分桶和合并完成，第一轮基数排序结束。

9. 第一轮基数排序已经对个位数进行了排序，得到了一个新的列表。在此基础上，走访此列表中的每一个数据，对它们进行第二轮基数排序，这次按数据的十位数进行分桶和合并。22放入数字为2的桶。

10. 继续走访列表按十位数分桶。32放入数字为3的桶。

11. 继续走访列表按十位数分桶。33放入数字为3的桶。

12. 一直走访完整个列表，将所有数据都放入对应的桶中。

13. 从有数据的桶中将数据取出，进行合并。取数据的方法与按个位数分桶时相同，升序排列时先取数字小的桶，降序反之，每个桶中的数据按添加的顺序取出，先进先出。数字9只有一位，十位为0，所以放在数字为0的桶中，先将其取出。

14. 继续取出数字为1的桶中的数据。

15. 将所有桶中的数据全部取出。以十位数进行分桶和合并完成，第二轮基数排序结束。在本例中，最大的数据只到十位，只需要两轮基数排序就排序完成了，如果最大的数据还有百位千位...，继续按相同的方法进行分桶和合并，直到最高位即可。排序结果如下图。

三、Python实现基数排序

# coding=utf-8
def radix_sort(array):
    max_num = max(array)
    place = 1
    while max_num > 10**place:
        place += 1
    for i in range(place):
        buckets = [[] for _ in range(10)]
        for num in array:
            radix = int(num/(10**i) % 10)
            buckets[radix].append(num)
        j = 0
        for k in range(10):
            for num in buckets[k]:
                array[j] = num
                j += 1
    return array


if __name__ == '__main__':
    array = [25, 17, 33, 17, 22, 13, 32, 15, 9, 25, 27, 18]
    print(radix_sort(array))

运行结果：

[9, 13, 15, 17, 17, 18, 22, 25, 25, 27, 32, 33]

代码中，使用Python内置函数max()求出了待排序列表中的最大值，并求出了最大值的位数place。然后创建了10个桶，从数字的个位数开始，将数据进行分桶，所有数据都分完桶之后，将数据从桶中取出，按顺序重新赋值给待排序列表。

代码中的 i 表示按数据的第 i 位进行分桶，i 从个位一直到最高位，radix 表示分桶时桶对应的数字为 radix，j 表示合并桶中的数据时，将数据赋值给待排序列表中索引 j 的位置。

四、基数排序的时间复杂度和稳定性

1. 时间复杂度

在基数排序中，需要走访待排序列表中的每一个元素进行分桶，列表长度为 n , 然后将每个桶中的数据取出进行合并，一共有 k 个桶，所以进行一轮基数排序的时间复杂度为T(n)=n+k，再乘分桶和合并的步骤数(常数，不影响大O记法)，得出进行一轮基数排序的时间复杂度为 O(n+k) 。当待排序列表中的最大值有 d 位时，需要进行 d 轮基数排序，时间复杂度为 O(d*(n+k)) 。

2. 稳定性

在基数排序中，需要将待排序列表中的数据进行分桶和合并。在分桶时，如果有相等的数据，它们一定会被分到同一个桶中，是按先后顺序进入桶中的，在合并桶时，按先进先出的原则，先进桶的数据先出桶，相等数据的相对次序不会发生变化。所以基数排序是一种稳定的排序算法。