基数排序

基数排序也是用了桶排序的思想，使用元素的每一位数字来决定桶的位置，排序过程如下：

代码示例：

public class Radix {

    public static void main(String[] args) {
        int[] array = {1,4,5,6,23,1,3,333,22,123,3432,412,31,231,2123};
        System.out.println(Arrays.toString(radixSort(array)));
    }

    public static int[] radixSort(int[] array) {
        // 最大值
        int max = getMax(array);
        // 最大值的长度
        int maxNumLength = getNumLength(max);
        
        List[] buckets = new ArrayList[10];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<Integer>();
        }
        int[] tmpArray = Arrays.copyOf(array, array.length);
        for (int i = 1; i <= maxNumLength; i++) {
            // 存入桶中
            for (int j = 0; j < tmpArray.length; j++) {
                int bucketIndex = (int) (tmpArray[j] % Math.pow(10, i) / Math.pow(10, i - 1));
                buckets[bucketIndex].add(tmpArray[j]);
            }
            // 按顺序取出
            int index = 0;
            for (int j = 0; j < buckets.length; j++) {
                for (int m = 0; m < buckets[j].size(); m++) {
                    tmpArray[index++] = (int)(buckets[j].get(m));
                }
                buckets[j] = new ArrayList<Integer>();
            }
        }

        return tmpArray;
    }

    private static int getNumLength(int number) {
        int tmp = 1;
        int length = 0;
        while ((number / tmp) != 0) {
            length++;
            tmp = tmp * 10;
        }
        return length;
    }

    private static int getMax(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        return max;
    }

}