【排序算法】快速排序和希尔排序

封面画师：Nengoro(ネんごろぅ)     封面ID：74731465

本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化     Data Structure Visualizations

执行流程：本文统一以升序为例子。

1. 快速排序

1.1 前言

在前一篇文章中，谈到了归并排序，它的时间复杂度为 $O(nlogn)$。在初学排序算法时，谈到了堆排序，堆排序的时间复杂度也是 $O(nlogn)$。那么还有其他排序算法的时间复杂度也是 $O(nlogn)$ 吗？

当然是有的，快速排序 就是其中一种。

根据上图可知，快速排序的最好、平均时间复杂度为 $O(nlogn)$，但最坏时间复杂度是 $O(n^2)$，这点甚至赶不上归并排序和堆排序，那要是经常遇到最坏情况，效率岂不是很低？怎么对得起 快速 二字呢？

当然有办法减低最坏情况出现的概率，总体来说快速排序的效率还是很高的。相比于平均时间复杂度也为 $O(nlogn)$ 的归并排序和堆排序，快速排序会 “更快” 一点。

1.2 执行流程

快速排序（Quick Sort），1960年由 查尔斯·安东尼·理查德·霍尔（Charles Antony Richard Hoare，缩写为 C.A.R.Hoare） 提出，昵称为东尼·霍尔（一译托尼·霍尔，英语：Tony Hoare）。

这又是一位大佬，曾在 1980 年获颁图灵奖、在 2011 年获颁约翰·冯诺依曼奖。

执行流程

1. 从序列中选择一个轴点元素 pivot，假设每次选择 0 位置的元素为轴点元素；
2. 利用 pivot 将序列分割成 2 个子序列：
   • 将小于 pivot 的元素放在 pivot 前面（左侧）
   • 将大于 pivot 的元素放在 pivot 后面（右侧）
   • 等于 pivot 的元素放在哪边都可以
3. 对分割出的子序列重复操作，直到不能再分割（子序列中只剩下 1 个元素）

执行过程图

静态图：

动态图：

快速排序的本质是 逐渐将每一个元素都转换成轴点元素。 既然如此，需要先搞清楚 0 位置的元素是怎么变成轴点的。

1.3 轴点构造

先选择序列中 0 位置的元素作为轴点元素，然后设置两个指针 begin 和 end，其中 begin 指向序列首元素，end 指向序列尾元素。

在先前的设计中，常将 end 设置为序列的长度，在这里也可以将其设置为序列的长度，但更好是将 end 向后移一位，即将 end 指向序列尾元素。

选择好轴点元素后，还需要将其备份一份。

从序列 右边 开始遍历（从 end 向 begin 遍历），比较遍历元素与轴点元素的大小关系：

• 当 end 指向的元素 大于 轴点元素时， end--；
• 当 end 指向的元素 小于等于 轴点元素时，end 不变，用 end 指向的元素覆盖 begin 指向的元素，然后begin++。

每当一个元素位置被确定时，需要从 相反方向 进行遍历（从 begin 到 end 遍历），比较遍历元素与轴点元素的大小关系：

• 当 begin 指向的元素 大于 轴点元素时， begin 不变，用 begin 指向的元素覆盖 end 指向的元素，然后end--；
• 当 begin 指向的元素 小于等于 轴点元素时， begin++。

重复进行以上操作，直到 begin == end，这个时候用备份的元素覆盖 begin 和 end 指向的元素，这样一个轴点就构造出来了。

上图仅仅介绍了构造第一个轴点，如果需要对整个序列进行排序，相当于需要将每个元素都转换成轴点元素。

在确定了第一个轴点后，需要在轴点左右两边的序列中确认第二个、第三个轴点，然后在确认的轴点左右两边确认新的轴点，直到每个元素都被确认为轴点，这也标志着排序的结束。

这其实和归并排序很类似，属于一种递归。

1.4 编码实现

快速排序和归并排序类似，也可以采用递归的方式。先理一下思路：

1. 备份 begin 位置的元素，确认第一个轴点的位置；
2. 在上一步确认的轴点两边重复上一步操作，直到每个元素都转换成轴点元素。

这是一个递归的过程。

那么重点就是如何确认轴点了，而在上一节中已经分析的轴点的确认方法了。

/**
 * @author 默烦
 * @date 2020/8/16
 */
