基数排序 | 半卷书

基数排序

这个最有意思的一个排序算法

public class RadixSort {

    public static void main(String[] args) {
        int[] arr=new int[] {67,45,1,234,987,22,11,3};
        radixSort(arr);
        System.err.println(Arrays.toString(arr));
    }
    //有 0 ，1,2,3,4,5,6,7,8,9个桶   
    //依次按照个位、十位、百位...放入对应的桶
    //再一次取出
    //如此循环
    public static void radixSort(int[] arr) {
        //取出数组中最大数
        int max=Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++) {
            if(arr[i]>max) {
                max=arr[i];
            }
        }
        //缓存 保存每轮结果
        int[][] temp=new int[10][arr.length];
        //每个桶保存了几个数
        int[] counts=new int[10];
        //基数排序执行几轮有最大数的位数决定
        int maxLength=(max+"").length();
        for(int j=0,n=1;j<maxLength;j++,n*=10) {
            for(int k=0;k<arr.length;k++) {
                //个位数的数字、十位的数字...
                int digit=arr[k]/n%10;
                temp[digit][counts[digit]]=arr[k];
                counts[digit]++;
            }
            for(int[] aa:temp) {
                System.err.println(Arrays.toString(aa));
            }
            int index=0;
            //执行完一轮之后把数字按照顺序取出
            for(int m=0;m<10;m++) {
                //桶里有数取出
                if(counts[m]>0) {
                    //把桶里的数依次取出
                    for(int h=0;h<counts[m];h++) {
                        arr[index]=temp[m][h];
                        index++;
                    }
                    counts[m]=0;
                }
            }
        }
    }

}