数据结构高分笔记：插入排序与折半插入排序精细整理

• 【插入排序】 https://www.bilibili.com/video/BV1b7411N798/?p=91&share_source=copy_web&vd_source=27abef6992749c2b76e3f7b2a2c835b5

📌 考纲导学与知识脉络

在数据结构的学习中，插入排序（Insertion Sort）*是最基础、最直观的排序算法。它是后续学习更高效排序（如希尔排序）的基石。 本篇笔记根据手写笔记的脉络，结合王道考研大纲及视频原文进行精细化整理。我们将从*直接插入排序（传统法 vs 哨兵法）*出发，过渡到利用二分查找优化的*折半插入排序，并延伸至链表插入排序，帮助你彻底攻克考研中的相关考点。

[知识脑图]
插入排序 ─── 直接插入排序 ─── 不带哨兵版 (Temp暂存)
          │                └── 带哨兵版 (A[0]兼顾暂存与边界)
          ├── 折半插入排序 ─── 利用前趋有序进行二分折半定位 (优化比较次数)
          └── 链表插入排序 ─── 链式存储下的指针修改操作 (优化移动次数)

第一部分：直接插入排序 (Direct Insertion Sort)

1. 核心算法思想

一句话总结：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

工作原理图解： 设待排序数组为 $A[1 \dots n]$：

1. 初始时，认为 $A[1]$ 是一个已经排好序的子序列。
2. 从第二个元素 $A[2]$ 开始，依次作为待插入的关键字。
3. 将当前处理的元素与前面已排序的子序列进行从后往前的对比。
4. 凡是比当前处理元素更大的元素，均需要依次往后移一位，为其腾出空间。
5. 将待插元素放入挪出来的空位，重复此步骤直至最后一个元素插入完毕。

2. 经典例题：直接插入排序过程推导

【例题 1】

已知初始序列为：[49, 38, 65, 97, 76, 13, 27, 49*]（其中 $49^*$ 带有下划线/星号，用于区分首个 $49$，以便验证算法的稳定性）。请写出直接插入排序递增排序的过程。

【详细推导步骤】

• 初始状态：[49] 是已排序子序列，待处理元素为 38。

  $\underbrace{[49]}_{\text{已排序}} \ \ 38 \ \ 65 \ \ 97 \ \ 76 \ \ 13 \ \ 27 \ \ 49^*$

• 第 1 趟：待插元素为 38。

  • 38 与 49 比较，49 > 38，49 后移。

  • 已经到头，将 38 插入到最前面。

    $\text{结果：} \underbrace{[38, 49]}_{\text{已排序}} \ \ 65 \ \ 97 \ \ 76 \ \ 13 \ \ 27 \ \ 49^*$

• 第 2 趟：待插元素为 65。

  • 65 与前驱 49 比较，65 > 49，无需移动，直接放回原位。

    $\text{结果：} \underbrace{[38, 49, 65]}_{\text{已排序}} \ \ 97 \ \ 76 \ \ 13 \ \ 27 \ \ 49^*$

• 第 3 趟：待插元素为 97。

  • 97 > 65，保持原位。

    $\text{结果：} \underbrace{[38, 49, 65, 97]}_{\text{已排序}} \ \ 76 \ \ 13 \ \ 27 \ \ 49^*$

• 第 4 趟：待插元素为 76。

  • 97 > 76，97 后移；65 < 76，停止查找。

  • 将 76 插入到原 97 的位置（即 65 的后面）。

    $\text{结果：} \underbrace{[38, 49, 65, 76, 97]}_{\text{已排序}} \ \ 13 \ \ 27 \ \ 49^*$

• 第 5 趟：待插元素为 13。

  • 与前面元素依次对比，发现前面的 97, 76, 65, 49, 38 都比 13 大，全部依次右移一位。

  • 将 13 插入到下标 $0$（或最开头的位置）。

    $\text{结果：} \underbrace{[13, 38, 49, 65, 76, 97]}_{\text{已排序}} \ \ 27 \ \ 49^*$

