基数排序

百度百科：

基数排序(radix sort)属于"分配式排序"(distribution sort)，又称"桶子法"(bucket sort)或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些"桶"中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

从上面的简单介绍，是并不了解基数排序是怎么弄的～基数排序不同与其他的排序，其他排序本质上都是按照交换或者比较来进行排序，但是基数排序并不是，它是按照分配，回收(分配到不同的位置上，然后回收)..不断分配..回收来进行排序，直到有序..

首先我们有以下这个数组：
int[] arrays = {6, 4322, 432, 344, 55 };

现在我们有10个桶子，每个桶子下能装载arrays.length个数字..

int[][] buckets = new int[arrays.length][10];

将数组的每个个位数进行分配到不同的桶子上：

将数组的每个十位数进行分配到不同的桶子上(像6这样的数，往前边补0)：

将数组的每个百位数进行分配到不同的桶子上(像6、55这样的数，往前边补0)：

将数组的每个百位数进行分配到不同的桶子上(像6、55，344，432这样的数，往前边补0)：

此时我们的数组就已经可以排好序了~~~过程就是这样子，其实不难就只有两个步骤：

• 将数组的每一位放进桶子里

• 回收

• 循环……

/**
 * @author yk
 */
public class CardinalSort {

    public static int findMax(int[] arrays, int L, int R) {

        //如果该数组只有一个数，那么最大的就是该数组第一个值了
        if (L == R) {
            return arrays[L];
        } else {

            int a = arrays[L];
            int b = findMax(arrays, L + 1, R);

            if (a > b) {
                return a;
            } else {
                return b;
            }
        }
    }

    public static void radixSort(int[] arrays) {

        int max = findMax(arrays, 0, arrays.length - 1);

        //需要遍历的次数由数组最大值的位数来决定
        for (int i = 1; max / i > 0; i = i * 10) {

            int[][] buckets = new int[arrays.length][10];

            //获取每一位数字(个、十、百、千位...分配到桶子里)
            for (int j = 0; j < arrays.length; j++) {

                int num = (arrays[j] / i) % 10;

                //将其放入桶子里
                buckets[j][num] = arrays[j];
            }

            //回收桶子里的元素
            int k = 0;

            //有10个桶子
            for (int j = 0; j < 10; j++) {
                //对每个桶子里的元素进行回收
                for (int l = 0; l < arrays.length ; l++) {

                    //如果桶子里面有元素就回收(数据初始化会为0)
                    if (buckets[l][j] != 0) {
                        arrays[k++] = buckets[l][j];

                    }

                }

            }

        }
    }

}