基数排序1111

遇到最大位程序结束，将桶中的元素一一倒出，

接下来详细分析定义一个数组来接受个，十，百位每个数字出现的次数，

然后将前一项出现次数与这一项项加

再将数从右到左排进桶中（相当于找下标）

public class radixSort {
    public static void main(String[] args) {
        int[] arr={13,21,11,52,62,43};
        RadixSort(arr);
        for(int nums:arr){
            System.out.println(nums);
        }
    }
    public static void RadixSort(int[] arr){
        if(arr.length<2){
            return;
        }
        sort(arr,0,arr.length-1,digit(arr));
    }
    //计算位数
    public static int digit(int[] arr){
        int max=Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++){
            max=Math.max(max,arr[i]);
        }
        int count=0;
        while(max!=0){
            max/=10;
            count++;
        }
        return count;
    }
    public static  void sort(int[] arr,int l,int r,int digit){
        final int count=10;
       int[] bucket=new int[r-l+1];//这是一桶，用于接收排序后的数
       int n=0;
       int b=0;
       int c=0;
       for(int i=1;i<=digit;i++){
           int[] count1=new int[count];//储存每次得到个，十，百，的次数
           for(int j=l;j<=r;j++){
               n=getGit(arr[j],i);//得到次数
               count1[n]++;
           }
           for(int m=1;m<count;m++){
               count1[m]=count1[m]+count1[m-1];//然后将前一项出现次数与这一项项加
           }
           for(int a=r;a>=l;a--){
             bucket[count1[getGit(arr[a],i)]-1]=arr[a];
               count1[getGit(arr[a],i)]--;
           }
           for(b=l,c=0;b<=r;b++,c++){
               arr[b]=bucket[c];
           }

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

}