基数排序也可以称为多关键字排序，同计数排序类似，也是一种非比较性质的排序算法。将待排序集合中的每个元素拆分为多个总容量空间较小的对象，对每个对象执行桶排序后，则完成排序过程。
基数排序在桶排序的基础上做了优化，桶排序需要选择适当的映射规则，来完成集合中元素到多个桶的映射，也可以称之为值域划分。但是当集合中元素跨度很大时，映射规则的设计比较困难，若规则设计的宽泛一些，则桶的个数较少，随便避免了许多空桶的情况，但是可能会存在元素分布不均，桶排序则演变为普通的比较性质排序；若规则设计的较为精确，则桶的个数较多，可能会存在大部分桶都是空桶的情况，存在较大空间浪费。
桶排序之所以存在上述问题，原因在于算法中对待排序元素的属性选择所致。排序过程选择使用了元素本身的 “大小” 属性，所以算法处理的元素集合就是这个 “大小” 空间。例如，若待排序元素为整型，而整型数字在 “大小” 方面可以是无限大或者无限小的；若待排序元素为字符串，而字符串在 “长度” 方面是无限大的。而桶排序又是一种对元素总容量敏感的排序算法，所以存在使用限制。
基数排序过程中也使用了桶排序操作，不过对于桶排序面向的对象进行了优化。例如，若元素是整数类型，则选择元素的每位数字作为排序对象，因为每个数字的容量空间大小只是 10；同理若元素是字符串，则选择元素的每位字符，因为每个字符的容量空间大小为 26。所以在基数排序过程中，给其中的桶排序操作选择了容量空间有限的排序对象。
基数排序中的桶排序操作具有一点特殊性，即每个桶的宽度，或者称为值域跨度为一，所以将待排序集合中所有元素移动到各个桶上之后，不需要再对每个桶进行排序。
算法过程
- 根据待排序元素的类型申请桶空间，并从待排序集合中计算出元素的最大位数；
- 从右向左，根据元素当前位数的值，将所有元素移动到对应的桶中；
- 将所有桶中元素移动回原始集合中；
- 重复步骤 2, 3，直到遍历完所有位数。
演示示例
待排序集合为：[1086, 187, 30, 76, 0, 1359, 36, 777, 9, 2]
step 1:
因为此处选择的待排序集合元素类型为十进制整数，所以基数为 10，申请的桶个数为：10，其中元素的最大位数为 4。
step 2:
遍历待排序集合，当位数 值为 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：
cycle 1:
当位数 值为 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]
cycle 2:
当位数 值为 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]
cycle 3:
当位数 值为 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()
代码中第一层循环对最大元素每一位进行桶排序，也就是迭代比较的次数，嵌套包括两个循环，第一个循环为将序列中所有元素移动到对应的桶中，第二个循环为将桶中所有元素移动回序列中。若元素最大位数为 ，则算法的复杂为
。
算法分析
由算法过程可知，基数排序的时间复杂度为 ，其中
为元素最大位数，也就是迭代比较的次数。算法过程中不存在元素之间的跨位置交换，属于稳定排序方式。算法过程中需要申请的空间大小为
，其中
表示待排序元素的基数，例如示例中的十进制整数排序，则
；若待排序元素为字符串，则
，因为基数的容量空间总是有限的，所以算法的时间复杂度为
。
其实基数排序中不一定按照每一位进行排序，也可能元素中的几位构成了一个组合，按照组合为单位进行排序。同时排序算法也不一定是桶排序方式，可以是别的排序算法，也可以给不同位使用不同的排序算法。总之基数排序提供了一个针对复杂元素类型的排序思路，可以针对元素中不同部分，选择不同的排序方式。
github链接：基数排序
