从今天起，与「排序」一刀两断

感谢官方置顶推荐 🎉😄。

• 可在作者的 github仓库 中获取本文和其他文章的 markdown 源文件及相关代码。

• 欢迎评论或仓库 PR 指出文章错漏或与我讨论相关问题，我将长期维护所有文章。

• 所有文章均用 Typora 完成写作，可使用 Typora 打开文章 md 文件，以获得最佳阅读体验。

⚠️ ⚠️ ⚠️ 本文巨长，全文两万五千余字，尝试彻底解析十大排序算法并给出相应实现。

❗️ 【NEW】 ❗️

• 9-15: 红黑树从入门到看开

$keywords$ :

三种元素交换方法 / 排序稳定性分析 / 排序复杂度分析 / 冒泡排序 / 选择排序 / 插入排序 / 希尔排序 / shell增量 / Hibbard增量 / Knuth增量 / 逆序数 / 归并排序 / 自顶向下 / 自底向上 / 原地与非原地 / 手摇算法 (三重反转) / 快速排序 / 非递归与递归快速排序 / 首位轴 / 三数取中轴 / 随机轴 / 双轴快排 / 堆排序 / 堆化方法 / 下滤方法 / 计数排序 / 稳定版计数排序 / 非稳定版计数排序 / 基数排序 / 基于计数排序的基数排序 / 不基于计数排序的基数排序 / 桶排序 / 决策树

前几天在讨论区上发布的二分查找和并查集文章反馈良好，这让我进一步相信基础知识的总结和分享确实很有一部分受众，于是趁热打铁，连夜推出本文。我(几乎)可以肯定，你在别处(基本上)看不到比本文更深入更广泛地网罗「十大排序」方方面面的文章，如果有，我就把这句话划掉。

「排序」十分基础，但内容庞杂，网上做全面介绍的资料不可谓不多，但我所看过的材料，总是在这一处或那一处上有所遗憾。比如复杂度缺少证明，比如优化版本未给出，比如缺少便于理解的图示，或者干脆就是到处复制粘贴错误百出的公众号引流文等等等等。因此上作者试图（企图）在「面试」这一层面上，彻底对排序做一个了断，使得面试官(几乎)不可能问得比本文内容更深更广（如果你是面试官，我劝你别看，我看你别劝👊😅）。

本文设想的读者应当是初学排序的同学，以及想对「排序」做一点查漏补缺工作的朋友，比如你突然想不起「双轴快排」该如何实现（对你竟然想要徒手实现双轴快排，我起立致敬🫡），或者「计数排序」稳不稳定，又或者「自底向上归并」该怎么写，你都可以在文中找到相应的答案。不过即便你就是纳闷，“不就是「排序」吗，自己随便看看不就好了，有什么好说的，还搞得这么煞有介事”，也十分欢迎你给出一些指导意见。

本文标题意在表达作者的一种希望，即看完本文，读者觉得确实有些帮助，甚或令七尺男儿拍案，以至于 「想嫁」 的心都有了，那就算对得起作者案头那把 键帽斑驳的双飞燕键盘 了。

发文的本心首要是向大家学习，其次是分享(一点微不足道)的心得。仍旧希望大家不吝赐教，你所指出的每一个错误，我都会 立即更正 。

本文主要内容（特色）如下：

• 内容 (应该还算) 全面。 具体如下。

  • 给出 $swap$ 的三种实现。

  • 给出十大排序中后面贴出的思维图所列的所有实现。

  • 所有代码均经过验证，注释关键语句，力求所见即所得，贴到IDE上就能跑。

  • 给出十大排序的所有稳定性和时空复杂度结论和分析证明。

  • 在「希尔排序」中讨论了逆序数。

  • 在「归并排序」中分析了 自顶向下/自底向上/原地/非原地 各情形排序过程，并给出各自的实现代码。

  • 在「归并排序」中讨论了「手摇算法」。

  • 在「快速排序」中讨论了三种基于不同轴选择的单轴快排（首位轴/随机轴/三数取中轴）并给出相应实现代码。分析给出了利用栈实现的迭代方式的快排。给出并逐行分析了「双轴快排」的代码。

  • 讨论了「计数排序」的稳定性。

  • 分别给出了基于计数排序和不基于计数排序的「基数排序」实现。

  • 从「决策树」角度分析并证明了基于「比较」的排序时间复杂度下界为$O(nlogn)$。

  • 贴出「Stiring公式」的详细证明文章链接。

• 叙述 (应该还算) 准确。 本文力求言必有据，所有性质，包括各类排序的稳定性，时空复杂度等关键信息，或给出例子，或给出图示，或严格证明，总之尽力拒绝模糊。

• 制作 (应该还算) 精良。 公式一概以 $\text{LATEX}$ 编辑。有多处方便记忆的汇总表格。有大量图示，动图静图，有助于理解之处尽附详图。

yuki的其他文章如下，欢迎阅读指正！

如下所有文章同时也在我的 github 仓库 中维护。

[2022-11-22]

• 更换了「冒泡排序」中「冒泡界排序」的实现 (换了一种更容易理解的写法)。
• 全文有多处调整。

[2022-10-19]

• 根据 @strange-antonellipd4 (God Man) 的建议，新增了基于 Sedgewick 增量的希尔排序实现。

1. 十大排序分类

2. 复杂度和稳定性一览

3. 三种交换方法

4. 冒泡排序

   1. 算法描述

   2. 优化

   3. 复杂度分析

   4. 代码

      1. 提前结束优化
      2. 冒泡界优化

