基数排序（不基于比较的排序）

基数排序过程图例：

原因：先以个位排序，再被高位数字颠覆掉，再按照十位数组排序，再被百位数组颠覆掉。

对上述桶利用几个简单结果替换（进行优化）：

算法代码：

public class BaseSort {
    public static void main(String[] args) {
        int[] arr = {11, 22, 34, 54, 67, 56, 87, 2, 34, 43, 12};
        sort(arr);
        for(int i=0; i<arr.length; i++){
            System.out.println(arr[i]);
        }

    }

    public static void sort(int[] arr){
        int length = arr.length;
        //获取数组中最大值位数
        int k = 0;
        int digit = maxbits(arr);
        final int base = 10;
        int[] help = new int[arr.length];
        for(int i=1; i<=digit; i++){
            int[] count = new int[base];
            //分别获取个位、十位、百位上的数字
            for(int j=0; j<length; j++){
                k = getDigit(arr[j],i);
                count[k]++;
            }
            for(int j=1; j<base; j++){
                count[j] = count[j] + count[j-1];
            }
            for(int j=length-1; j>=0; j--){
                k = getDigit(arr[j], i);
                help[count[k]-1] = arr[j];
                count[k]--;
            }
            for(int j=0; j<length; j++){
                arr[j] = help[j];
            }
        }
    }

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

    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;
    }
}

 

 

本文地址：https://blog.csdn.net/qq_26586431/article/details/109644822