不支持0和負(fù)數(shù)
基數(shù)排序?qū)τ胸?fù)數(shù)和 0 的數(shù)列難以進(jìn)行排序
一般來說桶思想就是：分配，回收，重復(fù)
分配：歸類到桶里
回收：從桶里取出
重復(fù)：重復(fù)以上操作

    /**
     * 基數(shù)排序：平均時(shí)間復(fù)雜度-O(n+k) 空間復(fù)雜度-O(n+k)
     * 非比較排序，多關(guān)鍵字排序
     * 將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補(bǔ)零
     * 從最低位開始，依次進(jìn)行一次排序
     * 從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個(gè)有序序列
     * <p>
     * 跟計(jì)數(shù)排序相似,都是桶思想
     */
    public static class RadixSort {
        public static void main(String[] args) {

            int[] arr = {421, 23, 45, 6539, 678, 234, 125};
            radixSort(arr);
        }

        public static void radixSort(int[] arr) {
            // 計(jì)算出最高位
            int length = getMaxDigit(arr);
            // 桶
            int[] bucket = new int[10];
            int[] result = new int[arr.length];

            for (int i = 0; i < length; i++) {
                // 對同位數(shù)上的進(jìn)行分組
                int division = (int) Math.pow(10, i);
                for (int j = 0; j < arr.length; j++) {
                    int num = arr[j] / division % 10;
                    bucket[num]++;
                }
                // 疊加元素（放到桶里）
                for (int j = 1; j < bucket.length; j++) {
                    bucket[j] += bucket[j - 1];
                }

                // 逆序輸出
                for (int m = arr.length - 1; m >= 0; m--) {
                    int num = arr[m] / division % 10;
                    //  取出
                    result[--bucket[num]] = arr[m];
                }
                System.arraycopy(result, 0, arr, 0, arr.length);
                // 清空bucket（全部賦值為0）
                Arrays.fill(bucket, 0);
                System.out.println(Arrays.toString(result));
            }
        }

        public static int getMaxDigit(int[] arr) {
            int max = arr[0];
            for (int i : arr) {
                if (max < i) {
                    max = i;
                }
            }
            return (max + "").length();
        }
    }