记数基数排序

记数基数排序的基础是桶排序，桶排序的一个要求就是要排序的数在一定范围以内，比如最大为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)))看着挺吓人，其实就是三位数每个位置上的数值，这段代码的原理就是从低位到高位，用了三次桶排序，当然每次排完的最后要把原数组的值改为输出数组的值，这样可以保存上一次排完的顺序。