Java排序算法之基数排序
基数排序（Radix Sort）是一种线性时间复杂度的排序算法，其时间复杂度为O(d(n+k))，其中d是数字的位数，k是进制数。基数排序是一种非比较排序算法，它按照数位的大小来进行排序。它可以处理正整数、负整数和小数。
基数排序的实现过程如下：
-
找到最大数，并确定最大数的位数。
-
从个位数开始，把所有数按照该位数进行排序。可以使用计数排序或桶排序。排序后，原数组变成了按照该位数排序后的数组。
-
重复第二步，直到最大数的最高位被处理完。
举个例子：
假设有以下六个数字要排序：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]}
}