基数排序(Radix Sort)算法是可以利用多个键值来排序数据的算法。排序还需要多个键值?有时候当然会需要啦!像是要排序文件时,可以先依照文件名称排序后,再依照文件大小来排,如此一来,整体上来看这些文件,会是以文件大小来排序,而相同文件大小的文件则是会依照文件名称来排序。基数排序法可以将整数的各个位数当作是键值,来进行线性时间的排序,比起会依照 k(要排序的数据可能的值的数量)愈大而愈吃空间的计数排序法,基数排序法的空间复杂度是比较能够控制的。
基数排序法(Radix Sort)
基数排序法的概念
基数排序法将整数的各个位数当作是键值,可以进行数值上递增、递减的排序,如:[1, 2, 3, 12, 23];或是进行字典排序,如 [1, 12, 2, 23, 3]。
若我们从整数最小的位数(LSD, least significant digit)开始,先把个位数当键值来排序、再把十位数当键值来排序、再把百位数当键值来排序……依此类推,直到完成最高位数的排序之后,就可以排出递增或是递减的串行了!若我们从整数最大的位数(MSD, most significant digit)开始,排到最小的个位数,就会是字典排序。这边要特别注意的是,从 MSD 开始排序的时候,从左边往右开始数的第一个有效位数就是 MSD,例如 8 和 20,8 是 8 的 MSD,2 是 20 的 MSD;从 LSD 开始排序的时候,从右边往左开始数的第一个有效位数就是 LSD,例如 8 和 20,8 是 8 的 LSD,0 是 20 的 LSD。
以程序实作面来说,LSD 的基数排序法比 MSD 的基数排序法还更容易实现。
基数排序法的过程
LSD──递增或递减排序
假设现在有个数组数据,内容如下:
索引 0 1 2 3 4 5 6 7 8 9 数值 69 81 30 38 9 2 47 61 32 79
要如何将它递增排列呢?
首先我们先拿个位数当键值,使用计数排序等适合少量已知数值范围数据且稳定的算法,先将串行进行第一次的递增排序。这边要注意的是,若有元素的位数小于整个串行的元素的最高位数时,要从最高位数开始补 0。
索引 0 1 2 3 4 5 6 7 8 9
数值 6 8 3 3 0 0 4 6 3 7
9 1 0 8 9 2 7 1 2 9 ●
排序后的结果如下:
索引 0 1 2 3 4 5 6 7 8 9
数值 3 8 6 0 3 4 3 6 0 7 ●
0 1 1 2 2 7 8 9 9 9 ○
再来继续排序十位数,排序后的结果如下:
索引 0 1 2 3 4 5 6 7 8 9
数值 0 0 3 3 3 4 6 6 7 8 ○
2 9 0 2 8 7 1 9 9 1 ○
由于此串行最高位数就是十位数,至此就排序完成啦!
MSD──字典排序
假设现在有个数组数据,内容如下:
索引 0 1 2 3 4 5 6 7 8 9 数值 69 81 30 38 9 2 47 61 32 79
要如何以辞典排列原则将它排序完成呢?
这边会需要用到额外的空间。利用十个桶子,编号为 0~9,把目前正在查看的位数是 0~9 的元素个别丢进这十个桶子内。如果该位数的值是 0,就丢进 0 号桶子;如果该位数的值是 5,就丢进 5 号桶子,依此类推。
桶子号码 0 1 2 3 4 5 6 7 8 9 桶子内容 [] [] [] [] [] [] [] [] [] []
一开始当然是先看 MSD,把元素依据 MSD 丢入桶子中之后,桶子的内容此时如下:
[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
桶子号码 0 1 2 3 4 5 6 7 8 9
桶子内容 [] [] [2] [30, 38, 32] [47] [] [69, 61] [79] [81] [9]
接着开始走访所有桶子,寻找所有元素数量大于 1 的桶子,因为它们还需要再分类!
[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
○ ○ ○ ●
桶子号码 0 1 2 3 4 5 6 7 8 9
桶子内容 [] [] [2] [30, 38, 32] [47] [] [69, 61] [79] [81] [9]
我们可以先找到号码 3 的桶子,它拥有三个元素。接着我们再拿十个新桶子出来,编号为 0~9,把原先十个桶子中号码 3 的桶子内的所有元素再分进去,此时要看的位数是目前位数(也就是 MSD)的下一个位数。
[69, 81, 30, 38, 9, 2, 47, 61, 32, 79] -> [30, 38, 32]
桶子号码 0 1 2 3 4 5 6 7 8 9
桶子内容 [30] [] [32] [] [] [] [] [] [38] []
同样地,开始走访所有桶子,寻找所有元素数量大于 1 的桶子,因为它们还需要再分类!
[69, 81, 30, 38, 9, 2, 47, 61, 32, 79] -> [30, 38, 32]
○ ○ ○ ○ ○ ○ ○ ○ ○ ○
桶子号码 0 1 2 3 4 5 6 7 8 9
桶子内容 [30] [] [32] [] [] [] [] [] [38] []
因为已经没有元素数量大于 1 的桶子了,就把这个桶子堆 2 的所有元素,再按照桶子顺序塞回原本在桶子堆 1 的号码 3 的桶子中。
[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
○ ○ ○ ○
桶子号码 0 1 2 3 4 5 6 7 8 9
桶子内容 [] [] [2] [30, 32, 38] [47] [] [69, 61] [79] [81] [9]
接着继续寻找元素数量大于 1 的桶子吧!
[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
○ ○ ○ ○ ○ ○ ●
桶子号码 0 1 2 3 4 5 6 7 8 9
桶子内容 [] [] [2] [30, 32, 38] [47] [] [69, 61] [79] [81] [9]
我们可以找到号码 6 的桶子,它拥有两个元素。接着我们再拿十个新桶子出来,编号为 0~9,把原先十个桶子中号码 6 的桶子内的所有元素再分进去,此时要看的位数是目前位数(也就是 MSD)的下一个位数。
[69, 81, 30, 38, 9, 2, 47, 61, 32, 79] -> [69, 61]
桶子号码 0 1 2 3 4 5 6 7 8 9
桶子内容 [] [61] [] [] [] [] [] [] [] [69]
同样地,开始走访所有桶子,寻找所有元素数量大于 1 的桶子,因为它们还需要再分类!
[69, 81, 30, 38, 9, 2, 47, 61, 32, 79] -> [69, 61]
○ ○ ○ ○ ○ ○ ○ ○ ○ ○
桶子号码 0 1 2 3 4 5 6 7 8 9
桶子内容 [] [61] [] [] [] [] [] [] [] [69]
因为已经没有元素数量大于 1 的桶子了,就把这个桶子堆 3 的所有元素,再按照桶子顺序塞回原本在桶子堆 1 的号码 6 的桶子中。
[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
○ ○ ○ ○ ○ ○ ○
桶子号码 0 1 2 3 4 5 6 7 8 9
桶子内容 [] [] [2] [30, 32, 38] [47] [] [61, 69] [79] [81] [9]
接着继续寻找元素数量大于 1 的桶子吧!
[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
○ ○ ○ ○ ○ ○ ○ ○ ○ ○
桶子号码 0 1 2 3 4 5 6 7 8 9
桶子内容 [] [] [2] [30, 32, 38] [47] [] [61, 69] [79] [81] [9]
因为已经没有元素数量大于 1 的桶子了,就把这个桶子堆 1 的所有元素,按照桶子顺序串接起来吧!
[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
○ ○ ○ ○ ○ ○ ○ ○ ○ ○
桶子号码 0 1 2 3 4 5 6 7 8 9
桶子内容 [] [] [2] [30, 32, 38] [47] [] [61, 69] [79] [81] [9]
└───────────────────────────────┬───────────────────────────────┘
[2, 30, 32, 38, 47, 61, 69, 79, 81, 9]
可以直接用原数组来保存串接结果,如此一来数组就排序完成了!
基数排序法的实作
LSD──递增和递减排序
这边的程序实作是以非常通用的方式来完成,一开始会先找出数组元素中的最大值,为了拿来判断目前是否已经看到最高位数。因为输入的元素有可能会是负数的,所以在寻找最大值的时候要以元素的绝对值为准。另外,计数排序法的部份,会创建出长度为 19 的计数数组,这是因为一个位数可能的值为 -9 ~ +9,共 19 种可能。((n / digit) % 10) + 9 这个算式是先计算出目前要看的位数的值之后,再进行 -(-9) 的索引值位移。
MSD──十进制字典排序(稳定排序)
这边的程序实作是以非常通用的方式来完成,为了要能够排序正数和负数,因此在最一开始,会先将数组元素分为负数和正数两个桶子,再分别对这两个桶子进行从 MSD 开始的排序。在桶子堆的桶子数量方面,这边的程序是使用 11 个,而不是 10 个,多出来的那个(索引编号为 0)是用来保存位数比较少的元素,如此一来在遇到 [40, 4] 的时候,4 才会在 40 的前面,当然,如果没有要这么严格要求这类的顺序的话,一个桶子堆是可以只用 10 个桶子的!
基数排序法的复杂度
以 #{{n}}# 来表示要排序的数据笔数。以 #{{d}}# 来表示数值的位数。以 #{{k}}# 来表示要排序的数据(键值)可能的值的数量,在此即为基数。
| 项目 | 值 | 备注 |
|---|---|---|
| 最差时间复杂度 | LSD:#{{O((n + k) \times d)}}# 稳定 MSD:#{{O(n \times d)}}# |
稳定计数排序法的复杂度再乘以数值的位数。 所有元素都相等时。 |
| 最佳时间复杂度 | LSD:#{{O((n + k) \times d)}}# 稳定 MSD:#{{O(n)}}# |
稳定计数排序法的复杂度再乘以数值的位数。 所有元素的 MSD 都不相同。 |
| 平均时间复杂度 | LSD:#{{O((n + k) \times d)}}# 稳定 MSD:#{{O(n \times d)}}# |
稳定计数排序法的复杂度再乘以数值的位数。 |
| 最差空间复杂度 | LSD:#{{O(n + k)}}# 稳定 MSD:#{{O((n + k) \times d)}}# |
稳定计数排序法的额外空间。 所有元素都相等时,每次的位数检查都会产生 #{{k}}# 个桶子,且其中有一个的桶子空间都会是 #{{n}}#。可用 LinkedList 结构来优化成 #{{O(n + k)}}#。 |
| 是否稳定 | LSD:是 稳定 MSD:是 |
听说原地的 MSD 基数排序法是不稳定的。 |


