排序算法之基数排序(桶排序)JAVA

排序过程
按从低位到高位的顺序对数组中的每个元素排序
例如： 12 , 3 , 21 , 56 , 84
第一轮排序：21 , 12 , 3 , 84 , 56
第二轮排序：3 , 12 , 21 , 56 , 84
简言之就是，从低位到高位，从小到大

排序的各项指标
平均时间复杂度：O(NM)
最坏时间复杂度：O(NM)
空间复杂度：O(M)
是否稳定：稳定

排序实现

在这里插入代码片
public static void radixSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    radixSort(arr, 0, arr.length - 1, maxBits(arr));
}

public static int maxBits(int[] arr) {
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }
    int res = 0;
    while (max != 0) {
        res++;
        max /= 10;
    }
    return res;
}

public static void radixSort(int[] arr, int begin, int end, int digit) {
    final int radix = 10;
    int i = 0, j = 0;
    int[] count = new int[radix];
    int[] bucket = new int[end - begin + 1];
    for (int d = 1; d <= digit; d++) {
        for (i = 0; i < radix; i++) {
            count[i] = 0;
        }
        for (i = begin; i <= end; i++) {
            j = getDigit(arr[i], d);
            count[j]++;
        }
        for (i = 1; i < radix; i++) {
            count[i] = count[i] + count[i - 1];
        }
        for (i = end; i >= begin; i--) {
            j = getDigit(arr[i], d);
            bucket[count[j] - 1] = arr[i];
            count[j]--;
        }
        for (i = begin, j = 0; i <= end; i++, j++) {
            arr[i] = bucket[j];
        }
    }
}

public static int getDigit(int x, int d) {
    return ((x / ((int) Math.pow(10, d - 1))) % 10);
}