public class QuickSort<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        sort(0, array.length);
    }

    /**
     * 对 [begin, end) 范围的元素进行快速排序
     *
     * @param begin 序列开始位置索引
     * @param end   序列长度
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) return;
        // 确定轴点位置
        int p = pivot(begin, end);
        // 对子序列进行快速排序
        sort(begin, p);
        sort(p + 1, end);
    }

    /**
     * 构造出 [begin, end) 范围的轴点元素
     *
     * @param begin 序列开始位置索引
     * @param end   序列长度
     * @return 轴点元素的最终位置
     */
    private int pivot(int begin, int end) {
        // 随机选择一个元素跟begin位置进行交换
        swap(begin, begin + (int) (Math.random() * (end - begin)));

        // 备份 begin 位置的元素
        E pivot = array[begin];
        // end 指向最后一个元素
        end--;
        while (begin < end) {
            while (begin < end) {
                if (cmp(pivot, array[end]) < 0) { // 右边元素 > 轴点元素
                    end--;
                } else { // 右边元素 <= 轴点元素
                    array[begin++] = array[end];
                    // 赋值后换方向遍历
                    break;
                }
            }

            while (begin < end) {
                if (cmp(pivot, array[begin]) > 0) { // 左边元素 < 轴点元素
                    begin++;
                } else { // 左边元素 >= 轴点元素
                    array[end--] = array[begin];
                    // 赋值后换方向遍历
                    break;
                }
            }
        }

        // 将轴点元素放入
        array[begin] = pivot;
        // 返回轴点元素的位置
        return begin;
    }
}

尝试对时间复杂度为 $O(nlogn)$ 的三个排序方式进行测试。生成 5 万个随机数，范围是 $[1, 50000]$，方法耗时如下：

可以看到快速排序是很优秀的，当然不同的硬件、不同的序列可能会导致这三种排序的耗时发生变化。

1.5 复杂度与稳定性

最好的情况

如果轴点左右元素数量比较均匀（各占一半）的情况下，就是最好的情况。

快速排序用了递归，可以像分析归并排序的时间复杂度一样，使用递推公式来计算快速排序的时间复杂度。

得到的递推公式跟分析归并排序时得到的递推公式一样。在最好情况下，快速排序的时间复杂度为 $O(nlogn)$。

最坏的情况

如果轴点左右元素数量极度不均匀，那就是最坏的情况。

那么在这种情况下的时间复杂度是多少呢？

根据递推公式，最坏情况下的时间复杂度是 $O(n^2)$。

降低最坏情况出现概率

既然最坏情况下时间复杂度这么高，那有什么解决的办法吗？

为了降低最坏情况的出现概率，一般采取的做法是 随机选择轴点元素。

简单来说，可以用 begin 位置的元素与当前序列中除 begin 位置外的其他元素进行交换。

代码修改也很简单，只需要在 pivot() 方法最开始的位置添加一句代码就可以实现随机选择轴点位置。

/**
 * 构造出 [begin, end) 范围的轴点元素
 *
 * @param begin 序列开始位置索引
 * @param end   序列长度
 * @return 轴点元素的最终位置
 */
private int pivot(int begin, int end) {
    // 随机选择一个元素跟begin位置进行交换
    swap(begin, begin + (int) (Math.random() * (end - begin)));

    // 备份 begin 位置的元素
    E pivot = array[begin];
    // end 指向最后一个元素
    end--;
    while (begin < end) {
        while (begin < end) {
            if (cmp(pivot, array[end]) < 0) { // 右边元素 > 轴点元素
                end--;
            } else { // 右边元素 <= 轴点元素
                array[begin++] = array[end];
                // 赋值后换方向遍历
                break;
            }
        }

        while (begin < end) {
            if (cmp(pivot, array[begin]) > 0) { // 左边元素 < 轴点元素
                begin++;
            } else { // 左边元素 >= 轴点元素
                array[end--] = array[begin];
                // 赋值后换方向遍历
                break;
            }
        }
    }

    // 将轴点元素放入
    array[begin] = pivot;
    // 返回轴点元素的位置
    return begin;
}

总结

• 最好时间复杂度为 $O(nlogn)$

• 最坏时间复杂度为 $O(n^2)$

• 由于递归调用的缘故，空间复杂度为 $O(logn)$

• 快速排序属于不稳定排序（从轴点构造过程也可以看出来）

1.6 轴点相等元素

在前面编写的代码中，确认轴点（获取轴点位置）时，有一段下图所示的代码：

圈出的代码中不含相等判断，就是说当选中元素与轴点相等时，会将选中元素赋值到另一边的子序列中。

