基数排序(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   ○

由于此串行最高位数就是十位数,至此就排序完成啦!

LSD 基数排序的过程动画

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]

可以直接用原数组来保存串接结果,如此一来数组就排序完成了!

MSD 字典排序的过程动画

基数排序法的实作

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 基数排序法是不稳定的。