Lecture 30：插入排序

直接插入和折半插入维护连续的有序前缀；希尔排序在每趟维护各个增量子表有序，直到增量 $1$ 才形成全表有序。直接插入一次只处理一个新元素，折半插入减少定位比较，希尔排序则先让远距离元素接近正确位置。

30.1 直接插入排序

30.1.1 基本过程

定义：#直接插入排序

描述：依次取无序区第一个元素，将它插入前面已排好序的子序列中，直到所有元素处理完毕。

void InsertSort(int A[], int n) {       // A[0..n-1]
    for (int i = 1; i < n; ++i) {
        int temp = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > temp) {
            A[j + 1] = A[j];            // 大于 temp 的元素后移
            --j;
        }
        A[j + 1] = temp;
    }
}

第 $i$ 趟开始前，A[0..i-1] 已有序；temp=A[i] 是本趟唯一待插入元素。
应先暂存 A[i]，再后移较大元素；直接交换相邻元素也能实现，但移动次数更多。
条件写为 A[j] > temp 而非 >=，相等元素不会跨越，故直接插入排序稳定。

30.1.2 哨兵实现与复杂度

将真实记录放在 A[1..n]，预留 A[0]：

void InsertSort_Sentinel(int A[], int n) {
    for (int i = 2; i <= n; ++i) {
        if (A[i] < A[i - 1]) {
            A[0] = A[i];
            int j;
            for (j = i - 1; A[0] < A[j]; --j)
                A[j + 1] = A[j];
            A[j + 1] = A[0];
        }
    }
}

A[0] 是哨兵，保证内层循环最终会停止，省去 j>=1 的边界判断；它不能存真实记录。
最好情况：原表已经有序，每趟只比较一次，时间为 $O(n)$。
最坏情况：原表逆序，第 $i$ 个元素要前移 $i-1$ 位：

$$ 1+2+\cdots+(n-1)=\frac{n(n-1)}{2}=O(n^2) $$

平均时间复杂度为 $O(n^2)$，辅助空间为 $O(1)$；适合小规模或近乎有序的序列。
链表可避免数组的大量物理后移，但定位插入位置仍需顺序比较，时间量级仍为 $O(n^2)$。

30.1.3 折半插入排序

定义：#折半插入排序

描述：在已排序子序列中用折半查找确定插入位置，再统一移动记录腾出位置的插入排序。

只适用于顺序表，因为需要随机访问中点。
为保持稳定性，若 A[mid] == temp，应继续在中点右侧寻找插入位置，使新记录排在已有相等记录之后。
定位阶段的关键字比较总量可降至 $O(n\log n)$，但每趟记录移动仍可能为 $O(n)$，所以总时间复杂度仍为 $O(n^2)$。

void BinaryInsertSort(int A[], int n) {  // A[1..n]，A[0] 暂存
    for (int i = 2; i <= n; ++i) {
        A[0] = A[i];
        int low = 1, high = i - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (A[mid] > A[0])
                high = mid - 1;
            else
                low = mid + 1;  // 相等时向右，找 upper_bound
        }

        // 此时 low == high + 1，是稳定插入位置
        for (int j = i - 1; j >= low; --j)
            A[j + 1] = A[j];
        A[low] = A[0];
    }
}

折半结束时 low 指向最终插入位置，high=low-1。图中的插入位置必须由比较过程确定，不能把 mid 停止时的位置直接当成答案。

原 PDF 的折半插入代码将 high=mid-1 误排为 high=mind-1；上面的可执行代码使用正确变量 mid。

30.2 希尔排序

30.2.1 基本思想

定义：#希尔排序 #缩小增量排序

描述：按增量 $d$ 将序列划分为若干个间隔为 $d$ 的子表，对每个子表做直接插入排序；逐步缩小 $d$，直到 $d=1$。

对某个起点 $i$，其增量子表为：

$$ L[i],L[i+d],L[i+2d],\ldots $$

最后一趟 $d=1$ 就是直接插入排序，但此前的大增量趟已消除了大量远距离逆序，使最后一趟通常更快。
常见增量序列是 $\lfloor n/2\rfloor,\lfloor n/4\rfloor,\ldots,1$；考题可能指定其他增量，必须按题给序列分组。
依赖下标相距 $d$ 的访问，适用于顺序表，不适合链表。

void ShellSort(int A[], int n) {        // A[1..n]，A[0] 为暂存单元
    for (int d = n / 2; d >= 1; d /= 2)
        for (int i = d + 1; i <= n; ++i)
            if (A[i] < A[i - d]) {
                A[0] = A[i];
                int j;
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d)
                    A[j + d] = A[j];
                A[j + d] = A[0];
            }
}

分趟示例：

对序列 $49,38,65,97,76,13,27,49$，取增量 $4,2,1$：

原 PDF 文字称“9 个元素”，但配图中下标 1--8 才是 8 个待排序记录，0 号位是暂存单元；因此第一趟增量按 $8/2=4$ 计算。

$d=4$ 时，四个子表分别是 $(49,76),(38,13),(65,27),(97,49)$；各自插入排序后得到 $(49,76),(13,38),(27,65),(49,97)$。

按原下标交错放回后，序列为 $49,13,27,49,76,38,65,97$。

$d=2$ 时，奇数位子表为 $(49,27,76,65)$，偶数位子表为 $(13,49,38,97)$；排序后分别为 $(27,49,65,76)$ 与 $(13,38,49,97)$。

交错放回得到 $27,13,49,38,65,49,76,97$；最后 $d=1$ 做一趟直接插入排序，得到 $13,27,38,49,49,65,76,97$。

这组数据中两个 $49$ 最终恰好没有逆序，并不能证明希尔排序稳定；只要存在另一组输入能使相等记录跨组越过，算法分类仍是不稳定。

30.2.2 性能与稳定性

辅助空间为 $O(1)$。
时间复杂度与增量序列密切相关；常用增量下最坏情况可达 $O(n^2)$，不能在未给增量的题中机械写某个固定平均复杂度。
希尔排序不稳定：两个相等关键字可能属于不同增量子表，一个记录会跨过另一个相等记录。
它比直接插入更适合中等规模、初始无序程度较高的顺序表，但不能因为“最后一趟是插入排序”就称它稳定。

30.3 本节复盘

直接插入排序维护前缀有序；最好 $O(n)$，平均和最坏 $O(n^2)$，稳定且原地。
折半插入只降低比较次数，移动次数不变，因此总复杂度仍为 $O(n^2)$；相等时向右找才能稳定。
希尔排序按增量做插入排序，最后增量为 $1$；效率依赖增量序列，且不稳定。