入门算法：基数排序

上手难度：★★★★

算法复杂度：O(nlog(r)m)，其中r为所采取的基数，而m为堆数

基数排序.gif

排序思想：

通过获取最大值的位数，进行循环遍历
第一次按个位排序后，除了一位数的值排好序了，整体来看依旧是无序的状态
第二次按十位排序后，所有一位数的值都会按顺序放到0位上，一位数的值已经排好序了，而按十位排序，两位数的值也会排好序，由于两位数的个位值之前已经按从小到大的顺序排序好了，所以在按十位值排序时，两位数的值也能按照从小到大的顺序排好

以此类推，每一次按位排序都会把这一位的数值排好序，同时为更高位的排序做好铺垫

建议把动图下载下来，逐帧播放比较好理解流程

代码实现：

public class RadixSort {

    public static int[] sort(int[] sourceArray) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        //获取位数
        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private static int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    /**
     * 获取最大值
     */
    private static int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    /**
     * 获取num的位数，例如100是3，10是2
     */
    protected static int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private static int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            //遍历数组，第一次进来mod=10,dev=1;往后每次进来翻10倍
            for (int j = 0; j < arr.length; j++) {
                //第一次对arr遍历对mod取余会得到个位数
                //第二次对arr遍历时，mod=100,dev=10,所有一位数的arr[j]都会落在[0]上，其他值会按照十位数的值排好序
                int bucket = ((arr[j] % mod) / dev) + mod;
                //把值存入取余对应的结果索引中，索引需要+10，也包含负数
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            //遍历counter里面的一维数组，每一次都按当前位排序的结果存入arr中
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private static int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

    public static void main(String[] args) {

        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        arr = sort(arr);

        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }

    }
}