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