插入排序¶

插入排序 | Linux C 编程一站式学习

插入排序 | Hello 算法

插入排序 | 维基百科

插入排序（Insertion Sort）的基本思想是: 每次将一个待排序记录按其关键字大小插入到前面已经排好序的子序列中, 使有序区间逐渐增长, 直到整个序列有序.

这和整理扑克牌常用手法很像: 手里的牌始终有序, 每抓到一张新牌, 就从右往左找到它该待的位置插进去.

由这一思想可以派生出三种算法:

• 直接插入排序: 边比较边后移, 找到位置后插入

• 折半插入排序: 用折半查找定位, 再统一后移

• 希尔排序: 按增量分组做直接插入, 让元素一次能跳得更远

三者都属于内部排序, 且都是原地算法(空间复杂度 \(O(1)\)). 与交换排序、选择排序并列, 是408中定义的内部排序的三大类之一.

直接插入排序¶

直接插入排序（Straight Insertion Sort）每次取未排序区间的第一个元素, 插入到左侧有序区间的合适位置.

把数组想象成一排固定座位而不是手里的牌: 两个相邻单元之间插不进一个新单元, 因此插入点右侧的元素必须依次后移一位, 腾出空位. 这和顺序表的插入是同一件事.

初始时, 只有 \(a[0]\) 一个元素, 单元素序列天然有序. 随后依次处理 \(a[1], a[2], \ldots, a[n-1]\).

以 \(\{10, 5, 2, 4, 7\}\) 为例 (竖线左侧是本趟开始前已经有序的前缀):

10 |  5,  2,  4,  7
5,  10 |  2,  4,  7
2,  5,  10 |  4,  7
2,  4,  5,  10 |  7
2,  4,  5,  7,  10 |

抓到 \(7\) 时, 只需从右往左依次和 \(10\)、\(5\) 比较: \(7 < 10\), 继续往左; \(7 > 5\), 插在这里. 无需再看左侧的 \(4\) 和 \(2\), 因为左侧已经有序. 这个前提就是下面要写的循环不变式.

flowchart TD
  A["j = 1"] --> B{"j < n?"}
  B -->|否| Z[结束]
  B -->|是| C["key = a[j]<br/>i = j - 1"]
  C --> D{"i >= 0 且 a[i] > key?"}
  D -->|是| E["a[i+1] = a[i]<br/>i--"]
  E --> D
  D -->|否| F["a[i+1] = key<br/>j++"]
  F --> B

算法实现¶

下面是 \(0\) 下标写法, 待排序区间为 \(a[0..n-1]\):

void insertion_sort(int a[], int n) {
    int i, j, key;
    for (j = 1; j < n; j++) {
        key = a[j];          // 本趟待插入元素
        i = j - 1;
        while (i >= 0 && a[i] > key) {
            a[i + 1] = a[i]; // 比 key 大的元素后移
            i--;
        }
        a[i + 1] = key;      // 空位插入
    }
}

void InsertSort(ElemType A[], int n) {
    int i, j;
    for (i = 2; i <= n; i++) {
        if (A[i] < A[i - 1]) {     // 小于前驱才需要插入
            A[0] = A[i];           // 哨兵
            for (j = i - 1; A[0] < A[j]; --j)
                A[j + 1] = A[j];
            A[j + 1] = A[0];
        }
    }
}

循环不变式¶

考虑如何证明"循环体执行 \(n-1\) 次后, 整个数组一定有序".

可以借用CLRS的循环不变式（Loop Invariant）, 若某个判断满足下面三条, 就可以用数学归纳法证明循环正确:

1. 初始化: 第一次执行循环体之前该判断为真

2. 保持: 若第 \(N\) 次循环之前为真, 则第 \(N\) 次循环之后仍为真

3. 终止: 循环结束后该判断为真, 足以说明问题已解决

直接插入排序的不变式是第 \(j\) 次循环之前, 子序列 \(a[0..j-1]\) 已排好序.

对应:

1. 第一次循环前 \(j = 1\), \(a[0..0]\) 只有一个元素, 显然有序 (归纳基础, 相当于递归的 Base Case)

2. 若 \(a[0..j-1]\) 已有序, 算法把所有大于 key 的元素后移并插入 key, 结束后 \(a[0..j]\) 仍有序 (递推关系)

3. 循环结束时 \(j = n\), 于是 \(a[0..n-1]\) 整体有序

这说明, 用不变式证明循环, 和用 Base Case + 递推证明递归, 是同一套思路, 递归与循环在证明上是等价的.

算法分析¶

设表长为 \(n\), 采用带哨兵的写法.

时间复杂度由「关键字比较次数 + 元素移动次数」决定. 第 \(i\) 趟 (\(i = 2, 3, \ldots, n\)) 是把 \(A[i]\) 插入 \(A[1..i-1]\).

