排序算法（十）：基数排序

作者: zhipingChen | 来源:发表于2018-08-29 22:45 被阅读6次

基数排序也可以称为多关键字排序，同计数排序类似，也是一种非比较性质的排序算法。将待排序集合中的每个元素拆分为多个总容量空间较小的对象，对每个对象执行桶排序后，则完成排序过程。

基数排序在桶排序的基础上做了优化，桶排序需要选择适当的映射规则，来完成集合中元素到多个桶的映射，也可以称之为值域划分。但是当集合中元素跨度很大时，映射规则的设计比较困难，若规则设计的宽泛一些，则桶的个数较少，随便避免了许多空桶的情况，但是可能会存在元素分布不均，桶排序则演变为普通的比较性质排序；若规则设计的较为精确，则桶的个数较多，可能会存在大部分桶都是空桶的情况，存在较大空间浪费。

桶排序之所以存在上述问题，原因在于算法中对待排序元素的属性选择所致。排序过程选择使用了元素本身的 “大小” 属性，所以算法处理的元素集合就是这个 “大小” 空间。例如，若待排序元素为整型，而整型数字在 “大小” 方面可以是无限大或者无限小的；若待排序元素为字符串，而字符串在 “长度” 方面是无限大的。而桶排序又是一种对元素总容量敏感的排序算法，所以存在使用限制。

基数排序过程中也使用了桶排序操作，不过对于桶排序面向的对象进行了优化。例如，若元素是整数类型，则选择元素的每位数字作为排序对象，因为每个数字的容量空间大小只是 10；同理若元素是字符串，则选择元素的每位字符，因为每个字符的容量空间大小为 26。所以在基数排序过程中，给其中的桶排序操作选择了容量空间有限的排序对象。

基数排序中的桶排序操作具有一点特殊性，即每个桶的宽度，或者称为值域跨度为一，所以将待排序集合中所有元素移动到各个桶上之后，不需要再对每个桶进行排序。

算法过程

根据待排序元素的类型申请桶空间，并从待排序集合中计算出元素的最大位数；
从右向左，根据元素当前位数的值，将所有元素移动到对应的桶中；
将所有桶中元素移动回原始集合中；
重复步骤 2, 3，直到遍历完所有位数。

演示示例

待排序集合为：[1086, 187, 30, 76, 0, 1359, 36, 777, 9, 2]

step 1:

因为此处选择的待排序集合元素类型为十进制整数，所以基数为 10，申请的桶个数为：10，其中元素的最大位数为 4。

step 2:

遍历待排序集合，当位数 $index$ 值为 1 时，根据元素个位数字，将待排序集合中所有元素移动到对应的桶中：

桶下标	桶中元素
0	30, 0
1
2	2
3
4
5
6	1086, 76, 36
7	187, 777
8
9	1359, 9

step 3:

将桶中所有元素移动回原始序列后，序列为：[30, 0, 2, 1086, 76, 36, 187, 777, 1359, 9]

重复执行 step 2 和 step 3：

circle 1:

当位数 $index$ 值为 2 时，根据元素十位数字，将集合中所有元素移动到对应的桶中：

桶下标	桶中元素
0	0, 2, 9
1
2
3	30, 36
4
5	1359
6
7	76, 777
8	1086, 187
9

将桶中所有元素移动回原始序列后，序列为：[0, 2, 9, 30, 36, 1359, 76, 777, 1086, 187]

circle 2:

当位数 $index$ 值为 3 时，根据元素百位数字，将集合中所有元素移动到对应的桶中：

桶下标	桶中元素
0	0, 2, 9, 30, 36, 76, 1086
1	187
2
3	1359
4
5
6
7	777
8
9

将桶中所有元素移动回原始序列后，序列为：[0, 2, 9, 30, 36, 76, 1086, 187, 1359, 777]

circle 3:

当位数 $index$ 值为 4 时，根据元素千位数字，将集合中所有元素移动到对应的桶中：

桶下标	桶中元素
0	0, 2, 9, 30, 36, 76, 187, 777
1	1086, 1359
2
3
4
5
6
7
8
9

将桶中所有元素移动回原始序列后，序列为：[0, 2, 9, 30, 36, 76, 187, 777, 1086, 1359]

算法示例

def radixSort(arr, radix=10):  # elements in the array are all non-negative integers
    k = math.ceil(math.log(max(arr) + 1, radix))  # calculate the digit length
    radixArr = [[] for i in range(radix)]  # apply the space
    for i in range(k):          # sort each digit
        for j in arr:       # add every element in the array to radixArr
            radixArr[j // (radix ** i) % radix].append(j)
        arr.clear()
        for a in radixArr: # add every element in radixArr to the array
            arr.extend(a)
            a.clear()

代码中第一层循环对最大元素每一位进行桶排序，也就是迭代比较的次数，嵌套包括两个循环，第一个循环为将序列中所有元素移动到对应的桶中，第二个循环为将桶中所有元素移动回序列中。若元素最大位数为 $K$ ，则算法的复杂为 $O(K*(N+N))$ 。

算法分析

由算法过程可知，基数排序的时间复杂度为 $O(KN)$ ，其中 $K$ 为元素最大位数，也就是迭代比较的次数。算法过程中不存在元素之间的跨位置交换，属于稳定排序方式。算法过程中需要申请的空间大小为 $N+R$ ，其中 $R$ 表示待排序元素的基数，例如示例中的十进制整数排序，则 $R=10$ ；若待排序元素为字符串，则 $R=26$ ，因为基数的容量空间总是有限的，所以算法的时间复杂度为 $O(N)$ 。