5. 选择排序

   1. 算法描述

   2. 双元选择优化

   3. 复杂度分析

   4. 代码

      1. 单元选择排序
      2. 双元选择排序

6. 插入排序

   1. 算法描述

   2. 折半插入优化

   3. 复杂度分析

   4. 代码

      1. 简单插入排序
      2. 折半插入排序

7. 希尔排序

   1. 算法描述

   2. 复杂度分析

   3. 逆序数

   4. 代码

      1. Shell增量
      2. Hibbard增量
      3. Knuth增量
      4. Sedgewick增量

8. 归并排序

   1. 算法描述

   2. 自顶向下和自底向上

   3. 原地归并

   4. 复杂度分析

      1. 自顶向下非原地
      2. 自顶向下原地
      3. 自底向上非原地 & 自底向上原地
      4. 总结

   5. 代码

      1. 自顶向下非原地归并
      2. 自顶向下原地归并
      3. 自底向上非原地归并
      4. 自底向上原地归并

9. 快速排序

   1. 算法描述

      1. 主轴的选取

   2. 非递归单轴快排(利用栈迭代)

   3. 双轴快排

   4. 复杂度分析

   5. 代码

      1. 单轴快排递归实现

         1. 首位轴
         2. 三数取中轴
         3. 随机轴

      2. 单轴快排迭代实现(利用栈)

         1. 首位轴
         2. 三数取中轴
         3. 随机轴

      3. 双轴快排

10. 堆排序

    1. 算法描述

       1. 堆化方法 (heapify)
       2. 下滤方法(siftDown)

    2. 复杂度分析

    3. 代码

11. 计数排序

    1. 算法描述

    2. 稳定性优化

    3. 复杂度分析

    4. 代码

       1. 不稳定计数排序
       2. 稳定计数排序

12. 基数排序

    1. 算法描述

    2. 处理负数优化

    3. 复杂度分析

    4. 代码

       1. 以计数排序为基础
       2. 不以计数排序为基础

13. 桶排序

    1. 算法描述
    2. 复杂度分析
    3. 代码

14. 决策树

15. 实战应用

十大排序分类

复杂度和稳定性一览

稳定性：

所谓排序的稳定性，指的是对于存在相等元素的序列，排序后，原相等元素在排序结果中的 相对位置相比原输入序列不变 。例如 $nums=\{3,1,2_1,2_2\}$ ，数字 $2$ 出现了两次，下标表示他们出现的次序，若排序方法将 $nums$ 排成了 $\{1,2_2,2_1,3\}$ ，虽然排序结果正确，但改变了两个 $2$ 的相对位置。只有排序为 $\{1,2_1,2_2,3\}$ 我们才说该排序是稳定的。

如果排序对象只是数值，那么是否稳定没有区别。但若是对引用类型进行排序，排序依据是该类型中的某个可比较的数值字段，那么我们可能会希望该字段相同，但其他字段不同的元素相对位置相比原输入保持不变，这时候就需要稳定排序。

下列说明在正文相应章节均有更详细的描述。

※1冒泡: 输入数组已排序时最好。
※2选择: 时间复杂度与输入数组特点无关。
※3插入: 输入数组已排序时最好。
※4希尔: 复杂度取决于增量序列，两行分别为希尔增量，
    和Knuth增量的希尔排序。输入数组已排序时最好。
※5归并: 所列复杂度为「自顶向下非原地」版本。
    自顶向下/自底向上，非原地/原地的时间空间复杂度见该归并排序一节。
※6快速: 当输入数组有序，且总是选取第一个元素为主轴时，
    时间复杂度退化为O(n^2)。空间开销为递归深度。
※7堆: 原地堆排序空间复杂度为O(1)。输入数组所有数字相等时，
    时间复杂度为O(n)。
※8计数: k是计数数组大小。应用稳定性优化则稳定，否则不稳定。
    朴素版本空间复杂度为O(k)，稳定性优化版本空间复杂度为O(n + k)。
※9基数: d是最大数位数，k是计数数组大小，处理负数时k=19。
※10桶: 稳定性取决于桶内排序是否稳定。空间取决于桶使用数组还是容器，
    若采用数组为O(kn)，容器则为O(n)。所有元素放入同一个桶时复杂度最大。
    最坏时间复杂度取决于采用哪种桶内排序算法。

稳定性: 存在稳定和非稳定版本时，视作「稳定」。

三种交换方法

对于冒泡、选择、插入等采用比较和交换元素的排序方法，由于经常执行交换操作，通常将交换动作写为 $swap$ 方法，需要交换时调用。最常见 $swap$ 写法有如下三种：

1. 方法一: 利用一个临时数 $tmp$ 来交换 $arr[i]$ ，$arr[j]$ 。
2. 方法二: 利用 $arr[i]$ 和和 $arr[j]$ 的加减运算避免临时数 $tmp$ 的开销，但由于涉及到加减法可能导致数字 「提前溢出」 。
3. 方法三: 利用位运算中的 异或 运算，能够避免 $tmp$ 的开销且不会导致数字溢出。

需要特别注意的是， 「方法二」和「方法三」要避免 $i=j$ ，若 $i=j$ ，执行 $swap$ 后将导致该数字变为 0。实际上自我交换总是不必要的，因此应当保证 $swap$ 被调用时 $i!=j$，这样就无需 $if$ 语句了。

