考研全科复习

Appearance

DS-07-02 插入排序 ​

408 > ### 数据结构 > #### 插入排序（直接插入排序/折半插入排序） ​

一、定位信息 ​

维度内容
章节归属第7章 排序
知识单元编号DS-07-02
前置知识DS-07-01 排序基本概念
后续衔接DS-07-05 希尔排序（基于插入排序的改进）
考试大纲要求掌握直接插入排序和折半插入排序的算法思想、实现及性能分析
预计学习时长35分钟

二、知识点讲解 ​

1. 直接插入排序（Straight Insertion Sort） ​

1.1 基本思想 ​

直接插入排序的核心思想是将待排序元素逐个插入到已排好序的有序序列中，初始时认为第一个元素自成一个有序序列，然后从第二个元素开始，依次将每个元素插入到前面已有序的序列中的正确位置。

类比：打扑克牌时，每抓一张新牌，就将其插入手中已排好的牌的合适位置。

1.2 算法过程 ​

设有 n 个待排序记录存放在数组 A[0..n-1] 中：

  1. 初始时，A[0] 自成一个有序区，A[1..n-1] 为无序区
  2. 从 i = 1 到 n-1，每次将 A[i] 插入到 A[0..i-1] 的有序区中
  3. 插入过程：从有序区末尾开始向前扫描，将比 A[i] 大的元素逐个后移，找到合适位置后插入

1.3 伪代码实现 ​

c
void InsertSort(ElementType A[], int n) {
    // 直接插入排序，A[0..n-1]
    int i, j;
    ElementType temp;  // 暂存待插入元素
    for (i = 1; i < n; i++) {  // 从第2个元素开始插入
        if (A[i].key < A[i-1].key) {  // 若A[i]比有序区最后一个元素小，才需要插入
            temp = A[i];  // 暂存待插入元素
            for (j = i - 1; j >= 0 && A[j].key > temp.key; j--) {
                A[j+1] = A[j];  // 比temp大的元素逐个后移
            }
            A[j+1] = temp;  // 插入到正确位置（j+1是因为循环多减了一次）
        }
        // 若A[i] >= A[i-1]，则A[i]已在正确位置，无需移动
    }
}

1.4 时间复杂度分析 ​

情况条件比较次数移动次数时间复杂度
最好序列已有序∑ᵢ₌₁ⁿ⁻¹ 1 = n-10O(n)
最坏序列逆序∑ᵢ₌₁ⁿ⁻¹ i = n(n-1)/2∑ᵢ₌₁ⁿ⁻¹ (i+1) = (n+2)(n-1)/2O(n²)
平均随机排列n²/4 + O(n)n²/4 + O(n)O(n²)

最好情况详细推导：当序列已有序时，内层循环只需比较一次（A[i] ≥ A[i-1]），共 n-1 次比较，0 次移动。

最坏情况详细推导：当序列逆序时，第 i 趟需要比较 i 次，移动 i+1 次（含暂存和最终赋值）。总比较次数 = 1+2+…+(n-1) = n(n-1)/2，总移动次数 = 2+3+…+n = (n+2)(n-1)/2。

1.5 空间复杂度 ​

仅使用常数个辅助变量（temp, i, j），空间复杂度为 O(1)，是原地排序。

1.6 稳定性 ​

稳定。因为当 A[i].key == A[j].key（j < i）时，插入过程中比较条件 A[j].key > temp.key 为 false（不严格大于），不会移动，保持了原顺序。

2. 折半插入排序（Binary Insertion Sort） ​

2.1 基本思想 ​

折半插入排序是直接插入排序的改进版。它将插入过程中的顺序查找改为折半查找，减少了比较次数，但移动次数不变。

2.2 伪代码实现 ​

c
void BinaryInsertSort(ElementType A[], int n) {
    // 折半插入排序，A[0..n-1]
    int i, j, low, high, mid;
    ElementType temp;
    for (i = 1; i < n; i++) {
        temp = A[i];       // 暂存待插入元素
        low = 0;           // 有序区左边界
        high = i - 1;      // 有序区右边界
        // 折半查找插入位置
        while (low <= high) {
            mid = (low + high) / 2;
            if (A[mid].key > temp.key)
                high = mid - 1;  // 插入点在左半部分
            else
                low = mid + 1;   // 插入点在右半部分（含相等时也放右边，保证稳定性）
        }
        // 此时 low 即为插入位置（low == high + 1）
        for (j = i - 1; j >= low; j--) {
            A[j+1] = A[j];  // 将 low..i-1 的元素逐个后移
        }
        A[low] = temp;  // 插入到正确位置
    }
}

2.3 时间复杂度分析 ​

方面复杂度说明
比较次数O(n log n)每趟用折半查找，比较 O(log i) 次，总计 ∑ᵢ₌₁ⁿ log i ≈ n log n
移动次数O(n²)移动次数与直接插入排序相同，最坏仍为 O(n²)
总时间O(n²)移动次数仍是瓶颈

折半插入排序减少了比较次数，但没有减少移动次数，因此总的时间复杂度仍为 O(n²)。在元素本身较大、移动成本较高时，折半插入排序比直接插入排序有优势。

2.4 稳定性 ​

稳定。折半查找中，当 A[mid].key == temp.key 时，令 low = mid + 1，保证了相同关键字元素的相对顺序。

3. 直接插入排序 vs 折半插入排序 对比表 ​

对比维度直接插入排序折半插入排序
查找方式顺序查找折半查找
比较次数（平均）O(n²)O(n log n)
移动次数O(n²)O(n²)
总时间复杂度O(n²)O(n²)
空间复杂度O(1)O(1)
稳定性稳定稳定
适用场景n 较小或基本有序元素较大，移动成本高