• 最好 (表已正序): 每趟只与前驱比较 \(1\) 次, 不移动. 比较 \(n-1\) 次, 移动 \(0\) 次, \(O(n)\)

• 最坏 (表逆序): 每趟都要插到表头, 并撞上哨兵才停

  \[ \text{比较次数} = \sum_{i=2}^{n} i = \frac{(n+2)(n-1)}{2} \]
  \[ \text{移动次数} = \sum_{i=2}^{n} (i+1) = \frac{(n+4)(n-1)}{2} \]

  算法复杂度 \(O(n^2)\)

• 平均 (插入位置在有序区中均匀分布): 约为最坏情况的一半, 仍是 \(O(n^2)\)

• 空间复杂度 \(O(1)\), 原地排序.

• 稳定性: 后移条件是 a[i] > key 而不是 >=, 相等元素不会跨过彼此, 稳定.

• 适用存储: 顺序表与链表都可以. 链表上定位仍是 \(O(n)\), 但插入本身是 \(O(1)\), 无需成片移动元素.

折半插入排序¶

相比较直接插入排序, 折半插入排序（Binary Insertion Sort）把"找位置"和"腾空位"拆分开来:

1. 左侧已是有序顺序表, 用折半查找确定插入位置

2. 再把插入点到 \(A[i-1]\) 的元素统一后移, 写入待插入值

void binary_insertion_sort(ElemType A[], int n)
{
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++) {
        A[0] = A[i];
        low = 1;
        high = i - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (A[mid] > A[0])
                high = mid - 1;   // 插入点在左半
            else
                low = mid + 1;    // 相等也往右, 保证稳定
        }
        for (j = i - 1; j >= high + 1; --j)
            A[j + 1] = A[j];
        A[high + 1] = A[0];
    }
}

A[mid] == A[0] 时 low = mid + 1, 插入点落在相等元素右侧, 相对次序不变, 因此折半插入仍然稳定.

算法分析¶

• 每趟折半查找约 \(\lfloor \log_2 i \rfloor + 1\) 次比较, \(n\) 趟合计 \(\Theta(n \log n)\). 比较次数只取决于 \(n\), 与初始序列无关

• 元素移动次数与直接插入相同, 仍依赖初始序列, 最坏 \(O(n^2)\)

• 因此整体时间复杂度仍为 \(O(n^2)\); 最好情况是 \(O(n \log n)\) (几乎不移动, 但折半每次都要做), 不是 \(O(n)\)

• 空间 \(O(1)\); 需要随机访问, 只适用于顺序表

希尔排序¶

希尔排序（Shell Sort, 1959, Donald Shell）又称缩小增量排序. 它抓住了直接插入的两个性质:

1. 对接近有序的序列, 插入排序接近线性

2. 每次却只能把元素移动一个位置, 逆序时小元素要挪很久才能到前面

于是先让相距较远的元素各自有序 (一次能跳一大步), 再逐步缩小间距; 最后间距为 \(1\) 时退化为直接插入, 但此时序列已经「宏观有序」, 只需微调.

过程¶

取增量序列 \(d_1 > d_2 > \cdots > d_t = 1\). 第 \(k\) 趟把下标相差 \(d_k\) 的记录分成一组, 组内做直接插入. 常用且便于手算的是希尔增量: \(n/2,\ n/4,\ \ldots,\ 1\).

以 \(\{8, 9, 1, 7, 2, 3, 5, 4\}\) 为例:

最后一趟增量必须为 \(1\), 否则不能保证全部排完.

void ShellSort(ElemType A[], int n) {
    int dk, i, j;
    for (dk = n / 2; dk >= 1; dk /= 2) {
        for (i = dk + 1; i <= n; ++i) {
            if (A[i] < A[i - dk]) {
                A[0] = A[i];           // 暂存, 不是哨兵
                for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk)
                    A[j + dk] = A[j];
                A[j + dk] = A[0];
            }
        }
    }
}

算法分析¶

• 空间复杂度 \(O(1)\)

• 时间复杂度依赖于增量序列, 目前没有公认的最优序列. 希尔增量最坏 \(O(n^2)\); 某些序列 (如 Hibbard \(2^k-1\)) 最坏可达 \(O(n^{3/2})\); 408 常记「特定范围内约 \(O(n^{1.3})\)」

• 不稳定: 相等关键字可能被分到不同子表, 组内排序会打乱相对次序. 例如 \(\{5_a, 5_b, 2\}\), 增量 \(2\) 的一组是 \((5_a, 2)\), 排完变成 \(\{2, 5_b, 5_a\}\)

• 只适用于顺序表: 按 \(d_k\) 跳跃访问, 链表做不到随机定位(其实也可以, 但是每次定位都要 \(O(n)\) 的开销)

