Java 基数排序

基数排序（Radix Sort）是一种非比较型整数排序算法，通常用于对数字进行排序。它按照数字的每一位（从最低有效位到最高有效位或从最高有效位到最低有效位）进行排序，每次使用一个稳定的排序算法（如计数排序或桶排序）对相应位进行排序。

以下是基数排序的一个基本实现，这里我们使用计数排序作为子排序算法，并假设我们要排序的是非负整数：

import java.util.Arrays;  public class RadixSort {  // 获取数组中最大值  private static int getMax(int[] array) {  int max = array[0];  for (int num : array) {  if (num > max) {  max = num;  }  }  return max;  }  // 计数排序，用于对指定位的数字进行排序  private static void countingSort(int[] array, int exp) {  int n = array.length;  int[] output = new int[n]; // 输出数组  int[] count = new int[10]; // 假设数字在0到9之间  Arrays.fill(count, 0);  // 统计每个桶中的数字个数  for (int i = 0; i < n; i++) {  count[(array[i] / exp) % 10]++;  }  // 修改count数组，使其包含位置信息  for (int i = 1; i < 10; i++) {  count[i] += count[i - 1];  }  // 构建输出数组  for (int i = n - 1; i >= 0; i--) {  output[count[(array[i] / exp) % 10] - 1] = array[i];  count[(array[i] / exp) % 10]--;  }  // 将排序结果复制回原数组  System.arraycopy(output, 0, array, 0, n);  }  // 基数排序主函数  public static void radixSort(int[] array) {  // 找到最大数，确定最大位数  int max = getMax(array);  // 从个位开始，对每一位进行计数排序  for (int exp = 1; max / exp > 0; exp *= 10) {  countingSort(array, exp);  }  }  public static void main(String[] args) {  int[] array = {170, 45, 75, 90, 802, 24, 2, 66};  System.out.println("排序前: " + Arrays.toString(array));  radixSort(array);  System.out.println("排序后: " + Arrays.toString(array));  }  
}

代码说明：

1. getMax函数：找到数组中的最大值，用于确定最大位数。
2. countingSort函数：实现计数排序，对数组按指定的位数（由参数exp决定）进行排序。exp是10的幂次，表示当前排序的位数（个位、十位、百位等）。
3. radixSort函数：基数排序的主函数，从个位开始，依次对每一位进行计数排序。
4. main函数：测试基数排序算法。

运行结果：

排序前: [170, 45, 75, 90, 802, 24, 2, 66]  
排序后: [2, 24, 45, 66, 75, 90, 170, 802]

基数排序的时间复杂度为O(d * (n + k))，其中d是数字的最大位数，n是数组的长度，k是计数排序的桶的数量（对于十进制数，k通常为10）。这使得基数排序在处理大量数字时非常高效，尤其是当数字位数较大时。