每日算法 — 使用java实现基数排序：计数排序基础与线性时间非比较排序

在排序算法的世界里，比较排序（如快速排序、归并排序）存在一个理论下限：任何基于比较的排序算法在最坏情况下都需要至少 O(n log n) 次比较。然而，当我们不再局限于”两两比较”的范式，而是利用数据的内部结构（如各位数字）时，便有机会突破这一界限。基数排序正是这样一种非比较排序算法，它通过按位分发将时间复杂度降低到 O(n) 级别。本文将用Java完整实现计数排序与基数排序，深入讲解稳定排序的关键作用。

一、计数排序：基数排序的基石

计数排序假设待排序的元素均为范围在 0 到 k 之间的整数。其核心思想是：对于每个元素 x，统计小于 x 的元素个数，从而直接确定 x 在输出数组中的位置。

1.1 算法步骤

统计频次：遍历输入数组，统计每个值出现的次数，存入计数数组 count。
累积计数：将 count 转换为累积计数数组，使得 count[i] 表示小于等于 i 的元素总数。
构建输出：从后向前遍历输入数组（保证稳定性），根据累积计数将元素放入输出数组的正确位置。

1.2 为什么需要稳定？

稳定性是指：若两个元素值相等，排序后它们的相对顺序与输入时一致。基数排序要求每一位的排序必须是稳定的，否则高位的排序结果会被低位的无序排序破坏。

1.3 Java实现

import java.util.Arrays;

/**
 * 计数排序实现
 * 适用于非负整数，时间复杂度 O(n + k)，空间复杂度 O(n + k)
 * 其中 k 为数据范围最大值
 */
public class CountingSort {

    /**
     * 计数排序主方法
     * @param arr 待排序数组（元素为非负整数）
     * @param maxVal 数组中的最大值，用于确定计数数组大小
     * @return 排序后的新数组
     */
    public static int[] sort(int[] arr, int maxVal) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[maxVal + 1];

        // 步骤1：统计每个元素出现的频次
        for (int value : arr) {
            count[value]++;
        }

        // 步骤2：累积计数，count[i] 表示小于等于 i 的元素总数
        for (int i = 1; i <= maxVal; i++) {
            count[i] += count[i - 1];
        }

        // 步骤3：从后向前遍历，保证稳定性
        // 相等元素中，后出现的在输出数组中也靠后
        for (int i = n - 1; i >= 0; i--) {
            int value = arr[i];
            int pos = count[value] - 1;  // 该元素在输出数组中的最终位置
            output[pos] = value;
            count[value]--;              // 递减计数，为相同值的下一个元素留出位置
        }

        return output;
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        int maxVal = 8;
        int[] sorted = sort(arr, maxVal);
        System.out.println("原始数组: " + Arrays.toString(arr));
        System.out.println("计数排序: " + Arrays.toString(sorted));
        // 输出：[1, 2, 2, 3, 3, 4, 8]
    }
}

1.4 复杂度分析

指标	值	说明
时间复杂度	O(n + k)	n 为元素个数，k 为数据范围
空间复杂度	O(n + k)	输出数组 + 计数数组
稳定性	稳定	从后向前遍历保证相等元素相对顺序
适用条件	非负整数且范围不大	k 过大时空间开销剧增

二、基数排序：从按值排序到按位排序

计数排序的瓶颈在于数据范围 k。当 k 很大（如 32 位整数的最大值）时，计数数组将耗尽内存。基数排序的巧妙之处在于：它不对整个数值进行计数排序，而是对每一位分别进行稳定排序。

2.1 核心思想

以十进制为例，对于数组 [170, 45, 75, 90, 2, 802, 24, 66]：

按个位排序：[170, 90, 2, 802, 24, 45, 75, 66]
按十位排序（在个位已排好的基础上）：[2, 802, 24, 45, 66, 170, 75, 90]
按百位排序（在十位已排好的基础上）：[2, 24, 45, 66, 75, 90, 170, 802]

关键洞察：低位排序为高位排序提供了预处理信息。当按十位排序时，若两个数十位相同（如 75 和 74 的十位都是 7），由于排序是稳定的，个位较大的元素会排在后面，这正是我们期望的顺序。

2.2 为什么必须从最低位开始（LSD）？

LSD（Least Significant Digit）基数排序从个位开始逐步向高位推进。这保证了在处理第 i 位时，低 i-1 位已经是有序的。若从高位开始（MSD），则高位相同的子区间需要递归处理，实现更复杂。

2.3 Java实现

import java.util.Arrays;

/**
 * 基数排序实现（LSD - 最低位优先）
 * 基于计数排序对每一位进行稳定排序
 * 适用于非负整数
 */
public class RadixSort {

    // 基数，十进制则为10
    private static final int RADIX = 10;

    /**
     * 获取数字在指定位数上的值
     * @param num 数字
     * @param digitPos 位数位置（0=个位, 1=十位, 2=百位...）
     * @return 该位上的数字（0-9）
     */
    private static int getDigit(int num, int digitPos) {
        int divisor = (int) Math.pow(RADIX, digitPos);
        return (num / divisor) % RADIX;
    }

    /**
     * 获取数组中最大值的位数
     * @param arr 数组
     * @return 最大值的位数
     */
    private static int getMaxDigits(int[] arr) {
        int max = 0;
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        int digits = 0;
        while (max > 0) {
            digits++;
            max /= RADIX;
        }
        return Math.max(digits, 1);  // 至少1位，处理全0数组
    }

