算法-排序-下（Sorting）

7.希尔排序（Shell Sort）

◼ 1959年由唐纳德·希尔（Donald Shell）提出
◼ 希尔排序把序列看作是一个矩阵，分成 m 列，逐列进行排序
m 从某个整数逐渐减为1
当 m 为1时，整个序列将完全有序

◼ 因此，希尔排序也被称为递减增量排序（Diminishing Increment Sort）

◼ 矩阵的列数取决于步长序列（step sequence）
✓ 比如，如果步长序列为{1,5,19,41,109,...}，就代表依次分成109列、41列、19列、5列、1列进行排序
✓ 不同的步长序列，执行效率也不同

希尔排序 – 实例
◼ 希尔本人给出的步长序列是 n/(2^k)，比如 n为16时，步长序列是{1, 2, 4, 8}

◼ 分成8列进行排序

◼ 分成4列进行排序

◼ 分成2列进行排序

◼ 分成1列进行排序

◼ 不难看出来，从8列变为 1列的过程中，逆序对的数量在逐渐减少
因此希尔排序底层一般使用插入排序对每一列进行排序，也很多资料认为希尔排序是插入排序的改进版

希尔排序 – 实例

◼ 假设有11个元素，步长序列是{1, 2, 5}

◼ 假设元素在第 col 列、第 row 行，步长（总列数）是 step
那么这个元素在数组中的索引是 col + row * step
比如 9 在排序前是第 2 列、第 0 行，那么它排序前的索引是 2 + 0 * 5 = 2
比如 4 在排序前是第 2 列、 1 行，那么它排序前的索引是 2 + 1 * 5 = 7
实现

@Override
    protected void sort() {
        List<Integer> stepSequence = shellSequence();
        for (Integer step : stepSequence) {
            //按照步长进行排序
            sort(step);
        }
    }
    /**
     * 分成step列进行排序
     */
    private void sort(int step) {
        // col : 第几列，column的简称
        for (int col = 0; col < step; col++) {// 对第col列进行排序
            // col、col+step、col+2*step、col+3*step
            for (int begin = col + step; begin < arr.length; begin += step) {
                int cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur - step);
                    cur -= step;
                }
            }
        }
    }

    /*
     * 获取步长数组
     */
    private List<Integer> shellSequence(){
        List<Integer> stepSequence = new ArrayList<>();
        int step = arr.length;
        while ((step = step >> 1) > 0) {
            stepSequence.add(step);
        }
        return stepSequence;
    }

◼ 最好情况是步长序列只有1，且序列几乎有序，时间复杂度为 O(n)
◼ 空间复杂度为O(1)，属于不稳定排序
◼ 希尔本人给出的步长序列，最坏情况时间复杂度是 O(n^2)

◼ 目前已知的最好的步长序列，最坏情况时间复杂度是 O(n^(4/3)) ，1986年由Robert Sedgewick提出

private List<Integer> sedgewickStepSequence() {
        List<Integer> stepSequence = new LinkedList<>();
        int k = 0, step = 0;
        while (true) {
            if (k % 2 == 0) {
                int pow = (int) Math.pow(2, k >> 1);
                step = 1 + 9 * (pow * pow - pow);
            } else {
                int pow1 = (int) Math.pow(2, (k - 1) >> 1);
                int pow2 = (int) Math.pow(2, (k + 1) >> 1);
                step = 1 + 8 * pow1 * pow2 - 6 * pow2;
            }
            if (step >= arr.length) break;
            stepSequence.add(0, step);
            k++;
        }
        return stepSequence;
    }

8.计数排序（Counting Sort）

◼ 之前学习的冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序
平均时间复杂度目前最低是 O(nlogn)

◼ 计数排序、桶排序、基数排序，都不是基于比较的排序
它们是典型的用空间换时间，在某些时候，平均时间复杂度可以比 O(nlogn) 更低

◼ 计数排序于1954年由Harold H. Seward提出，适合对一定范围内的整数进行排序

◼ 计数排序的核心思想
统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引

计数排序 – 最简单的实现

@Override
    protected void sort() {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //统计每个元素出现的次数,counts的长度取决于arr中最大的元素
        int[] counts = new int[1 + max];
        for (int i = 0; i < arr.length; i++) {
            //arr[i]是作为counts的索引
            counts[arr[i]] ++;
        }
        //按照顺序赋值
        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            //counts[i]代表每个元素出现的次数,索引i就是arr中的元素
            while (counts[i] -- > 0) {
                arr[index ++] = i;
            }
        }
    }

◼ 这个版本的实现存在以下问题
无法对负整数进行排序
极其浪费内存空间
是个不稳定的排序

计数排序 – 改进思路

...

    @Override
    protected void sort() {
        //获取元素最大值
        int max = arr[0];
        //获取元素最小值
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        // 开辟内存空间，存储次数
        int[] counts = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            //arr[i]-min是作为counts的索引
            counts[arr[i] - min]++;
        }
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i-1];
        }
        //用于存放排序好的数组
        int[] output = new int[arr.length];
        for (int i = counts.length - 1; i >= 0; i--) {
            output[--counts[arr[i]-min]] = arr[I];
        }
        //重新赋值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }

◼ 最好、最坏、平均时间复杂度：O(n + k)
◼ 空间复杂度：O(n + k)
◼ k 是整数的取值范围
◼ 属于稳定排序

9.基数排序（Radix Sort）

◼ 基数排序非常适合用于整数排序（尤其是非负整数），因此本课程只演示对非负整数进行基数排序
◼ 执行流程：依次对个位数、十位数、百位数、千位数、万位数...进行排序（从低位到高位）

◼ 个位数、十位数、百位数的取范围都是固定的0~9，可以使用计数排序对它们进行排序
◼ 思考：如果先对高位排序，再对低位排序，是否可行？

    @Override
    protected void sort() {
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        // 个位数: array[i] / 1 % 10 = 3
        // 十位数：array[i] / 10 % 10 = 9
        // 百位数：array[i] / 100 % 10 = 5
        // 千位数：array[i] / 1000 % 10 = ...
        for (int divider = 1; divider <= max; divider *= 10) {
            countSort(divider);
        }
    }
    private void countSort(int divider) {
        // 开辟内存空间，存储次数
        int[] counts = new int[10];
        // 统计每个整数出现的次数
        for (int i = 0; i < arr.length; i++) {
            //arr[i]counts的索引
            counts[arr[i] / divider % 10]++;
        }
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i-1];
        }
        // 从后往前遍历元素，将它放到有序数组中的合适位置
        int[] output = new int[arr.length];
        for (int i = counts.length - 1; i >= 0; i--) {
            output[--counts[arr[i] / divider % 10]] = arr[i];
        }
        //重新赋值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }

◼ 最好、最坏、平均时间复杂度：O(d ∗ (n + k)) ，d 是最大值的位数，k 是进制。属于稳定排序
◼ 空间复杂度：O(n + k)，k 是进制

基数排序 – 另一种思路

10.桶排序（Bucket Sort）

◼ 执行流程
① 创建一定数量的桶（比如用数组、链表作为桶）
② 按照一定的规则（不同类型的数据，规则不同），将序列中的元素均匀分配到对应的桶
③ 分别对每个桶进行单独排序
④ 将所有非空桶的元素合并成有序序列

◼ 元素在桶中的索引
元素值 * 元素数量