// 方法一: 利用临时数tmp
private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
// 方法二: 利用加减运算
private void swapCal(int[] arr, int i, int j) {
    if(i == j) return; // 若无法保证swapCal被调用时满足 i != j，则需有此句，否则i == j时此数将变为0
    arr[i] = arr[i] + arr[j]; // a = a + b
    arr[j] = arr[i] - arr[j]; // b = a - b
    arr[i] = arr[i] - arr[j]; // a = a - b
}
// 方法三: 利用异或运算
private void swapXOR(int[] arr, int i, int j) {
    if(i == j) return; // 若无法保证swapXOR被调用时满足 i != j，则需有此句，否则i == j时此数将变为0
    arr[i] = arr[i] ^ arr[j]; // a = a ^ b，也可写成 arr[i] ^= arr[j];
    arr[j] = arr[i] ^ arr[j]; // b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a， 也可写成 arr[j] ^= arr[i];
    arr[i] = arr[i] ^ arr[j]; // a = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b， 也可写成 arr[i] ^= arr[j];
}

冒泡排序

算法描述

对于要排序的数组，从第一位开始从前往后比较相邻两个数字，若前者大，则交换两数字位置，然后比较位向右移动一位。也就是比较 $arr[0]$ 和 $arr[1]$ ，若 $arr[0]>arr[1]$ ，交换 $arr[0]$ 和 $arr[1]$ 。接着比较位移动一位，比较 $arr[1]$ 和 $arr[2]$ ，直到比较到 $arr[n-2]和$ $arr[n-1](n=arr.length)$ 。第1轮从前到后的比较将使得最大的数字 冒泡 到最后，此时可以说一个数字已经被排序。每一轮的比较将使得当前未排序数字中的最大者被排序，未排序数字总数减 1。第 $arr.length-1$ 轮结束后排序完成。

如下动图展示了 $\{4,6,2,1,7,9,5,8,3\}$ 的冒泡排序过程（未应用优化）。

稳定性：稳定。

冒泡排序始终只交换相邻元素，比较对象大小相等时不交换，相对位置不变，故稳定。

优化

提前结束优化

当某一轮比较均未发生交换，说明排序已完成，可设置一个布尔值记录一轮排序是否有发生交换，若无则提前退出循环结束程序。

冒泡界优化

记录前一轮交换的最终位置，该位置之后的元素为已排序状态，下一轮的交换只需执行到该处。容易看出此优化包含了提前结束优化。见「代码」-「冒泡界优化」。

复杂度分析

时间复杂度：两层 $for$ 循环，第 1 轮比较 $n-1$ 次 $(n=arr.length)$ ，最后一轮比较 1 次。总比较次数为 $n\ast (n-1)/2$ 次，时间复杂度为 $O(n^2)$。当输入数组为已排序状态时，在应用提前结束优化的情况下，只需一轮比较，此时为最佳时间复杂度 $O(n)$。

空间复杂度：算法中只有常数项变量，$O(1)$。

代码

无优化的基本冒泡排序代码此处不列出。

提前结束优化

public int[] bubbleSort(int[] arr) {
    if (arr.length < 2) return arr;
    // n - 1轮次执行，当前 n - 1 个元素排好后，最后一个元素无需执行，故i < arr.length - 1
    for (int i = 0; i < arr.length - 1; i++) {
        // 本轮执行是否有交换的标志，若无则false，若有则true
        boolean swapped = false;
        // 每轮循环，通过依次向右比较两个数，将本轮循环中最大的数放到最右
        for (int j = 1; j < arr.length - i; j++) {
            // 若左大于右则交换，并将swapped置为true
            if (arr[j - 1] > arr[j]) {
                swap(arr, j - 1, j);
                swapped = true;
            }
        }
        // 若无交换，表示当前数组已完全排序，退出大循环
        if (!swapped) break;
    }
    return arr;
}

冒泡界优化

public int[] bubbleSort(int[] arr){
    if(arr.length < 2) return arr;
    // 上一轮最后交换的下标，即发生 swap(num, i, j) 时的 i
    int lastSwappedIdx = arr.length - 1;
    // 若上一轮最后交换的下标 > 0 ，继续
    while(lastSwappedIdx > 0){
        // 当前轮次发生交换的下标
        int curSwappedIdx = 0;
        // 每一轮 i 只需要考察到 lastSwappedIdx 前一位
        for(int i = 0; i < lastSwappedIdx; i++){
            if(arr[i] > arr[i + 1]){
                swap(arr, i, i + 1);
                curSwappedIdx = i; // 更新 curSwappedIdx
            }
        }
        // 若当前轮次未发生交换，则 lastSwappedIdx = 0 ，则在下一次 while 判断时退出，完成排序
        lastSwappedIdx = curSwappedIdx;
    }
    return arr;
}

选择排序

算法描述

对于要排序的数组，设置一个 $minIdx$ 记录最小数字下标。先假设第 1 个数字最小，此时 minIdx = 0 ，将 $arr[minIdx]$ 与后续数字逐一比较，当遇到更小的数字时，使 $minIdx$ 等于该数字下标，第1轮比较将找出此时数组中最小的数字。找到后将 $minIdx$ 下标的数字与第 1 个数字交换，此时称一个数字已被排序。然后开始第2轮比较，令 minIdx = 1，重复上述过程。每一轮的比较将使得当前未排序数字中的最小者被排序，未排序数字总数减 1。第 $arr.length-1$ 轮结束后排序完成。

如下动图展示了 $\{4,6,2,1,7,9,5,8,3\}$ 的选择排序过程（单元选择）。

微优化：在交换前判断 $minIdx$ 是否有变化，若无变化则无需交换。当数组大致有序时，能够减少无效交换带来的开销。

稳定性：不稳定。

