记数基数排序的基础是桶排序，桶排序的一个要求就是要排序的数在一定范围以内，比如最大为K，桶排序的一般步骤有下面三步：
1，建立一个大小为K+2的数组用来记数，(为什么是K+2， 因为我们用k+1的桶来记录k的数量)建立完记数数组之后，就遍历原数组，也就是要排序的数组，遍历一次就使记数加1。
2，对记数数组count[]从新赋值，即第i项的值是前面i-1项的和，这样表示的意思是第i项前面总共有count[i-1] + count[i-2] +...的数小于它，
3，对输出数组赋值，遍历原数组，根据在输出数组的位置来赋值。
下面用一个例子来描述：
private int[] countSort(int[] oriArray, int k) {
int[] tagArray = new int[k + 2];
int sum = 0; //
int[] sortArray = new int[oriArray.length];
//step1 记数，用k+1桶表示k桶的数据
//为什么这么写，后面会说。
for (int i = 0; i < oriArray.length; i++) {
tagArray[oriArray[i] + 1]++;
}
// step2 对记数数组重新赋值，
for (int i = 0; i <= k; i++) {
sum += tagArray[i];
tagArray[i] = sum;
}
// step3 输出数组
//通过前面的记数可以发现，tagArray[oriArray[i]]表示的其实是小于oriArray[i]的数量，也就是oriArray[i]在输出数组中的index，后面为什么tagArray[oriArray[i]]++，是因为如果有同样的数，那么就往后加一位。
for (int i = 0; i < oriArray.length; i++) {
sortArray[tagArray[oriArray[i]]] = oriArray[i];
tagArray[oriArray[i]]++;
}
for (int i = 0; i < sortArray.length; i++) {
Log.e("AAA", "the sortarray " + i + " " + sortArray[i]);
}
return sortArray;
}
说完了桶排序，记数基数排序就简单了，看一个简单例子：
假如有一些三位数，要求对他们排序，这个时候用桶排序就不合适了，总不能建1000个桶吧，比如说对下面的数组排序
int[] array = new int[]{367, 236, 544, 123, 532, 894, 353, 934, 477};
当然这些数有点少，但是原理是一样的，先对三位数的个位数进行桶排序，然后对十位数，最后对百位数，代码如下：
private void countingRadixSort(int[] array, int length) {
int maxVlue = 10;
int[] outArray = new int[array.length];
for (int position = length - 1; position >= 0; position--) {
int[] count = new int[maxVlue + 1];
int sum = 0;
for (int i = 0; i < array.length; i++) {
count[Integer.parseInt(String.valueOf(String.valueOf(array[i]).charAt(position))) + 1]++;
}
for (int b = 0; b < count.length; b++) {
sum += count[b];
count[b] = sum;
}
for (int i = 0; i < array.length; i++) {
outArray[count[Integer.parseInt(String.valueOf(String.valueOf(array[i]).charAt(position)))]] = array[i];
count[Integer.parseInt(String.valueOf(String.valueOf(array[i]).charAt(position)))]++;
}
for (int k = 0; k < outArray.length; k++) {
array[k] = outArray[k];
}
}
for (int i = 0; i < array.length; i++) {
Log.e("AAA", " array " + i + " is " + array[i]);
}
}
中间有一段，Integer.parseInt(String.valueOf(String.valueOf(array[i]).charAt(position)))看着挺吓人，其实就是三位数每个位置上的数值，这段代码的原理就是从低位到高位，用了三次桶排序，当然每次排完的最后要把原数组的值改为输出数组的值，这样可以保存上一次排完的顺序。
