题目：对于一个int数组，请编写一个基数排序算法，对数组元素排序。给定一个int数组A及数组的大小n，请返回排序后的数组。保证元素均小于等于2000。测试样例：[1,2,3,5,2,3],6[1,2,2,3,3,5]
思路：所谓基数排序是另一种使用桶排序的方式。它比计数排序更优，需要的桶的数目更少，需要多次对数组元素进行桶排序，先对数值按照各位进行桶排序散列到哈希表中，然后遍历哈希表取出元素覆盖原始数组array，此时的元素在个位数上面时有序的，但在十位以及百位等位置是无序的，然后再对十位进行散列，过程与前面相同，根据十位数值散列到哈希表中，然后遍历哈希表取出元素覆盖到原始数组array，此时十位数是有序的，数组元素按照十位数大小进行排序，但是在十位数相同的桶中，有多个元素，他们的顺序是由上一次的排序确定的，即他们的顺序还是按照个位数的大小来排序的，从而取出后的顺序在十位和个位上面都是有序的。
于是创建0~9共10个桶，用来表示每一位的余数，用int count[]=new int[10]数组表示每一个余数中元素的数目，例如count[3]表示余数为3的桶中元素的数目，因此整个散列结构是数组连接数组的结构，即散列的基本结构是[0~9]的数组，在该数组的每一个元素中又是一条数组count[]用来存放具有相同余数的元素，每个位置的count[]表示的是余数为该值的元素数目，于是count[0]表示该余数为该值的第一个元素，count[1]表示余数为该值的第二个元素……在明确使用数组套数组的哈希表结构后如何构建这种结构？通过将数组元素散列到散列表以及链接数组中来逐步建立数组链接数组的结构（哈希表可以是简单的数组；也可以是数组链接链表的结构；也可以是数组链接数组的结构）。因此对于计数排序，也使用哈希表，但是由于只需要记录每个散列元素的数目，因此可以只使用数组来实现哈希表；但是基数排序中由于桶的数目减少，仅仅有10个桶，需要在每个桶中存放多个元素来存储多个元素，因此需要使用数组链接数组或者数组链接链表的形式来实现哈希表，本题使用数组链接数组的方式来实现哈希表，特殊的，对于数组链接数组的哈希表结构，可以使用2维数组来实现。
①先创建一个二维数组int number[][]=new int[10][n];来存放整个待排序数组的所有元素。高维（左边的维）代表的是10个桶，用来散列每个位的数字，低维代表的是每个余数的桶中存放的元素（就是存放元素而不是存放元素的数目），由于创建数组需要明确指定大小，而每个余数桶中元素的数目最少是0，最多是n，因此数组的大小是n，于是number[3][2]表示的是余数为3的桶中的下标为2（第3个元素）的元素；
②遍历原始待排序数组array，求出个位数作为余数value，按照这个余数将其散列到对应的数组下标的位置，由于可能在该余数位置有多个元素，因此需要在该位置创建一个数组count[]用来记录该余数的第j个元素的值，使用count[value]来记录余数为value的每个元素，count[value]初始值为0，每记录一个元素numbr[value][count[value]]=A[j]之后要将count[value]++；直到扫描完成这个原始数组为止，此时就是将原始数组中的所有元素都散列到了数组链接数组的结构中了，并且本位低一位小的元素先放入桶中，大的后放入桶中，可以保证顺序；
③遍历10个桶，将桶中的元素逐一取出来，对桶从小到大遍历，对每个桶中的元素也是从小到大遍历元素，将其取出来覆盖到原始数组array[]中，于是对于本次位（个位）的散列排序结束，调整取余的基数，进行下一次的散列排序和取出，直到余数为0，即扫描都最高位时结束。
即基数排序有2层循环，外层循环用来对各个位置取余数（循环有限，不计入时间复杂度），内层循环用来散列元素和收集元素，散列时按照余数进行散列并逐个延长链接数组；收集元素时遍历各个余数位置和链接数组进行取出并覆盖原始数组array。
常识：如何从一个长整数中取出某一个位上的数字：先除以10^n得到取整后的数，再%10即对10取模取得余数，从而取得这个数值。
注意理解count[]数组的作用以及作用范围。
importjava.util.*;
//基数排序：使用数组链接数组的哈希表结构来存放数据，通过二维数组来实现哈希表
publicclass RadixSort {
public int[] radixSort(int[] A, int n){
//特殊输入
if (A == null || A.length< 2)
return A;
// 创建一个二维数组存放数据,10是桶的数目，n是每个桶中元素的最多数目,其大小最大是n,可以不放满
int number[][] = newint[10][n];
//定义遍历k，用来求不同位置的余数
int k = 1;
// 第一层循环，用于对每个位置求余数,已知元素的数据<=2000，因此需要遍历的位数是固定的,p=1,10,100,1000;如果不给定<2000这个条件，则要通过value=(A[i]/k)%10<=0来进行判断是否结束
int p = 1;
while (p <= 4) {
/*定义一个数组count[]用来存放每个桶value中的元素,value的范围是0~9所以数组的大小是10；千万注意;count[]数组用来记录当前位上每个元素的数目,只对当前位有效,当对下一位进行处理时要将count[]数组全部元素置空或者将count[]定义在while()循环之内于是每次更换位数时都会重置count[]数组*/
int[] count = new int[10];
//遍历原始数组A，将元素散列到二维数组构建的哈希表中
for (int i = 0; i< n; i++) {
// 求出当前位上每个元素的余数(如何求一个数中的某一个位的数组：先除以k=10^m,再%10取余数)
int value =(A[i] / k) % 10;
number[value][count[value]]= A[i];
//添加一个元素后，要对链接数组的长度指针+1
count[value]++;
}
// 定义一个指针index来遍历新的数组，用于将从哈希表中取出的元素逐个覆盖到原始数组中
int index = 0;
// 原始数组遍历完成，元素已经全部放入到哈希表（二维数组）中，将其取出覆盖原数组
for (int i = 0; i< 10; i++) {
// 该余数值的位置可能有多个值（count[value]个），要循环取出里面的各个值,从0开始取出
for (int j= 0; j < count[i]; j++) {
A[index]= number[i][j];
index++;
}
}
//本次遍历结束，调整除数，对前面一位进行取余等处理
k *= 10;
p++;
}
//千万注意：排序结束后要返回结果数组
return A;
}
}