Java基数排序详解（从零开始掌握非比较排序算法）

基数排序的基本步骤

1. 找出数组中的最大值，确定最大位数。
2. 从个位开始，对每一位进行“计数排序”（或其他稳定排序）。
3. 重复上述过程，直到处理完最高位。

Java 实现基数排序

下面是一个完整的 Java 基数排序实现代码：

public class RadixSort {    // 基数排序主方法    public static void radixSort(int[] arr) {        if (arr == null || arr.length <= 1) {            return;        }        // 找到最大值以确定最大位数        int max = getMax(arr);        // 对每一位进行计数排序        for (int exp = 1; max / exp > 0; exp *= 10) {            countingSortByDigit(arr, exp);        }    }    // 获取数组中的最大值    private static int getMax(int[] arr) {        int max = arr[0];        for (int i = 1; i < arr.length; i++) {            if (arr[i] > max) {                max = arr[i];            }        }        return max;    }    // 按指定位（exp 表示 1, 10, 100...）进行计数排序    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 i = 0; i < n; i++) {            int digit = (arr[i] / exp) % 10;            count[digit]++;        }        // 将 count 转换为累积计数（用于确定位置）        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);    }    // 测试方法    public static void main(String[] args) {        int[] arr = {170, 45, 75, 90, 2, 802, 24, 66};        System.out.println("排序前: " + java.util.Arrays.toString(arr));        radixSort(arr);        System.out.println("排序后: " + java.util.Arrays.toString(arr));    }}  

代码说明

• getMax()：用于找出数组最大值，从而知道需要处理多少位。
• countingSortByDigit()：对某一位（如个位、十位）执行计数排序，这是基数排序的核心子过程。
• 使用 exp（1, 10, 100…）来提取对应位上的数字。
• 整个算法是稳定的，因为计数排序是稳定的。

时间与空间复杂度

假设数组长度为 n，最大数有 d 位，每位的基数为 k（通常 k=10）：

• 时间复杂度：O(d × (n + k))，当 d 较小时，接近线性时间 O(n)。
• 空间复杂度：O(n + k)，需要额外的输出数组和计数数组。

适用场景

Java基数排序特别适合以下情况：

• 数据是整数或定长字符串。
• 数值范围不是特别大（避免位数过多）。
• 需要稳定且高效的线性排序。

总结

通过本篇Java排序教程，你已经掌握了基数排序算法的基本原理与 Java 实现。作为典型的非比较排序Java方法，基数排序在特定场景下性能优越。建议你在理解的基础上多动手练习，尝试修改代码以支持负数或字符串排序，进一步巩固所学知识！