本文以维基百科作为主要参考资料，记录了我对基数排序的思考过程，既用于思维训练，也方便将来回顾。

注：文中的 key 为待排序集合中的单个元素，与英文资料的指代相同（如维基百科和 CLRS 等）。

主要内容：

1.概述

基数排序 (Radix Sort) 是类似于桶排序和计数排序的一种分布式排序。与后者的最大区别是，基数排序通过对 key 的各个数位逐一排序，从而使待排序元素从局部有序变为整体有序，而桶排序和计数排序均是直接对整个 key 进行统计。

具体的排序方式可分为两种：从最低有效数位开始 (LSD, least significant digit) 和从最高有效数位开始 (MSD, most significant digit) 。

举例来说，假设待排序集合 S=[42, 19, 518, 1]，最大值的最高数位为百位。那么 LSD 将按个位、十位、百位的顺序执行，而 MSD 则会按百位、十位、个位的顺序执行。数位不足的 key 则以 0 进行填充至最大数位，如 42 和 1 分别被填充为 042 和 001。

算法的稳定性对于其他排序算法来说只是一种特性，是既不充分也不必要的条件，即算法是否稳定与算法是否正确并没有联系。但对于基数排序的 LSD 实现来说，每一轮排序的稳定性非常重要，能够保证上一轮的排序顺序有效，是 LSD 实现正确性的必要前提（而 MSD 则没有保持稳定的要求）。

应该明确的是，基数排序是一种思路，因此可以有各种不同的实现。为了便于理解，本文的后续部分以十进制整数进行讲解，但实际上只要是可将单个 key 以某种方式划分为不同数位的集合，都可以用基数排序来进行处理。如字符串可按 char 划分，对于长度较短的字符串可用 空字符 在之前或之后填充。而对于整数，既可以按十进制的方式拆分（如 518 拆分为 5-1-8），也可以按二进制的方式进行拆分（如 5 的二进制 0101 可拆分为 0-1-0-1），甚至能按八进制（3 bits）和十六进制（4 bits）进行数位的划分。

另外，由于负数的特殊性，使用基数排序处理负数部分需要额外的逻辑，但思路是一致的，因此本文的待排序集合均为正整数，不考虑负数的情况。

2.过程演示

LSD

假设待排序集合为 [171, 035, 072, 088, 002, 620, 002, 285]。

首先按最低位排序，即 1, 5, 2, 8, 2, 0, 2, 5，结果为：

1
620, 171, 072, 002, 002, 035, 285, 088

基于以上结果，再按十位进行排序，即 2, 7, 7, 0, 0, 3, 8, 8，结果为：

1
002, 002, 620, 035, 171, 072, 285, 088

最后基于以上结果，按百位进行排序，即 0, 0, 6, 0, 1, 0, 2, 0，结果为：

1
002, 002, 035, 072, 088, 171, 285, 620

MSD

以 MSD 方式排序时，对低位的排序范围必须基于上一位的重复部分。

假设待排序集合为 [183, 35, 272, 88, 2, 620, 1, 106]。

首先按最高位排序，即 1, 0, 2, 0, 0, 6, 0, 1，结果为：

1
{035, 088, 002, 001}, {183, 106}, {272}, {620}

（对百位中重复的部分用花括号进行划分）

基于重复的部分，对低一位（十位）进行排序，即 3, 8, 0, 0 和 8, 0，忽略没有重复的部分，结果为：

1
{002, 001}, 035, 088, 106, 183, 272, 620

同理，最后对十位中重复的部分进行排序：

1
001, 002, 035, 088, 106, 183, 272, 620

3.正确性分析

设 key 的有效数位为 w (width)，如 key=272，则 w=3. 以 LSD 排序方式为例，可以分为两种情况：

  1. 当 w 为 1。
  2. 当 w 大于 1，可进一步划分两种情况:
    1. 较高数位的值相同
    2. 较高数位的值不同

对于情况1，算法退化为只有 key 均为个位数的计数排序，因此正确。

