嘉兴高端网站外贸网站空间选择
基数排序（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)); }
}代码说明：
- getMax函数：找到数组中的最大值，用于确定最大位数。
- countingSort函数：实现计数排序，对数组按指定的位数（由参数exp决定）进行排序。exp是10的幂次，表示当前排序的位数（个位、十位、百位等）。
- radixSort函数：基数排序的主函数，从个位开始，依次对每一位进行计数排序。
- 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）。这使得基数排序在处理大量数字时非常高效，尤其是当数字位数较大时。