实现基数排序（Radix Sort）及其应用场景

基数排序是一种非比较型的整数排序算法，它通过逐位处理数字的每一位来实现排序。本文将详细讲解基数排序的工作原理、具体实现步骤、复杂度分析以及适用场景。

基数排序的基本思想

基数排序的核心思想是：将整数按位数切割成不同的数字，然后按每个位数分别进行比较排序。排序过程中，从最低有效位（LSB）到最高有效位（MSB）依次进行排序，每次排序都使用稳定的排序算法（通常是计数排序）来处理当前位。

算法步骤详解

1. 确定最大数字的位数：

   • 遍历数组，找到绝对值最大的数字（若包含负数需特殊处理）。
   • 计算该数字的位数（例如，数字123的位数为3）。

2. 从最低位到最高位逐位排序：

   • 使用稳定的排序算法（如计数排序）对当前位进行排序。
   • 重复此过程，直到处理完最高位。

3. 处理负数（如果存在）：

   • 若数组包含负数，需先分离正负数，分别排序后合并，或使用偏移量将负数映射到正数范围。

具体实现（以非负整数为例）

假设数组为 [170, 45, 75, 90, 2, 802, 24, 66]，最大数字802的位数为3。

步骤1：按个位排序

• 使用计数排序对个位数字（0-9）排序：
  • 个位分布：0(170,90)、2(802,2)、4(24)、5(45,75)、6(66)
  • 排序后数组：[170, 90, 802, 2, 24, 45, 75, 66]

步骤2：按十位排序

• 对十位数字排序（不足十位补0）：
  • 十位分布：0(802,2)、2(24)、4(45)、6(66)、7(170,75)、9(90)
  • 排序后数组：[802, 2, 24, 45, 66, 170, 75, 90]

步骤3：按百位排序

• 对百位数字排序：
  • 百位分布：0(2,24,45,66,75,90)、1(170)、8(802)
  • 排序后数组：[2, 24, 45, 66, 75, 90, 170, 802]

此时数组已完全有序。

代码实现（Java）

public class RadixSort {
    // 获取数组中最大数字的位数
    private static int getMaxDigits(int[] arr) {
        int max = Math.abs(arr[0]);
        for (int num : arr) {
            max = Math.max(max, Math.abs(num));
        }
        return String.valueOf(max).length();
    }

    // 基数排序主函数
    public static void radixSort(int[] arr) {
        int maxDigits = getMaxDigits(arr);
        int exp = 1; // 从个位开始

        for (int i = 0; i < maxDigits; i++) {
            countingSortByDigit(arr, exp);
            exp *= 10;
        }
    }

    // 根据当前位进行计数排序
    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10]; // 0-9的计数器

        // 统计当前位各数字出现次数
        for (int num : arr) {
            int digit = (num / exp) % 10;
            count[digit]++;
        }

        // 计算累计次数
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 从后向前遍历，保证稳定性
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // 将排序结果复制回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }
}

复杂度分析

• 时间复杂度：O(d*(n+k))，其中d为最大位数，n为元素个数，k为基数（十进制中k=10）。当d为常数时，复杂度为O(n)。
• 空间复杂度：O(n+k)，需要额外空间用于计数和输出数组。

应用场景与限制

适用场景：

1. 整数排序，尤其是位数较小的整数（如手机号、身份证号排序）。
2. 数据范围已知且分布均匀的情况。
3. 需要稳定排序且非比较排序的场景。

局限性：

1. 不适用于浮点数或字符串排序（需特殊处理）。
2. 当最大位数d很大时，效率可能低于快速排序。
3. 对负数需额外处理（如增加偏移量）。

总结

基数排序通过逐位排序的方式，避免了比较操作，在特定场景下效率显著。理解其稳定排序的关键和位数处理逻辑，是掌握该算法的核心。实际应用中需结合数据特性选择是否使用基数排序。