对于情况2，不失一般性，设两个十位数 XA 和 YB （X/Y/A/B 均为任意的 0-9 之间的数字），

对于2.1 X!=Y 的情况，对这两个 digit 排序的结果无需考虑较小数位 A 和 B 的具体值。如 10+ 必然小于 20+，或 60+ 必然大于 50+。

对于2.2 X==Y 的情况，由于较低位已被排序，A 和 B 之间有序（即 A<=B），同时由于 LSD 为稳定排序，因此保证了 X 和 Y 的相对位置不变，排序正确。

举例来说，对 [22, 23] 按十位数进行排序时，由于是稳定排序，因此就算不考虑个位数的具体值，排序结果也必然是 [22, 23] 而不会出现 [23, 22] 的情况，因此对较高位进行排序不会影响较低位的结果。

从较低位向较高位排序的过程中，如果较高位之间的值不同，则可忽略较低位的顺序。而如果较高位之间相同，由于相对位置不变且较低位已然有序，因此排序结果具有不变性且终止于最高位的排序，达到整体有序。

与 LSD 相似，MSD 也是分为较高数位之间相同和不同的两种情况。当较高位之间的值不同时，则无需考虑较低位的具体值。当较高位之间的值相同时，则需要对该部分 key 进行较低位的排序。因此 MSD 方式对每个数位的排序并不要求稳定。

4.复杂度

设集合中元素个数为 n, 当中最大值的数位为 w:

  • 时间复杂度：每次遍历 n 个 key, 共遍历 w 次，因此时间复杂度为 Θ(w·n)
  • 空间复杂度：需要基数容器（大小为 b）和存放排序结果（大小为 n）共两个辅助空间，因此空间复杂度为O(b+n)。如按十位划分整数 key，则 b=10; 按 ASCII 字符划分字符串 key, 则 b=2⁷=128，以此类推。

5.代码实现

LSD: 十进制整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public void lsd(int[] nums) {
    int max = nums[0];
    for (int n : nums) {
        if (n > max) {
            max = n;
        }
    }
    int width = String.valueOf(max).length(); // 最大值的位数
    int inputSize = nums.length, binSize = 10; // 集合的数量和 bin size
    int[] bins = new int[binSize]; // 每一轮记录基数个数的容器
    int[] tmp = new int[inputSize]; // 排序结果辅助空间
    int radix = 1;
    
    int i, digit, value;
    for (int j = 0; j < width; j++) { // 算法主体遍历 width 次
        for (i = 0; i < binSize; i++) {
            bins[i] = 0; // 清空上一轮的统计信息
        }
        
        for (i = 0; i < inputSize; i++) {
            value = nums[i];
            digit = (value / radix) % 10; // 求出当前数位 (digit) 的值
            bins[digit]++;
        }
        
        for (i = 1; i < binSize; i++) {
            bins[i] += bins[i - 1]; // 计算积分用于判断 key 的相对位置
        }
        
        for (i = inputSize - 1; i >= 0; i--) { // 反向填充保持稳定性
            value = nums[i];
            digit = (value / radix) % 10;
            tmp[--bins[digit]] = value;
        }
        
        for (i = 0; i < inputSize; i++) { // 排序结果移回原数组
            nums[i] = tmp[i];
        }
        radix *= 10; // 基数向高位移动
    }
}

MSD: 十进制整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public void msd(int[] nums) {
    int max = nums[0];
    for (int n : nums) {
        if (n > max) {
            max = n;
        }
    }
    int width = String.valueOf(max).length();
    int radix = (int) Math.pow(10, width - 1);
    msdInner(nums, radix, 0, nums.length - 1);
}

/**
 * MSD 排序内部实现，对 {@code nums} 中索引为 {@code left} 至 {@code right} 范围进行排序
 * @param nums 待排序集合
 * @param radix 本轮排序的基数
 * @param left 排序范围左侧索引值（含该值）
 * @param right 排序范围右侧索引值（含该值）
 */