• 第 6 趟：待插元素为 27。

  • 97, 76, 65, 49, 38 均大于 27，依次右移。

  • 13 < 27，停止挪位，将 27 插在 13 后面。

    $\text{结果：} \underbrace{[13, 27, 38, 49, 65, 76, 97]}_{\text{已排序}} \ \ 49^*$

• 第 7 趟：待插元素为 49*。

  • 97, 76, 65 均大于 49*，依次右移。

  • 遇到 49 时，由于 49 == 49*（不满足大于关系），停止右移。

  • 将 49* 插入到 49 的紧邻右侧。

    $\text{最终结果：} [13, 27, 38, 49, 49^*, 65, 76, 97]$

💡 稳定性验证：原本在后面的 $49^*$ 在排序后依然排在 $49$ 的后面，证明直接插入排序是一个稳定的排序算法。

3. 算法代码实现

3.1 传统实现方式：不带哨兵（使用 temp 暂存）

这是最符合直觉的实现。代码使用一个中间变量 temp 暂存当前需要插入的元素，以防在移动其他元素时被覆盖。

// 直接插入排序（无哨兵版）
void InsertSortWithoutSentinel(int A[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) { // 默认A[0]已有序，从A[1]开始往后处理
        if (A[i] < A[i-1]) {  // 若当前元素小于其前驱，说明需要向前插入
            temp = A[i];      // 用 temp 暂存 A[i]
            // 从后往前查找插入位置，且必须保证 j >= 0 防止数组越界
            for (j = i - 1; j >= 0 && A[j] > temp; --j) {
                A[j+1] = A[j]; // 大于 temp 的元素统一向后移位
            }
            A[j+1] = temp;    // 复制到插入位置
        }
    }
}

3.2 进阶实现方式：带哨兵（408课本经典实现）⭐

⚠️ 手写笔记背诵重点：使用带哨兵的实现，不需要使用 temp 临时保存了，也不需要在每轮循环都判断 $j \ge 0$。

在带哨兵的实现中，我们将数组的 A[0] 位置空出作为哨兵，实际的数据元素从 A[1] 开始存储。

// 直接插入排序（带哨兵版）
// 注意：传入的数组 A 实际物理空间应为 n+1，有效数据存放在 A[1]~A[n]
void InsertSort(int A[], int n) {
    int i, j;
    for (i = 2; i <= n; i++) { // 默认 A[1] 已有序，从 A[2] 开始依次处理
        if (A[i] < A[i-1]) {   // 若 A[i] 关键码小于其前驱
            A[0] = A[i];       // 1. 复制为哨兵（既起到了 temp 的暂存作用）
            
            // 2. 从后往前查找插入位置。
            // 因为 A[0] 存放了待插值，当 j 减小到 0 时，A[j] 必然不大于 A[0]（它们相等），
            // 此时循环必定自动终止！因此省去了 "j >= 0" 的边界判断，极大提高了循环效率。
            for (j = i - 1; A[0] < A[j]; --j) {
                A[j+1] = A[j]; // 向后挪位
            }
            A[j+1] = A[0];     // 3. 复制到最终插入位置
        }
    }
}

4. 直接插入排序性能分析

手写笔记中关于最好时间复杂度的记录略显模糊（写成了类似于 $O(1)$ 的字样）。此处根据王道教材进行规范修正和原理说明：

📊 性能汇总表

指标	复杂度 / 状态	详细物理开销与分析说明
空间复杂度	$O(1)$	仅需常数个辅助变量（i, j 或 A[0] 作为哨兵），与问题规模 $n$ 无关。
最好时间复杂度	$O(n)$	【原本就有序】：共需进行 $n-1$ 趟处理，但每一趟只需对比一次关键字 A[i] < A[i-1]，且不需要移动任何元素。比较次数为 $n-1$，移动次数为 $0$。
最坏时间复杂度	$O(n^2)$	【原本为逆序】：第 $i$ 趟处理需要对比 $i+1$ 次，移动 $i+2$ 次。总比较次数：$\sum_{i=2}^{n} (i) \approx \frac{n^2}{2}$总移动次数：$\sum_{i=2}^{n} (i+1) \approx \frac{n^2}{2}$
平均时间复杂度	$O(n^2)$	考研中通常将最好和最坏复杂度相加求期望，平均时间复杂度达 $O(n^2)$ 数量级。
算法稳定性	稳定 (Stable)	碰到相同关键字时不执行挪位，相同元素的相对顺序在排序前后不发生改变。

