Java排序算法之基数排序

基数排序（Radix Sort）是一种线性时间复杂度的排序算法，其时间复杂度为O(d(n+k))，其中d是数字的位数，k是进制数。基数排序是一种非比较排序算法，它按照数位的大小来进行排序。它可以处理正整数、负整数和小数。

基数排序的实现过程如下：

1. 找到最大数，并确定最大数的位数。

2. 从个位数开始，把所有数按照该位数进行排序。可以使用计数排序或桶排序。排序后，原数组变成了按照该位数排序后的数组。

3. 重复第二步，直到最大数的最高位被处理完。

举个例子：

假设有以下六个数字要排序：23，46，12，67，34，89。我们先找到最大数89，确定最大数的位数为2。

第一轮排序按照个位数排序：

个位数	桶1	桶2	桶3	桶4	桶5	桶6	桶7	桶8	桶9
3			23	34		46	67		89
2	12
6

第二轮排序按照十位数排序：

十位数	桶1	桶2	桶3	桶4	桶5	桶6	桶7	桶8	桶9
3				12	23	34		46	67
8									89

最终排序结果为：12，23，34，46，67，89。

Java实现基数排序的核心思想是：将数字按照每个位数分别排序，从低位到高位依次进行排序，最后得到有序序列。

下面是Java实现基数排序的代码：

public class RadixSort {/*** 基数排序* @param arr 待排序数组*/public static void radixSort(int[] arr) {if (arr == null || arr.length == 0) return;int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) max = arr[i]; // 找到最大值}int radix = 10; // 进制数，这里是10进制int exp = 1; // 指数int[] aux = new int[arr.length]; // 临时数组while (max / exp > 0) { // 从个位开始，对每一位进行排序int[] buckets = new int[radix];// 统计每个桶中的记录数for (int i = 0; i < arr.length; i++) {int bucketIndex = (arr[i] / exp) % radix;buckets[bucketIndex]++;}// 将各个桶中的数字个数，转化成各个桶中最后一个数字的索引位置for (int i = 1; i < radix; i++) {buckets[i] += buckets[i - 1];}// 将原数组中的元素放入临时数组中，根据桶中位置排序for (int i = arr.length - 1; i >= 0; i--) {int bucketIndex = (arr[i] / exp) % radix;aux[--buckets[bucketIndex]] = arr[i];}// 将有序的数组写回原数组for (int i = 0; i < arr.length; i++) {arr[i] = aux[i];}exp *= radix;}}public static void main(String[] args) {int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };radixSort(arr);System.out.println(Arrays.toString(arr)); // [2, 24, 45, 66, 75, 90, 170, 802]}
}