6. 前缀树、不基于比较的排序

前缀树

021 ``010 ``111 ``022 ``011 ``012
第一步：个位数进桶，出桶
0号桶：010
1号桶：021 111 011
2号桶：022 012
3号桶：
4号桶：
5号桶：
6号桶：
7号桶：
8号桶：
9号桶：
出桶后顺序：010 021 111 011 022 012
第二步：十位数进桶，出桶
0号桶：
1号桶：010 111 011 012
2号桶：021 022
3号桶：
4号桶：
5号桶：
6号桶：
7号桶：
8号桶：
9号桶：
出桶后顺序：010 ``111 ``011 ``012 ``021 ``022
第三步：百位数进桶，出桶
0号桶：010 011 ``012 ``021 022
1号桶：111
2号桶
3号桶：
4号桶：
5号桶：
6号桶：
7号桶：
8号桶：
9号桶：
出桶后顺序：010 ``011 ``012 ``021 ``022 ``111

优雅实现方式：不使用桶
021 ``010 ``111 ``022 ``011 ``012

准备一个大小为10的数组，
cout [1, 3, 2, 0, 0, 0, 0, 0, 0, 0] count【 表示个位数字为数组下标的数有几个】
cout[1, 4, 6, 6, 6, 6, 6, 6, 6, 6] count【表示个位数字<=数组下标的一共有几个】只标识当出现个位数字为i的数字时，应该填在cout`[i] - 1的位置上。

021 ``010 ``111 ``022 ``011 ``012
准备一个辅助数组存储以上六个数：help[]，下标0-5
从右向左看：
012 个位数字为2，查看cont[2] = 6 表示个位<=6的有6个，整体个位数小于等于2的数字占据的区域应该在 0-5， 而012又是从最右侧开始的，因此 **help[5] = 012, **cont[2]— ; cout` [1, 4, 5, 6, 6, 6, 6, 6, 6, 6]
011 个位数为，查看cont[1] = 4表示个位<=1的有4个，整体个位数小于等于1的数字占据的区域应该在 0-3范围上，而011从右侧遍历的，因此 **help[3] = 011, **cont[1]— ; cout` [1,3, 5, 6, 6, 6, 6, 6, 6, 6]
。。。
最后实现 help辅助数组中的数字就是一次进桶出桶操作后的数字序列。

代码实现：

public class Code04_RadixSort {
    // only for no-negative value
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxbits(arr));
    }
    /**
     * 最大值十进制位数
     *
     * @param arr
     * @return
     */
    public static int maxbits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }
    // arr[L..R]排序  ,  最大值的十进制位数digit
    /**
     * @param arr   数组
     * @param L     左边界 0
     * @param R     右边界 N-1 L = 0 R = N - 1时全局进行基数排序
     * @param digit 最大值的十进制数的位数
     *  时间复杂度： O((R-L+1)*log10MAX) MAX表示十进制最大数
     */
    public static void radixSort(int[] arr, int L, int R, int digit) {
        final int radix = 10;
        int i = 0, j = 0;
        // 有多少个数准备多少个辅助空间
        int[] help = new int[R - L + 1];
        for (int d = 1; d <= digit; d++) { // 最大数有多少位就进出多少次桶，从低位到高位依次进桶；如个位、十位、百位、千位
            // 10个空间
            // count[0] 当前位(d位)是0的数字有多少个
            // count[1] 当前位(d位)是(0和1)的数字有多少个
            // count[2] 当前位(d位)是(0、1和2)的数字有多少个
            // count[i] 当前位(d位)是(0~i)的数字有多少个
            int[] count = new int[radix]; // count[0..9]
            // 统计0-9十个桶中的词频 count[]
            for (i = L; i <= R; i++) {
                // 103  1   3
                // 209  1   9
                j = getDigit(arr[i], d);
                count[j]++;
            }
            // 累加 count`[]
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            // 从右往左开始遍历
            for (i = R; i >= L; i--) {
                j = getDigit(arr[i], d);
                help[count[j] - 1] = arr[i];
                count[j]--;
            }
            // 将help辅助数组拷贝到arr中，进入到下一轮的进桶出桶
            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = help[j];
            }
        }
    }
    /**
     * 获取十进制数 倒数第d位上的数字  如  getDigit(101,1)  表示获取个位上数字 1； getDigit(101,2)表示获取百位上数字 0
     * @param x 十进制数组
     * @param d
     * @return
     */
    public static int getDigit(int x, int d) {
        return ((x / ((int) Math.pow(10, d - 1))) % 10);
    }
}

排序算法总结

排序算法总结：

1. 不急于比较的排序，对样本数据有严格要求，不易改写
2. 基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
3. 基于比较的排序，时间复杂度的极限就是O(N*logN)
4. 时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的
5. 为了绝对的速度选择快排、为了省空间选择堆排序、为了稳定性选择归并排序

单纯的追求速度快，使用快排序，在大量实验基础上表明，快排，常数时间比较优异
在O(N*logN)的时间复杂度下，堆排序适合较小的额外空间复杂度，归并排序适合稳定性要求高的
以上三点都做到的比较算法，目前没未发现。

常见的坑：

1. 归并排序的往外空间复杂度可以变为O(1),”归并排序，内部缓存法”，但是将变得不再稳定。
2. “原地归并排序”，会导致时间复杂度变为O（N2）。
3. 快速排序稳定性改进，“01 stable sort”,但是会对样本数据要求更多。