Java 中的基数排序（Radix Sort）

1. 简介

本文将深入讲解基数排序（Radix Sort）算法，分析其性能表现，并给出 Java 实现。

✅ 核心要点：

基数排序是一种非比较型排序算法，不通过元素间直接比较来排序。
它适用于整数排序，但也可扩展用于字符串等类型（按字符位排序）。
本文以十进制系统（radix = 10）为例进行讲解，便于理解。

⚠️ 虽然名字叫“基数”，但它和“进制”密切相关。我们处理的是每一位上的数字，从个位、十位到百位，逐位排序。

2. 算法原理

基数排序的核心思想是：按位排序，从低位到高位（LSD 方式）或从高位到低位（MSD 方式）。我们这里采用最常见的 LSD（Least Significant Digit）方式。

与其他主流排序算法如 Merge Sort、Insertion Sort、Bubble Sort 不同，它完全避开了“比较”操作，因此在特定场景下性能更优。

关键依赖：稳定排序子程序

基数排序本身不直接排序，而是依赖一个稳定的排序算法作为子程序，对每一位上的数字进行排序。我们通常选择计数排序（Counting Sort）作为这个子程序，原因如下：

✅ 计数排序是稳定的 —— 相同值的元素相对顺序不变
✅ 对小范围整数（比如 0~9）效率极高，正好适合处理每一位的数字

3. 一个直观的例子

假设我们有如下数组需要排序：

目标是将其从小到大排序。我们从个位数开始，逐位向高位推进。

3.1 第一轮：按个位排序

提取每个数的个位数字：

使用稳定排序（如计数排序）按个位排序后，结果为：

✅ 注意：7 的个位是 7，37 的个位也是 7，但由于 7 原本在 37 前面，排序后仍保持在前 —— 这就是“稳定性”的体现。

3.2 第二轮：按十位排序

现在看十位数字（没有十位的视为 0）：

排序后结果：

⚠️ 注意：7 的十位是 0，所以它排到了最前面。其他数按十位大小排列。

3.3 第三轮：按百位排序

最后处理百位：

排序后：

✅ 此时数组已完全有序，算法结束。

4. Java 实现

主流程：逐位调用计数排序

void sort(int[] numbers) {
    int maximumNumber = findMaximumNumberIn(numbers);
    int numberOfDigits = calculateNumberOfDigitsIn(maximumNumber);
    int placeValue = 1; // 从个位开始 (1, 10, 100, ...)
    
    while (numberOfDigits-- > 0) {
        applyCountingSortOn(numbers, placeValue);
        placeValue *= 10; // 移动到下一位
    }
}

📌 说明：

findMaximumNumberIn() 找出最大值，确定要处理多少位
calculateNumberOfDigitsIn() 计算最大值的位数
placeValue 控制当前处理的是哪一位（个位、十位等）

子程序：基于位值的计数排序

void applyCountingSortOn(int[] numbers, int placeValue) {
    int range = 10; // 十进制，0~9
    int length = numbers.length;
    int[] frequency = new int[range];
    int[] sortedValues = new int[length];

    // 1. 统计当前位上各数字的频次
    for (int i = 0; i < length; i++) {
        int digit = (numbers[i] / placeValue) % range;
        frequency[digit]++;
    }

    // 2. 构建前缀和，确定每个数字的最终位置
    for (int i = 1; i < range; i++) {
        frequency[i] += frequency[i - 1];
    }

    // 3. 从后往前遍历原数组，保证稳定性
    for (int i = length - 1; i >= 0; i--) {
        int digit = (numbers[i] / placeValue) % range;
        sortedValues[frequency[digit] - 1] = numbers[i];
        frequency[digit]--;
    }

    // 4. 将排序结果拷贝回原数组
    System.arraycopy(sortedValues, 0, numbers, 0, length);
}

📌 关键细节：

(numbers[i] / placeValue) % 10 是提取某一位数字的经典写法
从后往前遍历是为了保持稳定性（相同位值的元素，原序靠后的排在后面）
frequency 数组用作“位置指针”，通过前缀和确定每个数字应放的位置

测试用例

@Test
void givenUnsortedArray_whenRadixSort_thenArraySorted() {
    int[] numbers = {387, 468, 134, 123, 68, 221, 769, 37, 7};
    RadixSort.sort(numbers);
    int[] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769};
    assertArrayEquals(numbersSorted, numbers); 
}

✅ 测试通过，说明实现正确。

5. 基数排序 vs 计数排序

虽然都用了“计数”的思想，但两者有本质区别：

对比项	计数排序（Counting Sort）	基数排序（Radix Sort）
频次数组长度	`maxValue + 1`	固定为 `radix`（如 10）
适用场景	数值范围小且密集	数值大但位数不多
是否分“桶”	❌ 直接按数值映射	✅ 按每一位分桶（0~9）
空间开销	可能很大（如最大值是 10^6）	很小（仅 10 个桶）

📌 一句话总结：
计数排序怕“最大值太大”，基数排序怕“位数太多”。如果你的数组里有 1, 2, 1000000，用计数排序会浪费大量空间；而用基数排序，只需多跑几轮即可。

6. 时间与空间复杂度

时间复杂度：O(d × (n + b))

n：数组长度
d：最大数的位数（如 769 是 3 位）
b：基数（base），十进制下为 10

每一轮调用一次计数排序，耗时 O(n + b)，共 d 轮。

✅ 当 d 是常数时（比如固定 32 位整数），时间复杂度可视为 **O(n)**，优于基于比较的 O(n log n) 排序。

空间复杂度：O(n + b)

n：辅助数组 sortedValues
b：频次数组 frequency

⚠️ 虽然是线性空间，但需要额外数组，不能原地排序。

7. 总结

基数排序是一种在特定场景下非常高效的排序算法：

✅ 优势：

非比较型，理论可达 O(n)
适合位数固定的大整数排序
实现简单，逻辑清晰

❌ 局限：

只适用于可按位分解的数据（整数、字符串）
需要稳定排序子程序支持
位数多时性能下降

📌 适用场景举例：

排序 IP 地址（每段 0~255）
排序电话号码
固定长度的 ID 或编号

项目源码已托管至 GitHub：https://github.com/dev-example/algorithms/tree/main/sorting-radix

Persistence

REST

Security