增量序列只要最后一项为 \(1\) 就能正确工作; 选取与严格复杂度证明仍是未完全解决的问题.

三种插入排序对照¶

对长度为 \(5\) 的几组一维数组, 分别用无哨兵直接插入 (plain)、哨兵直接插入 (sentinel)、折半插入 (binary)、希尔 (shell, 希尔增量 \(n/2,\ldots,1\)) 排序. 源码见GitHub.

plain / shell 数据在 \(a[0..n-1]\); sentinel / binary 把数据放在 \(A[1..n]\), \(A[0]\) 当哨兵或暂存.

比较计为关键字比较次数, 移动计为对数组元素的赋值 (含取出 / 写回 key / tmp):

                           Cmp    Mov
  akaedu     plain           8     14
  akaedu     sentinel       14     14
  akaedu     binary          7     14
  akaedu     shell          13     12
  sorted     plain           4      8
  sorted     sentinel        4      0
  sorted     binary          8      8
  sorted     shell           7      0
  reversed   plain          10     18
  reversed   sentinel       18     18
  reversed   binary          6     18
  reversed   shell          11     10
  dups       plain           9     14
  dups       sentinel       13     12
  dups       binary          7     14
  dups       shell          11      7

• 自适应在哨兵版上最清楚. 正序时每趟只跟前驱比 \(1\) 次就跳过内层, 比较 \(n-1=4\), 移动 \(0\), 即 \(O(n)\). plain 没有「小于前驱才插入」这道门, 即使已经就位也要把 key 取出再写回, 所以正序仍有 \(2(n-1)=8\) 次移动

• 直接插入一族的移动由「左边有多少个比它大」决定. plain / sentinel / binary 同一组数据的移动几乎一样 (逆序都是 \(18\), 与 \(\frac{(n+4)(n-1)}{2}=18\) 相符). 折半只改找位置的方式, 不减少后移. dups 里 sentinel 少 \(2\) 次, 是因为中间那个 \(3\) 已不小于前驱, 整趟插入被跳过

• 折半的收益在比较. 逆序时 binary \(6\) 次, 明显少于 plain \(10\)、sentinel \(18\); 正序时折半反而最多 (\(8\)), 因为每趟都要折半, 不能像哨兵那样「看一眼前驱就停」. 这就是「最好 \(O(n\log n)\) 而不是 \(O(n)\)」

• 折半比较次数「只取决于 \(n\)」, 指量级是 \(\Theta(n\log n)\)、不随逆序程度爆到 \(n^2\). 精确次数仍会随插入点偏左 / 偏右差几次: 正序总往右扩, \(8\) 次; 逆序总往左缩, \(6\) 次

• sentinel 逆序比较 \(18\), 比公式 \(\frac{(n+2)(n-1)}{2}=14\) 多 \(n-1=4\). 实现里 if (A[j] < A[j-1]) 和紧接着内层第一次 A[0] < A[j-1] 比的是同一对, 多计了每趟开头那一次. 移动次数不受影响

• 希尔的收益在移动. 逆序时只移 \(10\) 次, 直接插入一族都是 \(18\). \(n=5\) 增量是 \(2,1\): 第一趟按步长 \(2\) 做分组插入, 元素一次能跨 \(2\) 格, 这组逆序跑完 \(d_k=2\) 就已经整体有序, 第二趟 \(d_k=1\) 只做 \(4\) 次前驱比较、移动 \(0\)

• 正序时希尔也是 \(O(n)\) 档. 同样「小于同组前驱才插入」, 正序比较 \(7\)、移动 \(0\). \(7\) 不是 \(n-1=4\), 因为要跑两轮增量: 每趟外层比较 \(n-d_k\) 次, \(d_k=2\) 比 \(3\) 次, \(d_k=1\) 比 \(4\) 次, 合计 \(7\). 多出来的是「多几趟分组」, 不是在逆序上爆掉

• 希尔排序的不稳定性能在 dups 里看到. \(\{3,1,3,2,1\}\) 两个 \(1\) 原先左边那个在前; 增量 \(2\) 时后一个 \(1\) 与前一个 \(3\) 同组, 插入后跑到表头, 变成右边那个 \(1\) 在前. 组内仍用 <, 相等不插, 所以这组数据里两个 \(3\) 的相对次序没被打乱, 但两个 \(1\) 已经够当反例

• 希尔排序触发插入时, 外层 if 和内层第一次比较也是同一对, 会像 sentinel 那样多计. 正序没有内层, 所以 \(7\) 次都是干净的前驱比较

• \(n=5\) 看不出 \(O(n^{1.3})\) 和 \(O(n^2)\) 的渐近差别, 但逆序移动已经少了 \(8\) 次; 规模再大、增量序列再好, 差距才会显著拉开