从上图中可以看到，如果序列中的所有元素都与轴点元素相等，利用当前的算法实现，轴点元素可以将序列分成 2 个 均匀 的子序列。

拓展思考

如果将 cmp() 位置的判断分别改成 >= 、<= 会起到什么效果呢？

添加相等判断后，如果选中元素与轴点相等时，直接改变索引，不进行赋值转向。

添加相等判断后，轴点元素分割出来的子序列极其不均匀，导致出现最坏的时间复杂度 $O(n^2)$。

使用快速排序对 1w 个相同的数进行排序：

第一种是未添加相等判断的，第二种是添加了相等判断的。

添加前后耗时相差甚远，后者耗时近乎是前者的 40 倍。

如果进一步扩大数据规模，比如对 5w 个相等的数进行快速排序，第二种情况甚至可能出现StackOverflowError。

在实现快速时， 不要在比较元素时添加相等判断。

1.7 三路快排

三路快排，Three-way Quick Sort，是对普通快速排序算法的一种改进。

优势

在一般情况下，使用普通快速排序选择的基准恰好可以将序列中的元素对半分时，快速排序的时间复杂度为 $O(nlogn)$。

当序列中存在大量重复元素，甚至所有的元素都一样时，此时使用普通快速排序会导致基准两边的元素数量划分不平衡，时间复杂度退化成 $O(n^2)$。此时如果使用三路快排，能够将重复元素集中在同一个区间内，使得元素划分更加均匀，减少递归次数。

原理

三路快排相比于普通快速排序，就是将序列划分为三部分：

1. 小于基准元素的区间
2. 等于基准元素的区间
3. 大于基准元素的区间

之后对小于、大于基准元素的区间分别进行递归排序。

那么现在的问题就变成了怎么将序列划分为三部分，在 75. 颜色分类 一题中就需要实现类似的逻辑：

• 使用两个指针 i 和 j，最初 i 指向序列的第一个元素，j 指向序列的最后一个元素。除此之外，还需要一个指针 p 用来遍历序列，最初 p 也指向序列的第一个元素。
• 当 p 指向的元素小于基准值时，交换 p 与 i 指向的元素，之后 p 和 i 还要向前移动一位；
• 当 p 指向的元素大于基准值时，交换 p 与 j 指向的元素，之后 j 向前移动一位。注意，此时的 p 要保持不动，因为与 j 交换后，p 新指向的元素的大小关系还没判定，它可能恰好等于基准，也可能大于或者小于基准；
• 当 p 指向的元素等于基准值时，直接将 p 向前移动一位；
• 重复上述过程，直到 p 与 j 相遇。

代码实现

public class ThreeWayQuickSort<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        sort(0, array.length);
    }

    /**
     * 对 [begin, end) 范围的元素进行快速排序
     *
     * @param begin 序列开始位置索引
     * @param end   序列长度
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) return;

        // 随机选择一个元素跟 begin 位置进行交换
        swap(begin, begin + (int) (Math.random() * (end - begin)));

        E pivot = array[begin];
        int i = begin;
        int p = begin + 1;
        int j = end;

        while (p < j) {
            int cmp = cmp(array[p], pivot);
            if (cmp < 0) {
                swap(i++, p++);
            } else if (cmp > 0) {
                swap(p, --j);
            } else {
                p++;
            }
        }

        sort(begin, i);
        sort(j, end);
    }
}

2. 希尔排序

2.1 概念介绍

希尔排序（Shell Sort），由 唐纳德·刘易斯·希尔（Donald Lewis Shell） 在 1959 年提出。

希尔排序与前面的排序算法不同，希尔排序把序列看作一个 矩阵，分成 m 列，逐列进行排序：

• m 从某个整数逐渐减为 1
• 当 m 为 1 时，整个序列将完全有序

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

矩阵的列数取决于步长序列（step sequence）：

• 比如，如果步长序列为 $\{1, 5, 19, 41, 109\}$，就代表依次分成 109 列、41 列、19 列、5 列、1 列进行排序
• 不同的步长序列，执行效率也不同

2.2 排序实例

希尔本人给出的步长序列计算公式是 $\frac{n}{2^k}$ ，比如 n 为 16 时，步长序列为 $\{1, 2, 4, 8\}$。

如果对下面这个序列进行升序排序：

分成 8 列进行排序：

分成 4 列进行排序：

分成 2 列进行排序：

分成 1 列进行排序：

上面的排序过程中，最后一步是将每个元素独自形成一列进行排序，那么为什么不一开始就分成一列进行排序，前面的分列排序岂不是显得很多余？

其实并不是，从 8 列变为 1 列的过程中，逆序对的数量在不断减少。

希尔排序底层一般使用插入排序对每一列进行排序，因此也有很多资料认为希尔排序是插入排序的改进版。

插入排序的时间复杂度与逆序对的数量成正比关系。

上述给出的示例过于理想，元素数量恰好是 2 的次幂，如果元素数量不是 2 的幂呢？

假设有 11 个元素，步长序列是 $\{5, 2, 1\}$，分成 5 列进行排序，则有：

假设元素在第 $col$ 列、第 $row$ 行，步长（总列数）是 $step$：

• 那么这个元素在数组中的索引是 $col + row \times step$
• 比如 9 在排序前是第 2 列、第 0 行，那么它排序前的索引是 $2 + 0 \times 5 = 2$
• 比如 4 在排序前是第 2 列、第 1 行，那么它排序前的索引是 $2 + 1 \times 5 = 7$

2.3 编码实现

首先根据希尔给出的步长序列计算公式创建一个步长序列。

获得步长序列后，对原数列进行分列，然后进行排序，比如：

上图红色粗体数字表示列数，对每列的数据进行排序后可以得到右边的结果。

针对每一列进行的排序，可以使用 插入排序 来实现。

/**
 * @author 默烦
 * @date 2020/8/16
 */