存在跨越交换。找到本轮次最小值之后，将其与本轮起始数字交换，此时若中间有与起始元素同值的元素，将打破稳定性。

例:　7 7 2 。第一轮交换第一个 7 和 2，则两个 7 位置关系改变。

双元选择优化

在遍历寻找最小值下标 $minIdx$ 时，可以同时寻找最大值下标 $maxIdx$ ，这样就可以一轮遍历确定两个元素的位置，遍历次数减少一半，但每轮次的操作变多，因此该优化 只能少量提升选择排序的速度 (复杂度介于单元选择排序复杂度及其一半之间，只有系数上的区别)。

复杂度分析

时间复杂度：两层 $for$ 循环，第1轮比较 $n-1$ 次 ( n = arr.length ) ，最后一轮比较 1 次。总比较次数为 $n\ast (n-1)/2$ 次，时间复杂度为 $O(n^2)$。 双元选择优化版本也是 $O(n^2)$。

冒泡排序和选择排序的比较次数均为 $O(n^2)$，但选择排序的交换次数是 $O(n)$，而冒泡排序的平均交换次数仍然是二次的。

空间复杂度：算法中只有常数项变量，$O(1)$。

代码

单元选择排序

public int[] selectionSort(int[] arr) {
    if (arr.length < 2) return arr;
    for (int i = 0; i < arr.length - 1; i++) { // 当前 N-1 个元素排好后，最后一个元素无需执行，故 i < arr.length - 1
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) { // 找到本轮执行中最小的元素，将最小值下标赋值给 minIdx
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        swap(arr, i, minIdx); 
    }
    return arr;
}

双元选择排序

public int[] selectionSortDouble(int[] arr) {
    if (arr.length < 2) return arr;
    int n = arr.length;
    for (int i = 0; i < n - 1 - i; i++) { // 每轮确定两个数字，因此上界也会动态变化
        int minIdx = i, maxIdx = i;
        for (int j = i + 1; j < n - i; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
            if(arr[j] > arr[maxIdx]) maxIdx = j;
        }
        if(minIdx == maxIdx) break; // 若本轮最大值等于最小值，说明未排序部分所有元素相等，无需再排序
        swap(arr, i, minIdx); 
        if(maxIdx == i) maxIdx = minIdx; // 在交换 i 和 minIdx 时，有可能出现 i 即 maxIdx 的情况，此时需要修改 maxIdx 为 minIdx
        swap(arr, n - 1 - i, maxIdx); 
    }
    return arr;
}

插入排序

算法描述

对于待排序数组，从第 2 个元素开始 (称作插入对象元素) ，比较它与之前的元素 (称作比较对象元素) ，当插入对象元素小于比较对象元素时，继续往前比较，直到不小于 (≥) 比较对象，此时将插入对象元素插入到该次比较对象元素之后。重复这个插入过程直到最后一个元素作为插入对象元素完成插入操作。

如下 动图 展示了 $\{4,6,2,1,7,9,5,8,3\}$ 的简单插入排序过程。

稳定性：简单插入和折半插入 (二分插入) 排序是稳定的。

对于大小相同的两个数字，简单插入和折半插入均使得后来的数字靠右放置 （因为条件是 ≥ ），因此不会改变其相对位置。

折半插入优化

注意到插入排序的每一轮向前插入都使得该元素在完成插入后，从第一个元素到该元素是排序状态（指这部分的相对排序状态，在它们中间后续可能还会插入其他数字），利用这一点，对一个新的插入对象向前执行折半插入，能够显著减少比较的次数。另一种优化是增量递减插入排序，也叫 希尔排序 ，将在希尔排序章节中介绍。

折半插入的关键在于找到插入位置，折半过程代码如下。这实际上是二分查找「模版一」中的「小于等于」情形。如果你尚不能熟练且准确地写出如下代码，这说明你对二分查找写法不熟悉，推荐阅读我写的这篇全面解析二分查找的文章: 二分查找从入门到入睡。

// 模版一，小于等于情形
private int binarySearch(int[] arr, int l, int r, int target){
    while(l <= r){
        int c = l + (r - l) / 2;
        if(arr[c] <= target) l = c + 1;
        else r = c - 1;
    }
    return l;
}

复杂度分析

时间复杂度：两层 $for$ 循环，外层总轮次为 $n-1$ 轮 ( n = arr.length ) ，当原数组逆序时，移动次数为 $n\ast (n-1)/2$ 次，最坏时间复杂度为 $O(n^2)$，平均时间复杂度同为 $O(n^2)$。当原数组已基本有序时，接近线性复杂度 $O(n)$。例如原数组已完全排序，则算法只需比较 n - 1 次。

※ 折半插入总的查找(比较)次数虽为 $O(nlogn)$，但平均移动 (每轮移动一半的数字) 次数仍是 $O(n^2)$。

空间复杂度：算法中只有常数项变量，$O(1)$。

代码

简单插入排序

// 简单插入排序：内层用 for
public int[] insertionSortUseWhile(int[] arr) {
    if (arr.length < 2) return arr;
    for (int i = 1; i < arr.length; i++) {
        int target = arr[i], j = i - 1;
        for (; j >= 0; j--) {
            if(target < arr[j]) arr[j + 1] = arr[j];
            else break;
        }
        arr[j + 1] = target;
    }
    return arr;
}