    /**
     * 对数组按照指定数位进行计数排序（稳定排序）
     * @param arr 输入数组
     * @param digitPos 要排序的数位位置
     */
    private static void countingSortByDigit(int[] arr, int digitPos) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[RADIX];  // 0-9 共10个桶

        // 步骤1：统计当前位上每个数字的出现频次
        for (int num : arr) {
            int digit = getDigit(num, digitPos);
            count[digit]++;
        }

        // 步骤2：累积计数
        for (int i = 1; i < RADIX; i++) {
            count[i] += count[i - 1];
        }

        // 步骤3：从后向前构建输出数组，保证稳定性
        for (int i = n - 1; i >= 0; i--) {
            int digit = getDigit(arr[i], digitPos);
            int pos = count[digit] - 1;
            output[pos] = arr[i];
            count[digit]--;
        }

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

    /**
     * 基数排序主方法
     * @param arr 待排序的非负整数数组
     */
    public static void sort(int[] arr) {
        int maxDigits = getMaxDigits(arr);

        // 从个位开始，逐位进行稳定的计数排序
        for (int digitPos = 0; digitPos < maxDigits; digitPos++) {
            countingSortByDigit(arr, digitPos);
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 2, 802, 24, 66};
        System.out.println("原始数组: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("基数排序: " + Arrays.toString(arr));
        // 输出：[2, 24, 45, 66, 75, 90, 170, 802]

        // 大规模测试
        System.out.println("\n=== 大规模测试 ===");
        int[] large = new int[100000];
        for (int i = 0; i < large.length; i++) {
            large[i] = (int) (Math.random() * 1000000);
        }
        int[] copy = large.clone();
        long start = System.currentTimeMillis();
        sort(large);
        long radixTime = System.currentTimeMillis() - start;

        start = System.currentTimeMillis();
        Arrays.sort(copy);
        long systemTime = System.currentTimeMillis() - start;

        System.out.println("数组大小: 100000");
        System.out.println("基数排序耗时: " + radixTime + " ms");
        System.out.println("系统排序耗时: " + systemTime + " ms");
        System.out.println("排序结果一致: " + Arrays.equals(large, copy));
    }
}

2.4 可视化追踪

以数组 [170, 45, 75, 90, 2, 802, 24, 66] 为例，追踪每一位排序后的状态：

初始状态：[170, 45, 75, 90, 2, 802, 24, 66]

按个位排序后：个位值分别为 [0, 5, 5, 0, 2, 2, 4, 6]

排序结果：[170, 90, 2, 802, 24, 45, 75, 66]

按十位排序后：十位值分别为 [7, 9, 0, 0, 2, 4, 7, 6]

排序结果：[2, 802, 24, 45, 66, 170, 75, 90]

注意此时 170 和 75 的十位都是 7，但由于排序是稳定的，170 出现在 75 之前（因为在个位排序时 170 就在 75 之前）。

按百位排序后：百位值分别为 [0, 8, 0, 0, 0, 1, 0, 0]

排序结果：[2, 24, 45, 66, 75, 90, 170, 802]

三、复杂度分析

指标	值	说明
时间复杂度	O(d × (n + k))	d 为最大位数，k 为基数（通常为10）
空间复杂度	O(n + k)	输出数组 + 计数数组
稳定性	稳定	基于稳定的计数排序
适用条件	非负整数或可映射为整数的键	需要稳定的子排序例程

当 d 为常数（如固定长度的整数）且 k 为常数（基数固定为10）时，基数排序的时间复杂度可视为 O(n)，即线性时间。

与比较排序的对比

算法	时间复杂度	空间复杂度	稳定性	是否比较排序
快速排序	O(n log n)	O(log n)	不稳定	是
归并排序	O(n log n)	O(n)	稳定	是
堆排序	O(n log n)	O(1)	不稳定	是
计数排序	O(n + k)	O(n + k)	稳定	否
基数排序	O(d(n + k))	O(n + k)	稳定	否

基数排序牺牲了一定的空间复杂度，换取了理论上更优的时间复杂度。在实际应用中，当数据范围不大且需要稳定排序时，基数排序是非常高效的选择。

四、扩展：负数的处理

上述实现仅支持非负整数。若要支持负数，可采用以下策略：

找出数组中的最小值 minVal。
将所有元素加上 |minVal|，使所有数变为非负。
执行基数排序。
将所有元素减去 |minVal| 恢复原始值。

/**
 * 支持负数的基数排序
 */
public static void sortWithNegatives(int[] arr) {
    int minVal = Integer.MAX_VALUE;
    int maxVal = Integer.MIN_VALUE;
    for (int num : arr) {
        if (num < minVal) minVal = num;
        if (num > maxVal) maxVal = num;
    }

    int offset = Math.abs(minVal);
    // 偏移使所有数非负
    for (int i = 0; i < arr.length; i++) {
        arr[i] += offset;
    }

    sort(arr);  // 使用非负版本的基数排序

    // 恢复原始值
    for (int i = 0; i < arr.length; i++) {
        arr[i] -= offset;
    }
}

五、总结

基数排序展示了算法设计中”分解问题、逐个击破”的智慧：

将复杂问题分解为简单子问题：把按整个数值排序，分解为按每一位排序。
利用稳定排序保持已有信息：低位的排序结果通过稳定性传递到高位排序中。
突破理论下限：通过改变问题假设（不再仅依赖比较），获得更优的时间复杂度。

计数排序与基数排序是理解”非比较排序”范式的最佳入口。掌握它们不仅能应对算法面试中的各类变形题，更能在实际工程中（如大规模整数排序、字符串按字典序排序等场景）做出更优的算法选择。

Tagged with: Java 基数排序排序算法计数排序