基数排序是一种非比较型整数排序算法，其基本思想是将整数按位数切分，然后按每个位数分别排序。基数排序可以分为 LSD（Least Significant Digit，最低位优先）和 MSD（Most Significant Digit，最高位优先）两种方法。
以下是 Java 实现的基数排序（LSD 方法）的代码示例和注释。
import java.util.Arrays; public class RadixSort { // 主排序函数 public static void radixSort(int[] arr) { // 获取数组中的最大值，以确定最大位数 int max = Arrays.stream(arr).max().getAsInt(); // 从个位开始，对数组进行计数排序 for (int exp = 1; max / exp > 0; exp *= 10) { countingSortByDigit(arr, exp); } } // 按位数进行计数排序的辅助函数 private static void countingSortByDigit(int[] arr, int exp) { int n = arr.length; int[] output = new int[n]; // 输出数组 int[] count = new int[10]; // 计数数组，范围为 0-9 // 初始化计数数组为 0 Arrays.fill(count, 0); // 统计每个桶中的元素个数 for (int i = 0; i < n; i++) { count[(arr[i] / exp) % 10]++; } // 将计数数组转换为实际位置数组 for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } // 按当前位数将元素放入输出数组中 for (int i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // 将排序好的元素复制回原数组 System.arraycopy(output, 0, arr, 0, n); } // 测试函数 public static void main(String[] args) { int[] arr = {170, 45, 75, 90, 802, 24, 2, 66}; System.out.println("未排序数组: " + Arrays.toString(arr)); radixSort(arr); System.out.println("已排序数组: " + Arrays.toString(arr)); } }
上述代码实现了基数排序的 LSD 方法。以下是对代码的详细说明：
主排序函数 radixSort:
radixSort 函数首先通过 Arrays.stream(arr).max().getAsInt() 找到数组中的最大值，用于确定排序的最大位数。
通过 for 循环，从个位开始，每次排序按位数的增加（exp 从 1 到 10、100、1000 ...），调用 countingSortByDigit 函数对数组进行计数排序。
按位数进行计数排序的辅助函数 countingSortByDigit:
countingSortByDigit 函数首先初始化两个数组：output 用于存储排序后的结果，count 用于计数各个桶中的元素个数。
通过 for 循环，统计当前位数（由 exp 确定）的每个桶中的元素个数。
累加计数数组，将计数数组转换为实际位置数组。
通过倒序的 for 循环，按当前位数将元素放入输出数组中。
最后，将排序好的元素复制回原数组。
测试函数 main:
创建一个整数数组并输出未排序的数组。
调用 radixSort 函数对数组进行排序，并输出已排序的数组。
以下是另一种基数排序（MSD 方法）的代码示例和注释。
import java.util.Arrays; public class MSDRadixSort { // 主排序函数 public static void radixSort(int[] arr) { radixSort(arr, 0, arr.length - 1, getMaxDigit(arr)); } // 递归排序函数 private static void radixSort(int[] arr, int left, int right, int digit) { if (left >= right || digit < 0) { return; } // 基数桶数组 int[] buckets = new int[10]; int[] temp = new int[right - left + 1]; // 统计各个桶的个数 for (int i = left; i <= right; i++) { int bucketIndex = (arr[i] / digit) % 10; buckets[bucketIndex]++; } // 转换为各个桶的起始位置 for (int i = 1; i < 10; i++) { buckets[i] += buckets[i - 1]; } // 逆序放置元素到临时数组中 for (int i = right; i >= left; i--) { int bucketIndex = (arr[i] / digit) % 10; temp[--buckets[bucketIndex]] = arr[i]; } // 将临时数组复制回原数组 System.arraycopy(temp, 0, arr, left, temp.length); // 对每个桶进行递归排序 int start = left; for (int i = 0; i < 10; i++) { int end = (i == 9) ? right : left + buckets[i] - 1; radixSort(arr, start, end, digit / 10); start = end + 1; } } // 获取数组中最大值的位数 private static int getMaxDigit(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); int digit = 1; while (max / digit >= 10) { digit *= 10; } return digit; } // 测试函数 public static void main(String[] args) { int[] arr = {170, 45, 75, 90, 802, 24, 2, 66}; System.out.println("未排序数组: " + Arrays.toString(arr)); radixSort(arr); System.out.println("已排序数组: " + Arrays.toString(arr)); } }
上述代码实现了基数排序的 MSD 方法。以下是对代码的详细说明：
主排序函数 radixSort:
radixSort 函数首先调用 getMaxDigit 函数获取数组中最大值的位数。
调用递归函数 radixSort，从最大位数开始进行排序。
递归排序函数 radixSort:
递归函数 radixSort 用于对指定范围的数组进行排序，参数包括数组、左右边界和当前处理的位数。
递归终止条件为左右边界相交或当前位数小于 0。
初始化基数桶数组 buckets 和临时数组 temp。
统计当前位数的各个桶的个数，并转换为各个桶的起始位置。
逆序放置元素到临时数组中，并将临时数组复制回原数组。
对每个桶进行递归排序。
获取数组中最大值的位数 getMaxDigit:
getMaxDigit 函数用于获取数组中最大值的位数。
通过 while 循环，不断将最大值除以 10，直到小于 10 为止。
测试函数 main:
创建一个整数数组并输出未排序的数组。
调用 radixSort 函数对数组进行排序，并输出已排序的数组。
通过以上两个基数排序的实现示例，我们可以看到，基数排序的核心思想是利用计数排序对每个位数进行排序，从而达到整体排序的目的。LSD 方法从低位开始排序，而 MSD 方法从高位开始排序，具体选择哪种方法取决于实际应用场景和需求。
