1.基数排序

public class RadixSort {
　　public void radixSort(int arr[]) {
　　　　if(arr == null || arr.length < 2) {
　　　　　　return;
　　　　}
　　　　radixSort(arr,0,arr.length - 1,getMaxBit(arr));
　　}
　　public void radixSort(int arr[],int left,int right,int maxBit) {
　　　　int help[] = new int[right - left + 1];
　　　　for(int i = 1;i <= maxBit;i ++) {
　　　　　　int count[] = new int[10];
　　　　　　for(int j = left;j <= right;j ++) {
　　　　　　　　int x = getFigure(arr[j],i);
　　　　　　　　count[x] ++;
　　　　　　}
　　　　　　for(int j = 1;j < 10;j ++) {
　　　　　　　　count[j] = count[j] + count[j - 1];
　　　　　　}
　　　　　　for(int j = right;j >= left;j --) {
　　　　　　　　int x = getFigure(arr[j],i);
　　　　　　　　help[count[x] - 1] = arr[j];
　　　　　　　　count[x] --;
　　　　　　}
　　　　　　for(int j = 0;j < help.length;j ++) {
　　　　　　　　arr[j] = help[j];
　　　　　　}
　　　　}
　　}
　　public int getMaxBit(int arr[]) {
　　　　int max = arr[0];
　　　　for(int i = 1;i < arr.length;i ++) {
　　　　　　max = Math.max(max,arr[i]);
　　　　}
　　　　int res = 0;
　　　　while(max != 0) {
　　　　　　max /= 10;
　　　　　　res ++;
　　　　}
　　　　return res;
　　}
　　public int getFigure(int x,int y) {
　　　　return x / (int)Math.pow(10,(y - 1)) % 10;
　　}
}