// 简单插入排序，内层用 while
public int[] insertionSort(int[] arr) {
    if (arr.length < 2) return arr;
    for (int i = 1; i < arr.length; i++) { // N-1轮次执行
        int target = arr[i], j = i - 1;
        while (j >= 0 && target < arr[j]) { 
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = target; // 若发生移动，此时的插入对象数字≥j位置的数字，故插入位置为j + 1，若未移动也成立，无需判断
    }
    return arr;
}

折半插入排序

public int[] insertSortBinary(int[] arr) {
    if (arr.length < 2) return arr;
    // n - 1 轮次执行
    for (int i = 1; i < arr.length; i++) {
        // 通过二分查找得到插入位置
        int target = arr[i];
        int pos = binarySearch(arr, 0, i - 1, target);
        for (int j = i; j > pos; j--) { // 移动
            arr[j] = arr[j - 1];
        }
        arr[pos] = target; // 插入
    }
    return arr;
}

希尔排序

算法描述

希尔排序 是 简单插入排序的改进 ，它基于以下事实。

1. 简单插入排序对 排序程度较高的序列 有较高的效率。假设初始序列已完全排序，则每一轮均只需比较一次，将得到 $O(n)$ 的线性复杂度，冒泡排序和选择排序做不到这一点，均仍需 $O(n^2)$ 次比较 (冒泡排序在应用提前结束优化后可以做到) 。

2. 简单插入排序每次比较最多将数字移动一位，效率较低。

Donald Shell 在 1959 年发表的 论文 中，针对这两个事实，提出如下方法。对原待排序列中相隔 $gap$ 的数字执行简单插入排序，然后缩小 $gap$，对新的 $gap$ 间隔的数字再次执行简单插入排序。以一种规则减少 $gap$ 的大小，当 $gap$ 为 1 时即简单插入排序，因此希尔排序也称作 增量递减排序。希尔在论文中提出的增量序列生成式为 $n/2^k$，k = 1, 2, 3, ... ，例如 n = 11，则增量序列为 $\{1,2,5\}$ 。在讨论希尔排序时，可将其称为 Shell增量，另有更优的 Hibbard增量、Knuth增量、Sedgewick增量 等。

程序开始时 $gap$ 较大，待排元素较少，因此排序速度较快。当 $gap$ 较小时，基于第一点，此时待排序列已大致有序，排序效率接近线性复杂度。因此能够期待希尔排序复杂度将优于 $O(n^2)$。详细见「复杂度分析」。

稳定性：不稳定。

gap > 1 时，跨越 $gap$ 的插入可能会改变两个相同值元素的位置关系。例如 $\{0,1,4,3_1,3_2,5,6\}$ ，当 gap = 2 时，对 $\{0,4,3,6\}$ 简单插入排序后得到 $\{0,1,3_2,3_1,4,5,6\}$ ，原数组中的两个 3 的相对位置发生了变化。

复杂度分析

时间复杂度：希尔排序的时间复杂度与增量序列的选择有关。最优复杂度增量序列尚未明确。

Shell增量 (Shell, 1959): $n/2^k$，最坏时间复杂度 $\Theta (n^2)$。

Hibbard增量 (Hibbard, 1963)：$\{1,3,7,15,...\}$ ，即 $2^k-1,k=1,2,3,...$ ， 最坏时间复杂度 $\Theta (n^{\frac{3}{2}})$。

Knuth增量 (Knuth, 1971)：$\{1,4,13,40,...\}$ ，即 $(3^k-1)/2，k=1,2,3,...$ ，最坏时间复杂度 $\Theta (n^{\frac{3}{2}})$。

Sedgewick增量 (Sedgewick, 1982): $\{1,8,23,77,\mathrm{281...}\}$ ，即 $4^k+3\ast 2^{k-1}+1$ (最小增量 1 直接给出)，$k=1,2,3,...$ ，最坏时间复杂度 $\Theta (n^{\frac{4}{3}})$。

平均 / 最坏复杂度的证明需要借助数论和组合数学，本文不做讨论。

当输入数组已排序时，达到最好时间复杂度。

空间复杂度：算法中只有常数项变量，$O(1)$ 。

逆序数

希尔排序是较早出现的 突破二次复杂度 的排序算法，下面从 逆序数 的角度来直观地证明为何希尔排序能够突破二次复杂度。

以数值从小到大为「顺序」，则在一个排列中，如果任意一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个 逆序，一个排列中逆序的总数就称为这个排列的 逆序数。排序的过程就是不断减少逆序数 直到逆序数为 0 的过程。

回顾冒泡排序和简单插入排序，算法的每一次交换，都只交换相邻元素（简单插入排序中元素每次右移也看作交换），因此每次交换只能减少一个逆序。冒泡排序和简单插入排序的元素平均交换次数均为 $O(n^2)$， 也即逆序数 (或逆序数减少次数) 为 $O(n^2)$。 如果能跨越多个数字进行交换，则可能一次减少多个逆序。在选择排序中，每轮选到最小元素后的交换即是跨越多个元素的，交换次数 (减少逆序数的操作) 为 $O(n)$，要少于冒泡和简单插入排序，只是因为比较次数仍是 $O(n^2)$， 所以整体复杂度为 $O(n^2)$。

现在来分析跨越多个元素的交换如何减少逆序数，假设 $arr[i]>arr[j],i<j$。对于任意的 $arr[k](i<k<j)$：

1. 若 $arr[k]<arr[j]$ ，交换 $arr[i]和$arr[j] 后，三者的逆序数从 2 变为 1。

2. 若 $arr[k]>arr[i]$ ，交换 $arr[i]和$arr[j] 后，三者的逆序数从 2 变为 1。

3. 若 $arr[i]>arr[k]>arr[j]$，交换 $arr[i]$ 和 $arr[j]$ 后，三者的逆序数从 3 变为 0 。

$arr[k]=arr[i]$ 或 $arr[k]=arr[j]$ 的情况一样，都使得三者逆序数从 2 变为 1 ，下图省略。

对 $arr[i]$ 和 $arr[j]$ 的逆序消除，使得逆序 至少 减少一次，并 有机会减少大于一次的逆序 (情况3)，因此能够以比 $n^2$ 低阶的次数消除所有逆序。

实际上归并排序，快速排序，堆排序均实现了 长距离交换元素，使得复杂度优于 $O(n^2)$。

代码

从下列实现可看出，不同增量的代码仅 $gap$ 初始化和增量递减上有差异，此差异反映了各自不同的增量。

Shell增量

// 希尔排序：采用Shell增量 N / 2^k
public int[] shellSortShell(int[] arr) {
    if (arr.length < 2) return arr;
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) { // gap 初始为 n/2，缩小gap直到1
        for(int start = 0; start < gap; start++) { // 步长增量是gap，当前增量下需要对gap组序列进行简单插入排序
            for (int i = start + gap; i < n; i += gap) { // 此for及下一个for对当前增量序列执行简单插入排序
                int target = arr[i], j = i - gap;
                for (; j >= 0; j -= gap) { 
                     if (target < arr[j]) arr[j + gap] = arr[j];
                     else break; 
                }                 
                arr[j + gap] = target;
            }
        }
    }
    return arr;
}

