基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

算法步骤

• 最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。
• 最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

动图演示

radixSort.gif

复杂度

时间复杂度 = O (nd) 空间复杂度 = O(n + d）

代码实现

 /**
     * MSD基数排序
     * @param arr 待排序数组
     * @param maxDigitArr 上一轮次高位数上的值排序后的有序数组
     * @return
     */
    public static Integer[] MSDRadixSort(Integer[] arr, Integer[] maxDigitArr) {
        Integer[] result = null;
        // 计算待排序数组中值的最大位数
        int digitNum = 0;
        int index;
        for (int value : arr) {
            int length = (value + "").length();
            digitNum = digitNum >= length ? digitNum : length;
        }

        // 对满足最高位的值排序
        List<Integer>[] lists = new ArrayList[10];
        for (int value : arr) {
            int length = (value + "").length();
            // 判断取出的值是否满足digitNum位
            if (length < digitNum) {
                // 不足digitNum位，补上相应的0，放入角标为0的桶内
                // 角标为0的桶内元素处理，按照最高位满足digitNum位的步骤处理
                if (lists[0] == null)
                    lists[0] = new ArrayList<>();
                lists[0].add(value);
            } else {
                // 最高位满足digitNum
                // 计算最高位的值，定位对应数组的角标index
                int temp = value;
                for (int i = digitNum; i >= 2; i--) {
                    temp = temp / 10;
                }
                index = temp % 10;
                if (lists[index] == null)
                    lists[index] = new ArrayList<>();
                lists[index].add(value);
            }
        }
        // 按照最高位digitNum一轮次排序后，对除角标0外，不为空的数量超过1的桶内元素排序
        // count --统计最大位数为digitNum的记录值数
        int number = 0;
        for (int i = 1; i < 10; i++) {
            if (lists[i] != null && lists[i].size() >= 1) {
                number += lists[i].size();
                // 对桶内元素排序（用直接插入排序）
                // 从无序区依次取值
                for (int j = 1; j < lists[i].size(); j++) {
                    Integer jValue = lists[i].get(j);
                    // 从有序区依次取值
                    for (int k = j - 1; k >= 0; k--) {
                        if (lists[i].get(k) <= jValue) {
                            break;
                        } else {
                            // 相邻值互换
                            Integer kValue = lists[i].get(k);
                            lists[i].set(k, jValue);
                            lists[i].set(k+1, kValue);
                        }

                    }
                }
            }
        }

        Integer[] backupArr = new Integer[number];
        // 对除角标0外的不为空的桶，按角标大小依次从中取值合并
        int count = 0;
        for (int i = 1; i < 10; i++) {
            if (lists[i] != null) {
                for (int value : lists[i]) {
                    backupArr[count] = value;
                    count++;
                }
            }
        }

        // 个位数上的值比较排序后，list[0] == null，特殊情况：待排序数组包含0值
        Integer[] array;
        if (lists[0] != null && lists[0].size() >=2) {
            Object[] objectArr = lists[0].toArray();
            array = new Integer[objectArr.length];
            for (int i = 0; i < objectArr.length; i++) {
                array[i] = (Integer) objectArr[i];
            }
            // 每次根据某个位数排序后，得出的backupArr，作为下次递归时的maxDigitArr
            if (maxDigitArr == null) {
                result = MSDRadixSort(array, backupArr);
            } else {
                Integer[] temp = new Integer[backupArr.length + maxDigitArr.length];
                System.arraycopy(backupArr, 0, temp, 0, backupArr.length);
                System.arraycopy(maxDigitArr, 0, temp, backupArr.length, maxDigitArr.length);
                result = MSDRadixSort(array, temp);
            }
        }

        if (lists[0] == null || lists[0].size() == 1) {
            result = new Integer[backupArr.length + maxDigitArr.length];
            System.arraycopy(backupArr, 0, result, 0, backupArr.length);
            System.arraycopy(maxDigitArr, 0, result, backupArr.length, maxDigitArr.length);
        }

        return result;
    }

    //LSD  由低位为基底，先从 kd 开始排序，再对 kd - 1 进行排序，依次重复，直到对 k1 排序后便得到一个有序序列。LSD 方式适用于位数少的序列。
    public static int[] radixsort(int[] arr) {
        int[] radix = Arrays.copyOf(arr,arr.length);
        int[][] nums = new int[10][0];
        int max = RandomUtils.getMaxForArr(radix);
        int multiple = 1;
        int len = Integer.toString(max).length();
        while (multiple <= len) {

             RandomUtils.arrsClear(nums);

            for (int i = 0; i < radix.length; i++) {

                String s = Integer.toString(radix[i]);
                int length = s.length();
                if (length >= multiple) {

                    int end = length - multiple + 1;
                    int start = end - 1;

                    int unit = Integer.parseInt(Integer.toString(radix[i]).substring(start,end));

                    nums[unit] = RandomUtils.arrAppend(nums[unit],radix[i]);
                } else {
                    nums[0] = RandomUtils.arrAppend(nums[0],radix[i]);
                }

            }

            RandomUtils.soutArrs(nums);

            int step = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i].length <= 0)continue;
                for (int j = 0; j < nums[i].length; j++) {
                    radix[step++] = nums[i][j];
                }
            }

            multiple++;
        }

        return radix;
}

  public static void arrsClear(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[0];
        }
  }

  public static int getMaxForArr(int[] arr) {
         int max = arr[0];
        for (int i: arr) {
            if (i > max) max = i;
        }
        return max;
    }

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