排序算法-基数排序

    基数排序是一种非比较排序算法，它将待排序的数字按照位数进行排序。基数排序的思想是先按照个位数进行排序，然后按照十位数进行排序，接着按照百位数进行排序，以此类推，直到最高位排序完成。

    基数排序的步骤如下：

 

代码思路：

class RadixSort{public static void redixSort(int[] arr){if (arr==null || arr.length <2){return;}redixSort(arr,0,arr.length-1,maxbits(arr));}//求最大数有多少位private static int maxbits(int[] arr) {int max = Integer.MIN_VALUE;for(int a: arr){max=Math.max(max,a);}int res=0;while (max != 0){res++;max/=10;}return res;}private static void redixSort(int[] arr, int l, int r, int digit) {final int radix=10;int i=0,j=0;//定义一个与arr长度相等的数组int[] help =new int[r-l+1];//有多少位就循环几次，从个位开始for (int d=1;d<=digit;d++){//count和count‘都用count表示//count[0] 当前位（d位）是0的数字有多少个//count[1] 当前位（d位）是（0和1）的数字有多少个//count[2] 当前位（d位）是（0和1和2）的数字有多少个//count[i] 当前位（d位）是（0~i）的数字有多少个int[] count=new int[radix];//count[0..9]//countfor (i=l;i<=r;i++){j=getDigit(arr[i],d);count[j]++;}//count’for (i=1;i<radix;i++){count[i]=count[i]+count[i-1];}//从右往左遍历，对应的数放到help中for (i=r;i>=l;i--){j=getDigit(arr[i],d);help[count[j]-1] = arr[i];count[j]--;}//help数组赋值给结果数组for (i=l, j=0;i<=r;i++,j++){arr[i] =help[j];}}}//取出当前数对应位数的数，如x=109，d=1，相当于取109个位上的数，即9private static int getDigit(int x,int d){return ((x/((int) Math.pow(10,d-1))) % 10);}
}