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

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

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

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

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

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

算法过程

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

演示示例

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

step 1:

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

step 2:

遍历待排序集合，当位数

index

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

step 3:

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

重复执行 step 2 和 step 3：

circle 1:

当位数

index

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

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

circle 2:

当位数

index

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

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

circle 3:

当位数

index

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

将桶中所有元素移动回原始序列后，序列为：[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)

。

其实基数排序中不一定按照每一位进行排序，也可能元素中的几位构成了一个组合，按照组合为单位进行排序。同时排序算法也不一定是桶排序方式，可以是别的排序算法，也可以给不同位使用不同的排序算法。总之基数排序提供了一个针对复杂元素类型的排序思路，可以针对元素中不同部分，选择不同的排序方式。