三、记忆辅助 ​

  1. 打牌比喻：直接插入排序就像摸牌——每次抓一张，插入手中已排好的牌的合适位置
  2. 折半改进的本质：折半插入只改进了「找位置」的过程（O(log n)），没有改进「搬元素」的过程（仍 O(n²)），所以总复杂度不变
  3. 最好/最坏：已有序 → O(n) 最好；逆序 → O(n²) 最坏。所以「插入排序爱有序序列」
  4. 稳定性保证：比较条件用 > 而非 >=，相同关键字不会被移动，天然稳定

四、例题精解 ​

例题 1：直接插入排序的过程模拟 ​

题目：对序列 (49, 38, 65, 97, 76, 13, 27, 49') 进行直接插入排序，请写出第 4 趟排序后的结果（下标从 1 开始）。

第一步：审题 需要对给定序列执行直接插入排序，前 4 趟（i=1,2,3,4）的结果。

第二步：逐趟模拟

初始序列：[49] | 38, 65, 97, 76, 13, 27, 49'

第 1 趟（i=1）：将 38 插入 [49]

  • 38 < 49，49 后移，38 插入
  • 结果：[38, 49] | 65, 97, 76, 13, 27, 49'

第 2 趟（i=2）：将 65 插入 [38, 49]

  • 65 > 49，无需移动，65 已在正确位置
  • 结果：[38, 49, 65] | 97, 76, 13, 27, 49'

第 3 趟（i=3）：将 97 插入 [38, 49, 65]

  • 97 > 65，无需移动
  • 结果：[38, 49, 65, 97] | 76, 13, 27, 49'

第 4 趟（i=4）：将 76 插入 [38, 49, 65, 97]

  • 76 < 97，97 后移
  • 76 < 65 不成立，停止
  • 76 插入到 65 之后
  • 结果：[38, 49, 65, 76, 97] | 13, 27, 49'

第三步：解答 第 4 趟后序列为：38, 49, 65, 76, 97, 13, 27, 49'

第四步：总结 直接插入排序每趟保证前 i+1 个元素有序。注意当待插入元素 ≥ 有序区最后一个元素时，不需要任何操作。

例题 2：时间复杂度分析计算 ​

题目：直接插入排序在最坏情况下的比较次数为多少？若对 n=10 的逆序序列排序，实际比较次数是多少？

第一步：审题 需要计算最坏情况下直接插入排序的比较次数，分别给出公式和具体数值。

第二步：分析

最坏情况为序列完全逆序。此时每趟插入都需要比较到有序区的第一个元素：

  • 第 1 趟（i=1）：比较 1 次（与 A[0] 比较）
  • 第 2 趟（i=2）：比较 2 次
  • ...
  • 第 n-1 趟（i=n-1）：比较 n-1 次

总比较次数 = 1 + 2 + ... + (n-1) = n(n-1)/2

当 n = 10 时：总比较次数 = 10 × 9 / 2 = 45 次

第三步：解答 公式：最坏比较次数 = n(n-1)/2 n=10 时：45 次

第四步：总结 直接插入排序的比较次数与序列的逆序数密切相关。逆序数越多，比较和移动次数越多。最好情况（已有序）比较次数仅为 n-1。

例题 3：折半插入排序的优势场景 ​

题目：为什么说折半插入排序在"元素本身较大、移动成本高"时比直接插入排序有优势？

第一步：审题 需要解释折半插入排序的实际优势，不是总时间复杂度（两者都是 O(n²)），而是常数因子的差异。

第二步：分析

  • 折半插入排序的比较次数从 O(n²) 降到 O(n log n)
  • 移动次数仍为 O(n²)
  • 但"比较"和"移动"的实际代价不同：
    • 比较：关键字比较，通常代价较低
    • 移动：整个记录的赋值，若记录很大（如含多个字段），代价高
  • 折半查找减少了比较次数，在元素较大时可减少总时间

第三步：解答 折半插入排序通过折半查找将比较次数从 O(n²) 降至 O(n log n)，虽然移动次数不变，但当记录较大时，每次移动的代价远大于比较，减少比较次数带来的收益更明显。

第四步：总结 评估排序算法不能只看渐近复杂度，还要考虑常数因子和实际代价。折半插入排序在 n 不太大、记录较大的场景下是实用的改进。

五、考情分析 ​

年份题型考点难度
高频选择题直接插入排序的过程模拟★★☆
中频选择题最好/最坏情况的比较次数计算★★☆
低频应用题折半插入排序与直接插入排序的对比★★★

命题趋势：

  • 直接插入排序的过程模拟是常考题型，常考前几趟的结果
  • 时间复杂度分析（最好/最坏/平均）几乎年年涉及
  • 与希尔排序结合考查是常见模式

六、易错点 ​

  1. 循环变量的初始值：外层循环从 i=1 开始（第 2 个元素），不是 i=0
  2. 插入位置的确定：内层循环结束后 j+1 才是插入位置，因为循环条件 j >= 0 && A[j].key > temp.key 中 j 会多减一次
  3. 折半查找的等号处理：当 A[mid].key == temp.key 时应令 low = mid + 1（保证稳定性），不是 high = mid - 1
  4. 最好情况误判：不要认为"只有一个元素"是最好情况，最好情况是「序列已有序」，比较次数为 n-1
  5. 稳定性分析：直接插入和折半插入都是稳定的，不要因为折半查找就认为不稳定

七、来源标注 ​

  • 《数据结构（C语言版）》严蔚敏，第10.2节 插入排序
  • 《数据结构》王道考研，第7章 7.2节 插入排序
  • 408考试大纲：数据结构部分-插入排序
  • 《算法导论》Thomas H. Cormen，第2章 插入排序

考研全科复习资料 - 基于2026考研统考大纲

仅供学习参考