尤其需要注意的是，网上有大量错误的「Shell增量」希尔排序写法写成如下形式，gap直接从 n / 2开始，虽然gap减小到1时变成简单插入排序，可以得到正确结果，但增量序列并不一定满足「Shell增量」的定义，实际上只有当n为2的整数次幂时才满足。 删除内容为作者早先的错误认识，实际上 $Shell$ 增量并未要求增量序列必须为 $\{1,2,4,8,16,...\}$ ，而是无论 $n$ 等于多少，都直接从 $n/2$ 开始，不断除 2 直到 gap = 1。详情可参考 Donald Shell 原论文 A High-Speed Sorting Procedure。原论文 TABLE 1 给出了长度为 11 的序列 $\{3,11,6,4,9,5,7,8,10,2,1\}$，首个 $gap$ 为 gap = 11 / 2 = 5，接着是 gap = 2 ，gap = 1。

Hibbard增量

// 希尔排序： 采用Hibbard增量 {1, 3, 7, 15,...}
public int[] shellSortHibbard(int[] arr) {
    if (arr.length < 2) return arr;
    int n = arr.length, gap = 1; 
    while (gap < n / 2) gap = gap * 2 + 1; // 初始化gap (Hibbard增量序列)
    for (; gap > 0; gap /= 2) { // 缩小gap直到1
        for(int start = 0; start < gap; start++) { // 步长增量是gap，当前增量下需要对gap组序列进行简单插入排序
            for (int i = start + gap; i < arr.length; i += gap) { // 此for及下一个for对当前增量序列执行简单插入排序
                int target = arr[i], j = i - gap;
                for (; j >= 0; j -= gap) { 
                     if (target < arr[j]) arr[j + gap] = arr[j];
                     else break; 
                }                 
                arr[j + gap] = target;
            }
        }
    }
    return arr;
}

Knuth增量

// 希尔排序： 采用Knuth增量 {1, 4, 13, 40,...}
public int[] shellSortKnuth(int[] arr) {
    if (arr.length < 2) return arr;
    int n = arr.length, gap = 1; 
    while (gap < n / 3) gap = gap * 3 + 1; // 初始化gap (Knuth增量序列)
    for (; gap > 0; gap /= 3) { // 缩小gap直到1
        for(int start = 0; start < gap; start++) { // 步长增量是gap，当前增量下需要对gap组序列进行简单插入排序
            for (int i = start + gap; i < arr.length; i += gap) { // 此for及下一个for对当前增量序列执行简单插入排序
                int target = arr[i], j = i - gap;
                for (; j >= 0; j -= gap) { 
                     if (target < arr[j]) arr[j + gap] = arr[j];
                     else break; 
                }                 
                arr[j + gap] = target;
            }
        }
    }
    return arr;
}

Sedgewick增量

public int[] shellSortSedgewick(int[] arr) {
    if (arr.length < 2) return arr;
    int n = arr.length, gap = 1;
    List<Integer> gaps = new ArrayList<>();
    gaps.add(gap);
    for(int k = 1; gap < n; k++){ // 计算增量序列
        gap = (int) (Math.pow(4, k) + 3 * Math.pow(2, k - 1) + 1);
        gaps.add(gap);
    }
    for (int idx = gaps.size() - 1; idx >= 0; --idx) { // 缩小 gap 直到 1
        gap = gaps.get(idx);
        for(int start = 0; start < gap; start++) { // 步长增量是 gap ，当前增量下需要对 gap 组序列进行简单插入排序
            for (int i = start + gap; i < n; i += gap) { // 此 for 及下一个 for 对当前增量序列执行简单插入排序
                int target = arr[i], j = i - gap;
                for (; j >= 0; j -= gap) {
                    if (target < arr[j]) arr[j + gap] = arr[j];
                    else break;
                }
                arr[j + gap] = target;
            }
        }
    }
    return arr;
}

归并排序

算法描述

