Skip to content

Latest commit

 

History

History
59 lines (54 loc) · 1.44 KB

桶排序.md

File metadata and controls

59 lines (54 loc) · 1.44 KB

桶排序

    public static void radixSort(int[] arr){
        if(arr==null||arr.length<2){
            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;
    }
    //返回一个数的第d位数字
    public static int getDigit(int num,int d){
        int ans=0;
        while(d--!=0){
           ans=num%10;
           num/=10;
        }
        return ans;

    }
    public static void radixsort(int[] arr,int L,int R,int digit){
        final int radix=10;
        int i=0;int j=0;
        int[] help=new int[R-L+1];
        for(int d=1;d<=digit;d++){
            int[] count=new int[radix];
            for( i=L;i<=R;i++){
                j=getDigit(arr[i],d);
                count[j]++;
            }
            for(i=1;i<radix;i++){
                count[i]=count[i]+count[i-1];
            }
            for(i=R;i>=L;i--){
                j=getDigit(arr[i],d);
                help[count[j]-1]=arr[i];
                count[j]--;
            }
            for(i=L,j=0;i<=R;i++,j++){
                arr[i]=help[i];
            }
        }
    }