起承转合：为什么要优化为折半插入排序？

思考桥梁： 在直接插入排序中，我们每一趟都需要“边比较、边移动”。 既然我们在处理 $A[i]$ 时，它前趋子序列 $A[1 \dots i-1]$ 已经是一个排好序的有序表，那么在有序表里寻找“插入位置”时，我们真的有必要像傻子一样用“顺序查找”一步一步往前挪着对比吗？ 答案是否定的。既然前驱有序，我们理所当然可以使用效率更高的 二分查找（折半查找） 来快速定位待插入的位置！这就引出了——折半插入排序。

第二部分：折半插入排序 (Binary Insertion Sort)

1. 优化思路

• 直接插入排序 = 顺序查找插入位置 + 移动元素
• 折半插入排序 = 折半查找插入位置 + 移动元素

虽然使用折半查找成功将查找插入位置的比较次数降到了 $O(n\log_2 n)$ 级别，但是移动元素的次数并没有减少（依然需要把插入点右侧的所有元素整体后移）。因此，其整体的时间复杂度依然是 $O(n^2)$。

2. 折半查找插入位置的核心决策（稳定性处理）

为了保证折半插入排序的稳定性，遇到相同值的元素时必须特殊处理：

• 当 A[mid] == A[0]（待插值）时，为了保证新元素插在同值旧元素的右边，查找应该继续在 mid 所指位置右边进行。
• 即执行：low = mid + 1。
• 只有当 low > high 时，折半查找才会停止。
• 最终停止时，high + 1（或 low）即为元素应该插入的位置，我们需要将 [low, i-1] 内的所有元素整体右移。

3. 折半插入排序代码实现

// 折半插入排序
void BinaryInsertSort(int A[], int n) {
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++) {       // 依次将 A[2]~A[n] 插入前面的已排序序列
        A[0] = A[i];                 // 将当前待插元素暂存到 A[0]
        low = 1; high = i - 1;       // 初始化折半查找的范围（前趋有序区）
        
        while (low <= high) {        // 折半查找核心过程
            mid = (low + high) / 2;  // 取中间点
            if (A[mid] > A[0]) {
                high = mid - 1;      // 待插值比中间值小，往左半子表找
            } else {
                low = mid + 1;       // 待插值大于或【等于】中间值，往右半表找
            }
        }
        
        // 统一后移元素，腾出插入空位
        // 此时由于 low > high 退出循环，插入位置确定为 high + 1 (即 low 位置)
        for (j = i - 1; j >= high + 1; --j) {
            A[j+1] = A[j];
        }
        A[high+1] = A[0];            // 将元素放入确定的插入位置
    }
}

4. 经典例题：折半插入定位过程模拟

【例题 2】

现有序序列为 [20, 30, 40, 50, 60, 70, 80]，此时待插入元素为 55（存放在 A[0] 中）。模拟折半查找定位插入点的过程。

【详细定位步骤模拟】

• 初始状态：low = 1, high = 7。

  $\text{序列：} \underbrace{20}_{1} \ \ \underbrace{30}_{2} \ \ \underbrace{40}_{3} \ \ \underbrace{50}_{4} \ \ \underbrace{60}_{5} \ \ \underbrace{70}_{6} \ \ \underbrace{80}_{7}$

  $\text{待插值 } A[0] = 55$

• 第 1 轮折半：

  • $mid = \lfloor(1 + 7) / 2\rfloor = 4$（对应元素 50）
  • 比较：$A[mid] = 50 < A[0] = 55$，说明插入点在右边。
  • 调整：low = mid + 1 = 5。此时区间变为 [5, 7]。

• 第 2 轮折半：

  • $mid = \lfloor(5 + 7) / 2\rfloor = 6$（对应元素 70）
  • 比较：$A[mid] = 70 > A[0] = 55$，说明插入点在左边。
  • 调整：high = mid - 1 = 5。此时区间变为 [5, 5]。