归并排序是 分治思想 的应用，即将原待排数组 递归或迭代 地分为左右两半，直到数组长度为 1，然后合并 ($merge$) 左右数组，在合并中完成排序。详细过程需结合代码理解，如下 动图 展示了 $\{4,6,2,1,7,9,5,8,3\}$ 的归并排序过程（自顶向下非原地）。合并过程采用 非原地 合并方法，即依次比较两部分已排序数组，将比较结果依次写入 新空间 中。后续会介绍一种称作 原地(in-place) 归并排序的改进，使得空间复杂度达到 常数级 (自底向上时，$O(1)$)。

如下树状图中的橙色线表示递归的轨迹（自顶向下递归归并排序）。

稳定性：稳定。

合并时的此判断中的等号 if(left[l_next] <= right[r_next])，保证了出现相等元素时，居左的元素总会被放在左侧，即排序是稳定的。

自顶向下和自底向上

可以通过 自顶向下 (top-down) 或 自底向上 (bottom-up) 的方式实现归并排序。

自顶向下 (top-down)：从输入数组出发，不断二分该数组，直到数组长度为1，再执行合并。适合用 递归 实现。

自底向上 (bottom-up)：从输入数组的单个元素出发，一一合并，二二合并，四四合并直到数组有序。适合用 迭代 实现。

后续给出 自顶向下原地 / 自顶向下非原地 / 自底向上原地 / 自底向上非原地 四种代码实现。

原地归并

前述归并排序，每一次合并都是将两部分待合并数组的比较结果写入一个与 $arr$ 等大小的临时数组 $tmpArr$ 中，写入后再将 $tmpArr$ 中的合并结果写回到 $arr$ 中。于是 $tmpArr$ 的空间开销即为该实现的空间复杂度，为 $O(n)$。通过一种 原地旋转交换 的方法（俗称手摇算法/内存反转算法/三重反转算法，英文社区一般称为 block swap algorithm），则只需要 $O(1)$ 的辅助空间（由于递归空间为 $O(logn)$，其总的空间复杂度仍为 $O(logn)$）。以下介绍旋转交换的实现方法。

以 456123 为例，欲将 456 和 123 交换位置转换为 123456，只需要执行三次旋转即可：

1. 旋转 456，得到 654
2. 旋转 123，得到 321
3. 旋转 654321 得到 123456

应用上述「手摇算法」对两个排序序列的「原地归并」过程如下。

1. 记左数组第一个数下标为 $i$ ，记右数组第一个数下标为 $j$ 。

2. $i$ 向后遍历，找到左数组中第一个 大于 右数组第一个数字 (即 $arr[j]$ ) 的数，此时 $arr[i]>arr[j]$ 。

3. 以 $index$ 暂存右数组第一个元素的下标 $index=j$ 。

4. 找到右数组中第一个 大于等于 $arr[i]$ 的数，记其下标为 $j$ 。此时必有 $[i,index-1]$ 下标范围序列 大于 $[index,j-1]$ 下标范围序列。

5. 通过三次翻转交换 $[i,index-1]$ 和 $[index,j-1]$ 序列 (指下标范围)，即依次翻转 $[i,index-1]$ ，翻转 $[index,j-1]$ ，翻转 $[i,j-1]$ 。

6. 重复上述过程直到不满足 (i < j && j <= r)

※ 第4步如果找「大于」而不是「大于等于」，对于数字数组排序，结果正确，但将 破坏稳定性。读者可自行验证。

以 $\{1,2,4,6,7\}$ 与 $\{3,5,8,9\}$ 两个已排序序列的合并为例，观察借助手摇算法实现原地归并的过程。

1. 在 $\{1,2,4,6,7\}$ 中找到第一个大于 3 的数 4 ，其下标为 2 ，$i=2$。$index=j=5$。在 $\{3,5,8,9\}$ 中找到第一个大于 $arr[i]=arr[2]=4$ 的数 5，其下标为 6，$j=6$ 。
2. 如上操作使得 $[0,i-1]$ 必是最小序列，$[index,j-1]$ 必小于 $arr[i]$ 。因此交换 $[i,index-1]$ 和 $[index,j-1]$（采用三次旋转完成交换），使得这部分序列在整个数组中有序。
3. 交换后，继续执行上述过程，直到不满足该条件 ：i < j && j <= r。

复杂度分析

自顶向下非原地

时间复杂度

每次减半后的左右两半对应元素的对比和赋值 ( tmpArr[h++] = arr[lh] <= arr[rh] ? arr[lh++] : arr[rh++]; ) 总是必须的，也即在每一层递归中 (这里的一层指的是 递归树 中的层) ，比较和赋值的时间复杂度都是 $O(n)$，数组规模减半次数为 $logn$，即递归深度为 $logn$，也即总共需要 $logn$ 次 $O(n)$ 的比较和赋值，时间复杂度为 $O(nlogn)$。

也可以这样求解。当 $n=1$ 时，排序只需常数时间，可以记为 $O(1)$。$n$ 个元素的归并排序时间由 $n/2$ 个元素的归并排序的两倍，再加上将两个 $n/2$ 大小的已排序数比较及合并的耗时得到。得到如下两个式子 (第2个式子加号右边的 $n$ 表示比较及合并的时间)。

对第二个式子，左右两边除以 $n$ ，得到

可以不断地将括号内的 $n$ 除以 2 (假设 $n$ 为 2 的整数次幂)，从 $T(n)/n$ 写到 $T(1)$ ，得到

将上述所有式子相加后得到如下，故复杂度为 $O(nlogn)$。

空间复杂度

递归深度为 $logn$，递归过程中需要一个长度为 $n$ 的临时数组保存中间结果，空间复杂度为 $O(n)$。

自顶向下原地

时间复杂度

该方式的时间复杂度计算参考了此篇文章。

