八大排序算法之基数排序—Java

#基数排序
基数排序的求解思路可以参考链接.
此处只附对应的Java代码

public class RadixSortDemo {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        //1.先找到最大值
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            maxValue = Math.max(maxValue, arr[i]);
        }
        //2.最大值对应几位数？
        int maxValueLength = (maxValue + "").length();
        //3.构建10个桶
        int[][] bucket = new int[10][arr.length];
        //4.每个桶中存放数据的个数
        int[] bucketElementCount = new int[10];
        //5.针对每个元素的对应位进行排序处理处理，第一次为个位，第二次为十位数...
        for (int i = 0, n = 1; i < maxValueLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的对应位的值
                int digit = (arr[j] / n) % 10;
                bucket[digit][bucketElementCount[digit]++] = arr[j];
            }
            //6.按照桶的顺序将数据放入原数组
            int index = 0;
            for (int k = 0; k < bucketElementCount.length; k++) {
                for (int j = 0; j < bucketElementCount[k]; j++) {
                    arr[index++] = bucket[k][j];
                }
            }
            //7.重置bucketElementCount
            bucketElementCount = new int[10];
        }

    }
}