基数排序

基本原理

基数排序是一种非比较性的排序算法。基数排序的基本思想是：将整数按位数划分为不同的桶，然后按每个位数分别对桶中的元素进行排序，最终将所有位数上的排序结果合并在一起，得到最终的排序结果。

基数排序的时间复杂度为O(dn)，其中d是数字的最大位数，n是待排序元素个数。

实现步骤

基数排序的实现步骤如下：

1. 获取待排序数组中的最大值，确定最大位数d。
2. 对最末位进行排序，使用计数排序算法对每个数字出现的次数进行统计。
3. 基于计数排序的结果，依次确定每个数字在有序数组中的位置。
4. 将有序数组重新赋值给原数组。
5. 依次对每一位进行排序，直到最高位。

public class radixSort {
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 获取最大值的位数
        int maxNum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxNum) {
                maxNum = arr[i];
            }
        }

        int placeValue = 1;  // 当前位的权值
        while (maxNum / placeValue > 0) {
            countingSort(arr, placeValue);
            placeValue *= 10;
        }
    }

    private static void countingSort(int[] arr, int placeValue) {
        int[] count = new int[10];
        int radix = 10;

        for (int i = 0; i < arr.length; i++) {
            int digit = (arr[i] / radix) % 10;
            count[digit]++;
        }

        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        int[] output = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int digit = (arr[i] / radix) % 10;
            int index = count[digit] - 1;
            output[index] = arr[i];
            count[digit]--;
        }

        System.arraycopy(output, 0, arr, 0, arr.length);
    }
}