• 第 3 轮折半：

  • $mid = \lfloor(5 + 5) / 2\rfloor = 5$（对应元素 60）
  • 比较：$A[mid] = 60 > A[0] = 55$，说明插入点在左边。
  • 调整：high = mid - 1 = 4。

• 查找结束：

  • 此时 low (5) > high (4)，满足退出条件，折半查找停止。
  • 确定插入位置：high + 1 = 5。
  • 将 [5, i-1]（即原 60 及其右侧元素）整体右移一格，给 55 腾出位置，完成插入。

【例题 3：相同元素稳定性验证】

在前驱有序序列 [20, 30, 40, 50, 55, 60, 70, 80] 中，待插入元素为 $60^*$（值同样为 60）。请展示折半插入是如何保证其不越过原有 60 相对顺序的。

• 过程解析：

  • 经过折半比对后，当 $mid$ 恰好指向原 60（对应下标 $6$）时，由于算法设计了：

    if (A[mid] > A[0]) high = mid - 1;
    else low = mid + 1; // 相同元素走这个分支

  • 虽然 $A[mid] A[0] 60$，但它不满足 A[mid] > A[0]。

  • 因此程序会执行 low = mid + 1，将范围强行推向原 60 的右半区进行查找。

  • 最终查找结束时，新插入的 $60^*$ 必然落于原有 60 的右侧，完美保障了算法的稳定性！

5. 折半插入排序性能分析

📊 性能汇总表

• 空间复杂度：$O(1)$
• 最好时间复杂度：$O(n^2)$
• 最坏时间复杂度：$O(n^2)$
• 平均时间复杂度：$O(n^2)$
• 稳定性：稳定 (Stable)

⚠️ 核心考点辨析： 与直接插入排序相比，折半插入排序仅仅减少了“比较关键字”的次数（降为了 $O(n\log_2 n)$）。 但由于物理存储上仍为顺序表，“移动元素”的次数没有变（平均和最坏情况下依然是 $O(n^2)$ 级）。 因此，折半插入排序的总体时间复杂度依然是 $O(n^2)$，并没有带来质的飞跃。

知识延展：链表的插入排序 (Insertion Sort on Linked List)

考研对比切入点： 前面讨论的折半插入由于采用了“顺序表”（数组）存储，可以进行随机存取，因此可以二分查找。 如果我们将数据元素的物理存储结构改为单链表（Linked List），情况会如何？

[链式存储结构]
Head ──> [13] ──> [38] ──> [49] ──> [65] ──> [97] ──> [76 (当前处理节点)] ──> NULL

1. 链表插入排序的核心特点

1. 移动元素开销降为 $O(1)$： 在链表中插入或移动一个节点，只需要修改前驱和后继的指针，完全不需要像顺序表那样整体后移元素。
2. 无法进行随机存取（二分折半失效）： 由于链表只能从头节点依次往后“顺序查找”对比，因此无法实现折半插入排序，只能采用“直接插入排序”的思想进行顺序比对定位。

2. 性能分析与考点对比

• 比较次数：由于无法随机存取，只能从链表头部顺序向后查找插入点，关键字的对比次数依然是 $O(n^2)$ 数量级。
• 移动次数：修改指针为常数级操作，移动/插入的物理开销大大降低。
• 总体时间复杂度：虽然移动元素的实际物理开销变小了，但由于关键字比较次数依然为 $O(n^2)$，所以整体时间复杂度仍然保持 $O(n^2)$。
• 空间复杂度：$O(1)$。

🏁 考研考点大总结与对比表

在选择题和综合题中，王道经常喜欢将这三种插入排序横向对比。请熟记下表：

排序算法名称	比较次数 (最坏/平均)	移动次数 (最坏/平均)	空间复杂度	稳定性	适用存储结构
直接插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	顺序表、链表均可
折半插入排序	$O(n\log_2 n)$	$O(n^2)$	$O(1)$	稳定	仅适用于顺序表
链表插入排序	$O(n^2)$	$O(n)$ （仅修改指针）	$O(1)$	稳定	仅适用于链表

💡 黄金考点提示： 如果原始序列已经基本有序或数据规模极小时，直接插入排序能够达到非常优秀的执行效率（接近 $O(n)$），甚至会优于快速排序等高级排序算法。