private void msdInner(int[] nums, int radix, int left, int right) {
    int maxIndex = nums.length - 1;
    if (left > maxIndex || right > maxIndex) {
        return;
    }
    
    int binSize = 10;
    int[] bins = new int[binSize]; // 基数统计容器
    int[] sum = new int[binSize]; // 用于记录积分结果
    int[] tmp = new int[right - left + 1]; // 排序结果辅助空间
    
    int i, digit, value;
    for (i = left; i <= right; i++) {
        value = nums[i];
        digit = (value / radix) % 10;
        bins[digit]++;
    }
    
    for (i = 0; i < binSize; i++) {
        sum[i] = bins[i];
        if (i > 0) {
            sum[i] += sum[i - 1]; // 计算积分用于判断 key 的相对位置
        }
    }
    
    for (i = right; i >= left; i--) {
        value = nums[i];
        digit = (value / radix) % 10;
        tmp[--sum[digit]] = value;
    }
    
    for (i = left; i <= right; i++) {
        nums[i] = tmp[i - left];
    }
    
    if (radix == 1) { // 已达最低位，无需后续处理
        return;
    }

    // 对 bins 相同的部分，计算其边界并进行较低位的排序
    int num;
    for (i = 0; i < binSize; i++) {
        num = bins[i];
        if (num > 1) {
            right = left + num - 1;
            msdInner(nums, radix / 10, left, right);
        }
        left += num;
    }
}

MSD 与之前 LSD 的实现的主要区别是不能直接在 bins 数组中计算积分，而是将积分结果记录在另一个数组中。bins 中存在相同 key 时对该部分递归排序。

MSD 变种：二进制原地排序

在英文维基中提到的原地 MSD 排序实现（大意）：

二进制 MSD 基数排序，也被称为二进制快排 (binary quicksort)。具体实现为：

将输入数组的 key 归入两个逻辑上的容器：0 bin 和 1 bin;

0 bin 从数组第一个元素开始，则其左侧为 0 集合的边界，该部分向右扩展。

1 bin 从数组最后的开始，其右侧为 1 集合的边界，该部分向左扩展。

排序过程中，对每个 key 的 digit 进行判断：digit 为 1 则将该 key 移动到 1 bin 边界位置，并使 1 bin 的边界左移 1 位；digit 为 0 则将 0 bin 边界往右移 1 位；循环至 0 bin 和 1 bin 边界重合时，即完成一轮判断。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * MSD 原地二进制排序
 * 
 * @param nums 待排序数组
 */
public void msdBinaryInplace(int[] nums) {
    int radix = 1 << 30; // signed interger 的最高位
    inplace(nums, radix, 0, nums.length - 1);
}

/**
 * 原地排序内部实现，对 {@code nums} 的 {@code left} 至 {@code right} 范围进行排序
 * 
 * @param nums
 * @param radix 本轮排序的基数
 * @param left 待排序区间左侧（含该值）
 * @param right 待排序区间右侧（含该值）
 */
private void inplace(int[] nums, int radix, int left, int right) {
    if (radix == 0 || left >= right) {
        return;
    }
    
    int i = left, j = right;
    int value;
    while (i < j) {
        value = nums[i];
        if ((value & radix) == 0) { // 当前位为 0，0 bin 边界往右移
            i++;
        } else {
            swap(nums, i, j); // 当前为 1，交换后 1 bin 边界往左移（注意此时 i 值不变，下一轮仍从 i 开始）
            j--;
        }
    } // ends at: i == j
    
    boolean flag = (nums[i] & radix) == 0; // 注①
    int bound = flag ? i : i - 1;
    
    radix >>= 1;
    inplace(nums, radix, left, bound);
    inplace(nums, radix, bound + 1, right);
}

注①:

每一轮排序会中止于 i == j，此时存在两种可能性：digit(i)=0 或 digit(i)=1。

由于每一轮排序最终会划分出 0 bin 和 1 bin ，并各自进行下一轮排序。设 bound 为 0 bin 的右界，那么 bound + 1 为 1 bin 的左界。因此当 digit(i)=0 时，bound = i; 当 digit(i)=1 时，bound = i - 1.