Radix Sorting 稳定 O(d(r+n))
不需要进行关键字之间的比较、交换、移动，借助分配和收集完成排序
扑克牌
最主位关键字
最次位关键字
最高位优先 most significant digit first 先按照最主位关键字排序，知道最后一个关键字，必须将序列逐层分割成若干个子序列，然后对个子序列分别进行排序
最低位优先least significant digit first 从最次位关键字开始，知道最主位关键字，不必分成子序列，对每一个关键字的排序都是整个序列参加排序，但是，对除最低位关键字之外的关键字进行排序时，必须使用稳定的排序算法
采用LSD实现数组元素排序
先按个位数进行排序，再按十位数进行排序，……，知道最高位
（1）必须知道数组中最大的元素是几位数，最大的元素是几位数，就需要进行几轮比较
（2）将每轮排序的结果放在一个临时数组中
public static void radioSortLSD(int[] array){ //先按个位数排序，再按十位数排序，直到最高位，因此，必须先知道数组中的最大元素是几位数 //得到数组中最大的元素，最大的元素的位数 int max = getMax(array); //对每一位进行排序时，必须知道有几个数 //例如，先按照个位数排序，必须知道待排序数组中个位数为0,1,2,3,4,5,6,7,8,9的数分别有几个,暂时将它们存储在一个长度为10 的数组中 //一个数的个位数是几，是该数除以10的余数 //一个数的十位数是几，是该数除以10之后的数再除以10的余数 （x/10）%10 //先按个位数排序，再按十位数排序，直到最高位， 将每次排序的结果先存储在一个临时数组中，然后复制到待排序数组中 for(int div=1;max/div>0;div*=10){ int[] temp = new int[array.length]; int[] count = getCount(array, div); //count[i]中记录的是当前按照某位数（如个位数）进行排序，该位上的值为i的元素的个数 //调整count[]，调整之后，count[i]中的值为该位（如个位数）上的值为i的元素在临时数组中的下标起始值 for(int i=count.length-1;i>=0;i--){ int tempCount = 0; for(int j=i-1;j>=0;j--){ tempCount += count[j]; } count[i] = tempCount; } System.out.print("count adjuge-----");listArray(count); for(int i=0;i<array.length;i++){ //(array[i]/div)%10 temp[count[(array[i]/div)%10]] = array[i]; count[(array[i]/div)%10]++; } //将临时数组中的结果复制到待排序数组中 for(int i=0;i<temp.length;i++){ array[i] = temp[i]; } listArray(array); } } public static int[] getCount(int[] array,int div){ int count[] = new int[10]; //count数组中，下标为i的元素count[i]的值 即为待排序数组中当前位数（如个位）是i的元素的个数 for(int i=0;i<array.length;i++){ count[(array[i]/div)%10]++; } System.out.print("count---");listArray(count); return count; } public static int getMax(int array[]){ int max = 0; for(int i=0;i<array.length;i++){ if(max<array[i]){ max = array[i]; } } return max; } 原始数据：278 109 63 930 589 184 505 269 8 83 count---1 0 0 2 1 1 0 0 2 3 count adjuge-----0 1 1 1 3 4 5 5 5 7 930 63 83 184 505 278 8 109 589 269 count---3 0 0 1 0 0 2 1 3 0 count adjuge-----0 3 3 3 4 4 4 6 7 10 505 8 109 930 63 269 278 83 184 589 count---3 2 2 0 0 2 0 0 0 1 count adjuge-----0 3 5 7 7 7 9 9 9 9 8 63 83 109 184 269 278 505 589 930