public class ShellSort<E extends Comparable<E>> extends Sort<E> {

    @Override
    protected void sort() {
        List<Integer> stepSequence = shellStepSequence();
        for (Integer step : stepSequence) {
            sort(step);
        }
    }

    /**
     * 分成 step 列进行排序
     *
     * @param 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 < array.length; begin += step) {
                int cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur - step);
                    cur -= step;
                }
            }
        }
    }

    /**
     * 获取步长序列
     */
    private List<Integer> shellStepSequence() {
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;
        while ((step >>= 1) > 0) {
            stepSequence.add(step);
        }
        return stepSequence;
    }
}

2.4 复杂度与稳定性

最好情况是步长序列只有 1 ，且序列几乎有序，此时时间复杂度为 $O(n)$。

最坏的时间复杂度为 $O(n^{\frac{4}{3}}) \sim O(n^2)$，见下文分析。

平均时间复杂度取决于步长序列。

希尔排序采取原地排序，没有依赖额外存储空间也没有递归调用，因此空间复杂度为 $O(1)$。

希尔排序属于 不稳定排序（从分列排序示意图可以看出来）。

希尔排序是逐列排序的，其稳定性无法控制，也无法通过先前的稳定性测试代码测试出来，为了打印结果的准确，需要修改稳定性判断 isStable() 方法：

private boolean isStable() {
    if (this instanceof SelectionSort) return false;
    if (this instanceof ShellSort) return false;
    Student[] students = new Student[20];
    for (int i = 0; i < students.length; i++) {
        // 创建有序的序列
        students[i] = new Student(i * 10, 10);
    }
    sort(((E[]) students)); // 进行排序
    for (int i = 1; i < students.length; i++) {
        int score = students[i].score;
        int prevScore = students[i - 1].score;
        // 检查序列顺序是否发生改变
        if (score != prevScore + 10) return false;
    }
    return true;
}

生成 3w 个随机数，范围 $[1, 30000]$，方法耗时如下：

2.5 步长序列

根据希尔本人给出的步长序列计算公式，最坏情况时间复杂度为 $O(n^2)$：

private List<Integer> shellStepSequence(int count) {
    List<Integer> stepSequence = new ArrayList<>();
    int step = count;
    while ((step >>= 1) > 0) {
        stepSequence.add(step);
    }
    return stepSequence;
}

随着科学家们的研究，目前已知的最好的步长序列计算公式的最坏情况时间复杂度为 $O(n^{\frac{4}{3}})$，这是由 Robert Sedgewick 在 1986 年提出的。

将上述代码替换到先前的实现中，其它代码不变：

@Override
protected void sort() {
    // 根据元素数量算出步长序列
    List<Integer> stepSequence = sedgewickStepSequence();
    // 按步长序列划分进行排序
    for (Integer step : stepSequence) {
        sort(step); // 按step进行排序
    }
}

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 >= array.length) break;
        stepSequence.add(0, step);
        k++;
    }
    return stepSequence;
}