当序列为 链表 时，手摇算法只需做如下指针调整即可（只做示意，非实际代码）。

双向链表时：
tmp = index.prev 
index.prev = i.prev
i.prev = j.prev
j.prev = tmp

单向链表时：
(i-1).next = index
(index-1).next = j
(j-1).next = i

对于长度为 $n$ 的序列，手摇算法操作元素个数至多不超过 $n/2$ 个 (由较短的一侧决定)，容易得到下述递推式。

由前述计算方法可复杂度为 $O(nlogn)$。

当序列为 数组 时，以 $\{1,3,5,7,...k\}$ 和 $\{2,4,6,8,...,n\}$ 的手摇合并为例，对于长度为 $n$ 的序列，一次手摇算法需要翻转大约一半的元素。例如第一次手摇，需翻转 $\{3,...,k\}$ 和 $\{2\}$ ( $\{2\}$ 只有一个元素，实际不翻转) 得到 $\{k,...,3\}$ 和 $\{2\}$ ，然后再翻转 $\{k,...,3,2\}$ 得到 $\{2,3,...,k\}$。下一次手摇对象是 $\{5,...,k\}$ 和 $\{4\}$ ，翻转元素个数相比上一次减少一个，可知完成 $\{1,3,5,7,...k\}$ 和 $\{2,4,6,8,...,n\}$ 的手摇合并所需要的对元素的翻转次数是 $c\ast n^2$ (等差数列求和，$c$ 是一常数)，于是有下列递推式。

仍沿用前述方法计算

其中 $k=logn$，由等比数列求和公式得到

故复杂度为 $O(n^2)$。

上述复杂度为 最坏及平均情形， 最好情形是输入数组已排序，则无需手摇，但序列长度为 $n$ 时需要的比较判断次数是 $n$，于是最好情形的递推式如下，复杂度为 $O(nlogn)$。

空间复杂度

递归深度为 $logn$，手摇算法仅需 $O(1)$ 的辅助空间，综合来看空间复杂度为 $O(logn)$。

自底向上非原地 & 自底向上原地

时间复杂度

同自顶向下非原地 / 原地的分析类似，只是程序运行过程从递归变为了迭代。

空间复杂度

自底向上非原地归并：迭代过程中需要一个长度为 $n$ 的临时数组保存中间结果，空间复杂度为 $O(n)$。

自底向上原地归并：手摇算法仅需 $O(1)$ 的辅助空间，其他空间开销均为常数级，空间复杂度为 $O(1)$。

总结

四种归并排序的时空复杂度总结如下（待排序序列是数组形式，不考虑链表形式）。

根据上述分析，原地相比非原地，空间消耗较少，采用 自底向上原地归并排序 时空间复杂度为常数级 $O(1$)，但需要 $O(n^2)$ 的时间复杂度。是一种以时间换空间的做法，通常空间不为瓶颈时，应采用 效率更高的非原地归并排序。

代码

自顶向下非原地归并

public int[] mergeSort(int[] arr) {
    if (arr.length < 2) return arr;
    int[] tmpArr = new int[arr.length];
    mergeSort(arr, tmpArr, 0, arr.length - 1);
    return arr;
}
// mergeSort 递归方法
private void mergeSort(int[] arr, int[] tmpArr, int l, int r) {
    if(l < r) {
        int c = l + (r - l) / 2;
        mergeSort(arr, tmpArr, l, c);
        mergeSort(arr, tmpArr, c + 1, r);
        merge(arr, tmpArr, l, c, r);
    }
}
// 非原地合并方法
private void merge(int[] arr, int[] tmpArr, int l, int c, int r) {
    int lh = l, rh = c + 1, h = l; // lh: left head, rh: right head, h: tmpArr head
    while (lh <= c && rh <= r) {
        tmpArr[h++] = arr[lh] <= arr[rh] ? arr[lh++] : arr[rh++];
    }
    while (lh <= c) tmpArr[h++] = arr[lh++]; // 左半边还有剩余，加入 tmpArr 末尾
    while (rh <= r) tmpArr[h++] = arr[rh++]; // 右半边还有剩余，加入 tmpArr 末尾
    for(; l <= r; l++) arr[l] = tmpArr[l]; // 将 tmpArr 拷回 arr 中
}

自顶向下原地归并

public int[] mergeSort(int[] arr) {
    if (arr.length < 2) return arr;
    mergeSort(arr, 0, arr.length - 1);
    return arr;
}
// mergeSort 递归方法
private void mergeSort(int[] arr, int l, int r) {
    if(l < r) {
        int c = l + (r  - l) / 2;
        mergeSort(arr, l, c);
        mergeSort(arr, c + 1, r);
        merge(arr, l, c, r);
    }
}
// 原地归并（手摇算法）
private void merge(int[] arr, int l, int c, int r) {
    int i = l, j = c + 1; // #1
    while(i < j && j <= r) {
        while(i < j && arr[i] <= arr[j]) i++; // #2
        int index = j; // #3
        while(j <= r && arr[j] < arr[i]) j++; // #4 注意是 arr[j] < arr[i]，即找到j使得arr[j] 为第一个大于等于 arr[i]值
        exchange(arr, i, index - 1, j - 1); // #5
    }
}
// 三次翻转实现交换
private void exchange(int[] arr, int l, int c, int r) {
    reverse(arr, l, c);
    reverse(arr, c + 1, r);
    reverse(arr, l, r);
}
// 原地翻转
private void reverse(int[] arr, int l, int r) {
    while(l < r) {
        swap(arr, l++, r--);
    }
}