跳转至

408 高频考点精讲:插入排序(Insertion Sort (Direct, Binary, and Shell Sort))

模块归属:数据结构 · 排序
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:3 次(2016~2025 年:2017#10、2020#11、2022#42)
  • 历年总考查频次:3 次
  • 出题形式:单项选择题(算法渐进性能分析、比较与移动次数微观辨析、算法选型论证)、综合解答题(流式有序插入算法设计、Top-K 极值维护与复杂度证明,分值 10 分)
  • 命题特点:
  • 微观运行机理与状态依赖性考查:重点考查“初始基本有序”及“小规模数据”输入场景下,直接插入排序比较次数与移动次数的非对称退化特性,并与简单选择排序、冒泡排序形成精细辨析;
  • 算法设计与工程维护思想考查:综合应用大题倾向于将插入排序的“有序区动态扩展与维持”机制应用于海量流式数据处理(如维护固定长度 \(k\) 的滑动窗口有序数组求 Top-K 极值);
  • 内部排序多维综合对比:从时空复杂度、稳定性、是否原地、比较与移动次数、每一趟是否确定全局最终位置等多个维度进行纵深综合考查。
近十年考查年份分布:
2016   2017   2018   2019   2020   2021   2022   2023   2024   2025
 -      √      -      -      √      -      √      -      -      -
      (#10)                 (#11)        (#42)

二、 具体考察内容

1. 直接插入排序(Direct Insertion Sort)

(1) 算法核心思想

直接插入排序是一种基于“增量构建有序序列”的原地排序算法。其基本思想为:在排序全过程中,将待排序记录序列划分为两个逻辑部分: * 前半部分:有序区 \(A[1 \dots i-1]\); * 后半部分:无序区 \(A[i \dots n]\)。

算法每次从无序区首部取出第一个记录 \(A[i]\)$ \text{(称为待插入记录),通过由后向前的关键字比对,在有序区} $\(A[1 \dots i-1]\)$ \text{中寻找其合适的插入位置,同时将所有大于该记录的有序区元素依次向后平移一位,最后将待插入记录放入空出的位置。经过} $\(n-1\) 趟迭代,无序区清空,整个序列转化为全局有序。

初始状态:
[有序区: A[1]] | [无序区: A[2], A[3], ..., A[n]]

第 i 趟插入过程:
[有序区: A[1], ..., A[j], A[j+1], ..., A[i-1]] | [待插入: A[i]] [剩余无序区...]
                          └── 向后平移 ──┘
插入完成状态:
[有序区: A[1], ..., A[j], A[i], A[j+1], ..., A[i-1]] | [剩余无序区...]

(2) 带哨兵(Sentinel)机制的算法实现与边界推导

在基于数组的顺序存储实现中,通常引入下标为 0 的存储单元 \(A[0]\) 作为哨兵(Sentinel)。哨兵机制的设计具有两大核心功能: 1. 暂存功能:暂存当前待插入的记录,无需为暂存变量额外开辟堆栈空间; 2. 越界防护与循环条件优化:在由后向前遍历有序区的比较过程中,若待插入元素小于有序区内的所有元素,搜索指针 \(j\)$ \text{递减到 0 时,必然会与哨兵单元} $\(A[0]\)$ \text{发生比对。由于} $\(A[0]\)$ \text{存放的正是待插入元素本身,比对条件} $\(A[0] < A[j]\)$ \text{(即} $\(A[0] < A[0]\))必然判定为假,循环自然终止。

这一机制彻底省去了每一轮循环中对下标边界 \(j \ge 1\) 的显式逻辑判断,消除了内层循环的分支跳转指令,显著提升 CPU 指令流水线执行效率。

// 基于 1-based 索引并引入 A[0] 哨兵的标准直接插入排序算法实现
void InsertSort(int A[], int n) {
    int i, j;
    // 初始认为 A[1] 自成有序区,从第 2 个元素开始依次向有序区插入
    for (i = 2; i <= n; i++) {
        // 若当前元素小于其前驱,说明需插入有序区;否则当前已有序,直接跳过
        if (A[i] < A[i - 1]) {
            A[0] = A[i]; // 将待插入记录存入哨兵单元
            // 边比较边后移:无需检查 j >= 1,当 j 减到 0 时 A[0] < A[0] 必然为假跳出循环
            for (j = i - 1; A[0] < A[j]; --j) {
                A[j + 1] = A[j]; // 大于待排元素的记录后移一位
            }
            A[j + 1] = A[0]; // 将哨兵元素填入最终腾出的空位
        }
    }
}

(3) 比较次数与移动次数的严格代数推导

直接插入排序的时间复杂度与初始序列的状态高度相关,分为最好、最坏与平均三种情形进行严格推导。

① 最好情况(序列完全正序)
  • 初始状态:\(A[1] \le A[2] \le \dots \le A[n]\)。
  • 比较次数:每一趟循环中,外层仅执行一次判断 A[i] < A[i - 1],由于前驱小于等于当前元素,条件为假,内层 for 循环完全不执行。第 \(i\)$ \text{趟只需比较 1 次,共执行} $\(n - 1\) 趟: $\(C_{\min} = \sum_{i=2}^n 1 = n - 1\)$
  • 移动次数:没有任何元素发生位置移动。若严格计入赋值操作(无需进入 if 分支),赋值移动为 0: $\(M_{\min} = 0\)$
  • 最好时间复杂度:比较操作为线性阶,算法时间复杂度为 \(O(n)\)。
② 最坏情况(序列完全逆序)
  • 初始状态:\(A[1] > A[2] > \dots > A[n]\)。
  • 比较次数:第 \(i\)$ \text{趟插入时,待插入元素} $\(A[i]\)$ \text{小于有序区内所有} $\(i-1\)$ \text{个元素。搜索指针} $\(j\)$ \text{从} $\(i-1\)$ \text{逐步减至 0,共与有序区元素比较} $\(i-1\)$ \text{次,最后在} $\(j=0\)$ \text{处与哨兵} $\(A[0]\)$ \text{比较 1 次,单趟比较次数为} $\(i\) 次。总比较次数为: $\(C_{\max} = \sum_{i=2}^n i = \frac{(2 + n)(n - 1)}{2} = \frac{n^2 + n - 2}{2}\)$
  • 移动次数:第 \(i\)$ \text{趟需执行:将} $\(A[i]\)$ \text{写入哨兵} $\(A[0]\)$ \text{(1 次移动);有序区} $\(i-1\)$ \text{个元素依次后移一位(} $\(i-1\)$ \text{次移动);将哨兵写回} $\(A[1]\)$ \text{(1 次移动)。单趟移动总次数为} $\(i + 1\) 次。总移动次数为: $\(M_{\max} = \sum_{i=2}^n (i + 1) = \frac{(3 + n + 1)(n - 1)}{2} = \frac{n^2 + 3n - 4}{2}\)$
  • 最坏时间复杂度:比较与移动次数均达到平方阶,算法时间复杂度为 \(O(n^2)\)。
③ 平均情况(随机全排列,等概率模型)

设序列中 \(n\)$ \text{个元素互不相同,共有} $\(n!\)$ \text{种可能的排列,每种排列出现的先验概率均等为} $\(1/n!\)。 * 在第 \(i\)$ \text{趟插入时,有序区已有} $\(i-1\)$ \text{个元素,待插入元素} $\(A[i]\)$ \text{插入到有序区中的可能位置共有} $\(i\)$ \text{个(从最左端到最右端),每个位置的概率均为} $\(1/i\)。 * 当插入到第 \(k\)$ \text{个可能位置(} $\(1 \le k \le i\)$ \text{)时,需要比较的次数为} $\(i - k + 1\)$ \text{(若算入与哨兵比较,平均约为} $\(\frac{i+1}{2}\) 次比较与移动)。 * 第 \(i\) 趟的期望比较次数为: $\(E[C_i] = \sum_{k=1}^i \frac{1}{i} \cdot k = \frac{i + 1}{2}\)$ * 全过程平均比较总次数为: $\(C_{\text{avg}} = \sum_{i=2}^n \frac{i + 1}{2} = \frac{1}{2} \left[ \frac{(n+1)(n+2)}{2} - 3 \right] \approx \frac{n^2}{4}\)$ * 同理,有序区元素的平均平移次数亦约为 \(\frac{n^2}{4}\)。 * 平均时间复杂度:算法平均时间复杂度为 \(O(n^2)\)。

(4) 空间复杂度与算法稳定性

  • 空间复杂度:算法仅借助 \(A[0]\)$ \text{哨兵单元(或常数个循环指针变量)完成位置交换与暂存,辅助存储空间为常数级,空间复杂度为} $\(O(1)\),属于原地排序(In-place Sorting)。
  • 稳定性严格判定:在内层循环寻找插入位置时,判断条件为严格小于:A[0] < A[j]。如果待排元素在有序区中遇到与自身关键字相等的记录,该条件立即判定为假,搜索终止,待排元素被插入在相等记录的紧邻后方。因此,序列中关键字相同的记录在排序前后的相对物理次序严格保持不变,直接插入排序是稳定的排序算法。

(5) 链表存储结构适配性

直接插入排序完全支持在单链表或双链表上运行: * 指针重链优势:定位到插入位置后,将节点插入链表仅需 \(O(1)\) 次指针赋值重定向,完全免除了顺序表所需的数组元素物理整体搬迁(平移移动开销为 0); * 顺序搜索限制:由于单链表不具备随机访问特性,查找插入位置仍必须从链表表头向后顺序线性遍历,单趟比较次数依然为 \(O(i)\); * 总结:链式插入排序总比较次数依然为 \(O(n^2)\)$ \text{,总时间复杂度仍为} $\(O(n^2)\)$ \text{,空间复杂度仍为} $\(O(1)\)。


2. 折半插入排序(Binary Insertion Sort)

(1) 算法设计动机

在直接插入排序的处理过程中,由于前 \(i-1\) 个元素构成的子序列已经是一个严格有序的递增序列。在有序序列中定位目标元素的插入点时,顺序查找存在明显的比较冗余。折半插入排序利用折半查找(二分查找)机制代替顺序查找,在有序区中以对数时间定位插入点。

(2) 算法执行逻辑与区间边界收敛推导

折半插入排序将每一趟分为两大独立阶段: 1. 阶段一(折半查找定界):通过二分比较确定待插入记录在有序区中的最终绝对下标; 2. 阶段二(物理平移与就位):将该下标及其之后的所有有序区元素整体后移一位,将待排元素填入空出位置。

// 折半插入排序算法标准实现
void BinaryInsertSort(int A[], int n) {
    int i, j, low, high, mid, temp;
    for (i = 2; i <= n; i++) {
        temp = A[i]; // 暂存待插入元素
        low = 1; 
        high = i - 1; // 设置折半查找边界

        // 折半查找插入位置
        while (low <= high) {
            mid = low + (high - low) / 2;
            if (A[mid] > temp) {
                high = mid - 1; // 目标落在左半区间
            } else {
                // 当 A[mid] <= temp 时,为了保证稳定性,必须继续在右半区间查找
                low = mid + 1; 
            }
        }

        // 此时 low == high + 1,low 即为目标插入位置
        // 将 [low, i - 1] 区间内的所有元素统一后移一位
        for (j = i - 1; j >= low; --j) {
            A[j + 1] = A[j];
        }
        A[low] = temp; // 放入目标位置
    }
}
  • 收敛性与稳定性证明:
  • 在二分比较中,当出现 A[mid] == temp 时,算法令 low = mid + 1,强制要求折半查找向右侧半区收缩。
  • 循环终止条件必为 low = high + 1,此时 low 所指向的单元恰好是第一个严格大于 temp 的记录所在位置(若所有元素均小于等于 temp,则 low 收敛到 \(i\))。
  • 插入到 low 位置保证了相同关键字的元素依然排在原有相同元素的后方,从而维持了算法的稳定性。

(3) 比较次数与移动次数的解耦特征

折半插入排序展现了内部排序中极其独特的“比较与移动操作相互解耦”的性质: * 比较次数的独立性:
在长度为 \(i-1\)$ \text{的有序区中进行折半查找,所构成的折半查找判定树高度为} $\(\lfloor \log_2(i-1) \rfloor + 1\)。每一趟定位所需的比较次数严格取决于该判定树高度,与待排序列的初始物理排列次序完全无关。 总比较次数为: $\(C = \sum_{i=2}^n \lceil \log_2 i \rceil \approx \int_1^n \log_2 x \, dx = n \log_2 n - n \log_2 e \approx O(n \log_2 n)\)$ 因此,无论初始序列是正序、逆序还是乱序,折半插入排序的比较次数恒为 \(O(n \log_2 n)\)。 * 移动次数的物理瓶颈:
折半查找仅加速了插入位置的检索过程,但并未改变基于顺序表连续存储的物理约束。确定插入位置 low 后,区间 \([low, i-1]\) 内的元素依然必须逐一向后平移。 - 最好情况(正序):每次 low = i,移动次数为 0; - 最坏情况(逆序):每次 low = 1,移动次数仍为 \(\frac{n(n-1)}{2} = O(n^2)\); - 平均情况:移动次数依然为 \(\approx \frac{n^2}{4} = O(n^2)\)。 * 时空复杂度总结: - 时间复杂度:受制于元素物理平移的平方级开销,整体时间复杂度仍为 \(O(n^2)\); - 空间复杂度:仅需常数级辅助变量,空间复杂度为 \(O(1)\); - 结构局限:由于折半查找必须依赖下标快速随机访问特性,折半插入排序仅适用于顺序存储结构,不可用于链式存储结构。


3. 希尔排序(Shell Sort)

(1) 算法设计动机:突破平方阶瓶颈

直接插入排序在两类极端场景下表现出近乎线性的极高执行效率: 1. 数据规模极小(\(n\) 很小); 2. 序列基本有序(逆序对数量极少)。

基于此观察,D. L. Shell 于 1959 年提出了希尔排序(又称缩小增量排序)。希尔排序通过引入“跨步跳跃分割”机制,将待排序列分割成若干个子序列分别进行直接插入排序;随后逐步缩小步长(增量),当增量缩减至 1 时,整个序列已高度趋近于全局有序,最后经过一次步长为 1 的标准直接插入排序完成全序。这一设计成功打破了传统简单排序算法 \(O(n^2)\) 的时间复杂度壁垒。

(2) 增量序列与算法执行流程

  • 分组规则:选取一个递减的增量序列 \(\{d_1, d_2, \dots, d_t\}\),满足: $\(d_1 > d_2 > \dots > d_t = 1\)$
  • 单趟过程:对于增量 \(d_k\)$ \text{,将整个数组中所有下标相差} $\(d_k\)$ \text{整数倍的元素划分为同一个子序列。总共构成} $\(d_k\) 个独立的子序列: $\(\{A[j], A[j + d_k], A[j + 2d_k], \dots\} \quad (1 \le j \le d_k)\)$ 在各子序列内部,分别执行直接插入排序。
// 希尔排序算法标准实现(采用 Shell 原始增量 d = n / 2)
void ShellSort(int A[], int n) {
    int dk, i, j;
    // 增量逐步折半缩减,直至 dk = 1
    for (dk = n / 2; dk >= 1; dk = dk / 2) {
        // 对各个增量分组交替进行直接插入排序
        for (i = dk + 1; i <= n; ++i) {
            if (A[i] < A[i - dk]) {
                A[0] = A[i]; // 暂存待插入元素(此处 A[0] 仅作暂存,不作哨兵)
                for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk) {
                    A[j + dk] = A[j]; // 跨步向后移动
                }
                A[j + dk] = A[0];
            }
        }
    }
}
  • 常见增量序列特性对比:
  • Shell 原始增量:\(d_1 = \lfloor n/2 \rfloor, d_{k+1} = \lfloor d_k/2 \rfloor\)$ \text{。由于各增量之间存在偶数公因子,互不互质,可能出现奇数位置与偶数位置直到最后一趟才发生交互比对的病态情形,最坏时间复杂度仍为} $\(O(n^2)\);
  • Hibbard 增量序列:\(d_k = 2^k - 1\)$ \text{(如} $\(1, 3, 7, 15, \dots\)$ \text{)。相邻增量互质,最坏时间复杂度降为} $\(O(n^{3/2})\)$ \text{,平均时间复杂度约为} $\(O(n^{5/4})\);
  • Sedgewick 增量序列:形如 \(9(4^i - 2^i) + 1\)$ \text{或} $\(4^i - 3 \cdot 2^i + 1\)$ \text{,最坏时间复杂度优化至} $\(O(n^{4/3})\)$ \text{,平均时间复杂度可达} $\(O(n^{7/6})\)。
  • 408 考纲基准标准:
  • 时间复杂度:在常规考查中,希尔排序的平均时间复杂度一般记为约为 \(O(n^{1.3})\)$ \text{,其最坏时间复杂度在} $\(O(n^2)\)$ \text{到} $\(O(n^{1.5})\) 之间(视增量序列而定);
  • 空间复杂度:原地排序,空间复杂度为 \(O(1)\)。

(3) 算法不稳定性严格证明

希尔排序是不稳定的排序算法。 * 机理剖析:由于算法在步长 \(d_k > 1\) 时采取跨步分组策略,相同关键字的记录若被分配到不同的增量分组中,在各自独立的子序列内部排序后,其相对物理先后位置可能发生颠倒。即便最后一趟是步长为 1 的直接插入排序,也无法恢复此前已被颠倒的相对次序。 * 极简反例构造: - 待排序列:包含 3 个元素 \(A = [2, 2^*, 1]\)$ \text{(其中} $\(2^*\) 用于区分相同键值); - 设定初始增量 \(d = 2\): - 分组 1(下标 1 与 3):子序列为 \(\{A[1], A[3]\} = \{2, 1\}\)$ \text{,经直接插入排序后变为} $\(\{1, 2\}\); - 分组 2(下标 2):子序列为 \(\{A[2]\} = \{2^*\}\),保持不变; - 第一趟增量排序结束后的序列形态为: $\([1, 2^*, 2]\)$ - 此时关键字数值同为 2 的两个记录,原本在前的记录 \(2\)$ \text{跑到了记录} $\(2^*\) 的后方,算法稳定性被彻底破坏。


4. 插入排序的最优应用场景与工程价值

在现代计算机体系结构与工业级通用基础类库中,插入排序虽渐进时间复杂度为 \(O(n^2)\),却在特定场景下扮演着不可替代的角色:

(1) 场景一:基本有序(Nearly Sorted)数据集

定义序列中的逆序对(Inversion Pair)数量为 $$ \text{I = |{(i, j) \mid i < j \text{ 且 } A[i] > A[j]}|} $\(。 * 直接插入排序的比较次数满足:\)C \le n - 1 + I\(; * 移动次数满足:\)M \le 2(n - 1) + I\(; * 当待排序列处于“基本有序”(例如仅有少量新元素被追加到已排序列尾部,或已有序列受到轻微局部扰动)时,\)I = O(n)$$ \text{,直接插入排序的时间复杂度达到严格的线性阶} $\(O(n)\)。在这一工况下,直接插入排序的执行耗时远低于快速排序、堆排序等高级算法。

(2) 场景二:小规模数据集(小 n 阈值截断优化)

在工业级混合排序算法(如 JDK 的 Dual-Pivot Quicksort、Python 与 Rust 标准库的 Timsort、C++ STL 的 Introsort 与 pdqsort)中,均采用了插入排序作为递归底层的截断保护: * 指令极其精炼:直接插入排序内循环只有几条核心机器指令,无递归调用开销,无额外函数调用栈帧创建与销毁代价; * 极佳的 CPU Cache 局部性:顺序遍历与连续后移具有完美的空间局部性(Spatial Locality),对现代 CPU 的一级数据缓存(L1 Data Cache)与预取器(Hardware Prefetcher)极度友好; * 截断阈值:当递归子区间长度缩小到某个常数阈值(通常为 \(16 \sim 32\)$ \text{)时,算法自动从快速排序或归并排序平滑切换为直接插入排序(或折半插入排序),可使整体排序性能提升} $\(10\% \sim 25\%\)。

(3) 场景三:海量流式数据在线增量维护(Streaming Top-K)

当面对无限到达的数据流,且需要动态维持一个容量为 \(k\) 的有序极值窗口时(如 2022 年第 42 题),插入排序思想具有天然优势: * 维护大小为 \(k\) 的固定数组; * 每次新到达一个元素,利用折半插入或顺序插入将其置入窗口合适位置,并丢弃溢出的第 \(k+1\) 个元素; * 单次处理时间仅为 \(O(k)\)$ \text{,全局空间开销仅为} $\(O(k)\)。


5. 八大内部排序算法多维横向对比矩阵

算法名称 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 稳定性 是否原地 每趟是否确定至少一个元素最终位置 最适应用工况
直接插入排序 \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 稳定 是 否 基本有序、小规模序列、链式存储
折半插入排序 \(O(n \log_2 n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 稳定 是 否 关键字比对代价高、顺序存储小规模序列
希尔排序 \(O(n)\) \(O(n^2)\)$ \text{或} $\(O(n^{1.5})\)$ \text{ 约} $\(O(n^{1.3})\) \(O(1)\)$ \text{ 不稳定 是 否 中等规模序列(} $\(n < 10^4\))
冒泡排序 \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 稳定 是 是(每趟沉底/浮顶) 教学演示、微型序列
快速排序 \(O(n \log_2 n)\) \(O(n^2)\) \(O(n \log_2 n)\) \(O(\log_2 n) \sim O(n)\) 不稳定 否(递归栈) 是(基准元素归位) 大规模离散随机分布序列
简单选择排序 \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 不稳定 是 是(每趟确定极值) 记录物理尺寸极大(移动代价高昂)
堆排序 \(O(n \log_2 n)\) \(O(n \log_2 n)\) \(O(n \log_2 n)\) \(O(1)\) 不稳定 是 是(每趟堆顶沉底) 海量数据静态 Top-K 检索
二路归并排序 \(O(n \log_2 n)\) \(O(n \log_2 n)\) \(O(n \log_2 n)\) \(O(n)\) 稳定 否 否 要求强稳定性、外部多路归并
基数排序 \(O(d(n + r))\) \(O(d(n + r))\) \(O(d(n + r))\) \(O(r)\) 稳定 否 否 关键字可按固定基数切分、规模极大

三、 近十年真题精讲(2016~2025)


【真题 1】2022 年 408 第 42 题 · 综合应用题(海量数据 Top-K 查找与有序插入思想)

题目
现有 \(n\)(\(n > 100000\)$ \text{)个数保存在一维数组} $\(M\)$ \text{中,需要查找} $\(M\) 中最小的 10 个数,请回答下列问题。
(1) 设计一个完成上述查找任务的算法,要求平均情况下的比较次数尽可能少,简单描述其算法思想,不需要程序实现。
(2) 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

【解析】

(1) 算法思想设计

本题要求在 \(n > 100000\)$ \text{的海量数据中筛选出最小的 10 个数(} $\(k = 10\)),具有强烈的工程优化导向。题目核心约束为平均情况下的比较次数尽可能少。围绕这一目标,标准的优秀解法包含以下两种范式,且均能取得满分:

方案一:基于有序数组维护的插入筛选算法(本考点直接映射方案)
  • 核心数据结构:建立一个长度为 \(k=10\)$ \text{的辅助数组} $\(A\)$ \text{,并保持} $\(A\) 始终处于升序排列状态。
  • 初始化:将数组 \(M\)$ \text{的前 10 个元素复制到辅助数组} $\(A\)$ \text{中,采用直接插入排序将其整理为递增有序序列:} $\(A[0] \le A[1] \le \dots \le A[9]\)。
  • 流式扫描插入与淘汰: 从 \(M[10]\)$ \text{开始依次向后扫描数组} $\(M\)$ \text{中剩余的} $\(n - 10\) 个元素:
  • 对于当前扫描元素 \(x = M[i]\)$ \text{,首先将其与辅助数组当前的最大值(即尾部元素} $\(A[9]\))进行比较;
  • 若 \(x \ge A[9]\)$ \text{,则说明} $\(x\) 不可能属于全局最小的 10 个数,直接丢弃,继续考察下一个元素;
  • 若 \(x < A[9]\)$ \text{,说明当前最大值} $\(A[9]\)$ \text{已被淘汰。此时利用折半插入(或由后向前的直接插入)在} $\(A[0 \dots 8]\)$ \text{中检索} $\(x\)$ \text{的合适插入位置,将比} $\(x\)$ \text{大的元素统一后移一位,将} $\(x\)$ \text{插入其中,维持辅助数组} $\(A\) 始终递增有序且长度恒为 10;
  • 算法收敛:遍历完数组 \(M\)$ \text{的全部元素后,辅助数组} $\(A\) 中保存的即为整个数组中最小的 10 个数。
方案二:基于大根堆维护的堆筛选算法
  • 建立一个容量为 \(k=10\)$ \text{的大根堆} $\(H\);
  • 将 \(M\) 的前 10 个元素建立为初始大根堆,堆顶保存当前这 10 个数中的最大值;
  • 遍历剩余的 \(n - 10\)$ \text{个元素:若当前元素} $\(x\)$ \text{小于堆顶元素,则淘汰堆顶,将} $\(x\)$ \text{置于堆顶并执行一次向下调整(Sift-down);若} $\(x\) 大于等于堆顶则直接忽略;
  • 扫描结束后,大根堆中的 10 个元素即为最小的 10 个数。
(2) 复杂度定量推导与证明(以方案一有序插入法为例)
  • 时间复杂度推导:
  • 初始化阶段:对 10 个元素进行直接插入排序,比较次数为常数(至多 \(\frac{10 \times 9}{2} = 45\) 次);
  • 扫描阶段:需要扫描 \(n - 10\)$ \text{个元素。对于每个元素,首先进行 1 次比较(与} $\(A[9]\)$ \text{比较)。在随机分布假设下,新元素小于} $\(A[9]\)$ \text{的概率极低(随已遍历元素数量} $\(m\)$ \text{呈} $\(\frac{10}{m}\) 迅速衰减)。绝大部分元素仅需 1 次比较即被过滤丢弃。
  • 即便发生插入,单次插入在大小为 10 的有序数组中采用折半查找仅需 \(\lceil \log_2 10 \rceil \le 4\) 次比较,移动至多 9 次。
  • 全过程总比较次数为 \(O(n \times 1) = O(n)\)。 因此,平均情况下的时间复杂度为 \(O(n)\)。
  • 空间复杂度推导: 算法仅需开辟常数大小为 \(k = 10\)$ \text{的辅助数组} $\(A\)$ \text{以及若干控制变量,辅助存储空间完全与} $\(n\) 的规模无关。 因此,空间复杂度为 \(O(1)\)。

【参考解答】

(1) 算法思想:
定义一个大小为 10 的辅助数组 \(A\)$ \text{。先将数组} $\(M\)$ \text{的前 10 个元素复制到} $\(A\)$ \text{中,并使用直接插入排序将其按升序排好。随后遍历数组} $\(M\)$ \text{中剩余的元素,将当前元素与} $\(A\)$ \text{中最大元素} $\(A[9]\)$ \text{比较:若大于或等于} $\(A[9]\)$ \text{,则跳过该元素;若小于} $\(A[9]\)$ \text{,则丢弃} $\(A[9]\)$ \text{,采用折半插入(或直接插入)将该元素插入到有序数组} $\(A\)$ \text{的相应位置,并使原大于该元素的记录后移,保持} $\(A\)$ \text{数组持续递增有序。扫描完全部数据后,} $\(A\) 中的 10 个元素即为最小的 10 个数。
(2) 复杂度:
平均时间复杂度为 \(O(n)\)$ \text{,空间复杂度为 } $\(O(1)\)。


【真题 2】2020 年 408 第 11 题 · 算法微观性能对比(比较次数与移动次数)

题目
对大部分元素已有序的数组进行排序时,直接插入排序比简单选择排序效率更高,其原因是( )。
I. 直接插入排序过程中元素之间的比较次数更少
II. 直接插入排序过程中所需要的辅助空间更少
III. 直接插入排序过程中元素的移动次数更少
A. 仅 I          B. 仅 III          C. 仅 I, II          D. 仅 I, II 和 III

【解析】

本题考查直接插入排序与简单选择排序在“大部分元素已有序(基本有序)”这一特化输入分布下的微观性能差异。逐项剖析如下:

1. 命题 I 深度分析(元素之间的比较次数)
  • 直接插入排序:
    直接插入排序具有强烈的“输入敏感性(Input Sensitivity)”。当数组大部分元素已有序时,每个新元素只需与有序区前驱比较 1 次至极少几次,即可确定其位置,无需扫描整个有序区。 在最好情况(完全正序)下,第 \(i\) 趟仅比较 1 次,全过程比较次数仅为: $\(C_{\text{insert}} = n - 1 = O(n)\)$ 在基本有序情况下,其比较次数依然紧致贴近 \(O(n)\) 线性级别。
  • 简单选择排序:
    简单选择排序的算法逻辑是:第 \(i\)$ \text{趟必须完整扫描无序区中剩余的所有} $\(n - i\) 个元素,通过逐一比对找到无序区的全局最小值,然后与无序区首元素交换。 该扫描过程完全独立于初始序列的有序程度。无论数组是完全正序、逆序还是杂乱无序,其第 \(i\)$ \text{趟比较次数恒为} $\(n - i\) 次,总比较次数恒为定值: $\(C_{\text{select}} = \sum_{i=1}^{n-1} (n - i) = \frac{n(n - 1)}{2} = \Theta(n^2)\)$
  • 对比结论:在基本有序序列下,直接插入排序的比较次数由 \(\Theta(n^2)\)$ \text{骤降至接近} $\(O(n)\)$ \text{,远少于简单选择排序僵化固定的} $\(\frac{n(n-1)}{2}\) 次。命题 I 正确。
2. 命题 II 深度分析(所需要的辅助空间)
  • 直接插入排序与简单选择排序均属于典型的原地排序(In-place Sorting)算法;
  • 直接插入排序仅需一个哨兵单元 \(A[0]\)$ \text{或临时变量暂存待排记录,辅助空间复杂度为} $\(O(1)\);
  • 简单选择排序仅需一个临时变量用于记录最小关键字下标及执行变量交换,辅助空间复杂度同样为 \(O(1)\);
  • 对比结论:两者辅助空间开销在渐进意义与实际物理开销上完全相同,不存在谁比谁更少的问题。命题 II 错误。
3. 命题 III 深度分析(元素的移动次数)
  • 简单选择排序:
    每一趟在无序区找到最小值后,至多执行一次物理交换(涉及 3 次元素移动)。经过 \(n-1\) 趟,总移动次数至多为: $\(M_{\text{select}} \le 3(n - 1) = O(n)\)$ 即便在全乱序或逆序工况下,简单选择排序的移动次数也严格被线性阶 \(O(n)\) 所封顶。
  • 直接插入排序:
    只有在数组完全正序的极端情形下,直接插入排序移动次数才为 0。但在“大部分元素已有序”的一般实际情形下,只要无序区出现少量较小的元素,在插入有序区时,就必须将有序区中比其大的元素逐个向后平移一位,单次插入即可能引发多次连续的内存移动操作。
  • 对比结论:在移动次数指标上,简单选择排序在最坏与平均情况下均稳定保持在 \(O(n)\) 的极低水平;而直接插入排序在非完全有序情形下移动开销通常高于简单选择排序。因此“直接插入排序移动次数更少”在统计与普遍意义上不成立。命题 III 错误。

综上分析,导致直接插入排序效率更高的原因仅有命题 I。

正确答案:A


【真题 3】2017 年 408 第 10 题 · 排序算法选型论证(归并排序 vs 插入排序)

题目
在内部排序时,若选择了归并排序而没有选择插入排序,则可能的理由是( )。
1. 归并排序的程序代码更短
2. 归并排序的占用空间更少
3. 归并排序的运行效率更高
A. 仅 2          B. 仅 3          C. 仅 1, 2          D. 仅 1, 3

【解析】

本题考查内部排序算法在软件工程选型时的综合权衡考量。对题干给出的三项理由逐条进行严谨的算法工程学论证:

1. 理由 1 论证(程序代码复杂度)
  • 插入排序:实现逻辑极其紧凑,基于嵌套的双重循环结构(外层遍历无序区,内层移动有序区),核心代码仅需约 \(6 \sim 10\) 行,无任何递归或动态资源管理。
  • 归并排序:基于分治策略(Divide and Conquer),整体架构由递归划分函数 MergeSort 与归并核心函数 Merge 构成,需在合并过程中精细控制双指针边界、暂存数组读写及剩余片段拷贝,代码量与逻辑复杂度显著高于直接插入排序。
  • 结论:归并排序的代码明显比插入排序更为复杂繁琐。理由 1 错误。
2. 理由 2 论证(占用空间开销)
  • 插入排序:原地排序算法,空间复杂度为 \(O(1)\),无需额外开辟动态数组空间。
  • 归并排序:在将两个有序子表合并为一个完整有序表的过程中,必须借助于一个与待排序列等长的辅助数组用于双指针比较暂存,其辅助空间复杂度为严格的 \(O(n)\)。
  • 结论:归并排序的内存空间开销显著大于插入排序。理由 2 错误。
3. 理由 3 论证(运行效率与时间复杂度)
  • 插入排序:平均时间复杂度为 \(O(n^2)\)$ \text{,最坏时间复杂度为} $\(O(n^2)\)$ \text{。当数据规模} $\(n\)$ \text{逐步扩大(如} $\(n \ge 10^4\)$ \text{)时,} $\(n^2\) 的时间开销将急剧恶化,导致运行耗时发生指数级飞跃。
  • 归并排序:无论待排序列的初始物理排列分布如何,分治递归树高度恒为 \(\lceil \log_2 n \rceil\)$ \text{,每层合并开销恒为} $\(O(n)\)$ \text{,其最好、最坏与平均时间复杂度均严格收敛在稳定的} $\(O(n \log_2 n)\)。
  • 性能断层对比:当 \(n = 10^6\) 时:
  • 插入排序操作步数量级约为 \(n^2 = 10^{12}\);
  • 归并排序操作步数量级约为 \(n \log_2 n \approx 10^6 \times 20 = 2 \times 10^7\); 两者运行效率相差达数万倍。因此,在大规模数据处理中选用归并排序的核心理由正是其具备压倒性的运行效率。理由 3 正确。

综上所述,合理的理由仅有 3。

正确答案:B


四、 核心解题套路与易错陷阱

1. 核心解题套路

(1) “每趟执行完毕是否确定最终位置”判别法则

在 408 单项选择题中,考查“给出某一排序算法经过 \(k\) 趟后的序列中间状态,推断其所采用的排序算法”属于极其高频的必考题型。掌握各算法“元素最终归位特性”是秒杀此类题目的关键工具:

各算法每一趟结束能否确定至少一个元素的最终绝对位置:
┌───────────────┬────────────────────────────────────────────────────────┐
│ 绝对能够确定  │ • 简单选择排序:每趟将无序区极值交换到边界,确定1个绝对位置 │
│               │ • 堆排序:每趟堆顶(最大/最小)沉底交换,确定1个绝对位置 │
│               │ • 冒泡排序:每趟极值下沉到末端或上浮到顶端,确定1个绝对位置 │
│               │ • 快速排序:每趟基准元素划分就位,确定至少1个绝对位置      │
├───────────────┼────────────────────────────────────────────────────────┤
│ 绝对不能保证  │ • 直接插入排序:前 i 个元素局部有序,但若后续出现更小元 │
│               │   素,已排好的前 i 个元素仍会继续向后平移,全局位置全未定 │
│               │ • 折半插入排序:机理同直接插入排序,不能保证任何元素就位 │
│               │ • 希尔排序:各增量组独立,步长非1时无任何元素到达最终位置 │
│               │ • 二路归并排序:各子块局部归并,无法保证元素到达最终位置 │
│               │ • 基数排序:按位分配收集,未到最高位收集前无全局最终归位 │
└───────────────┴────────────────────────────────────────────────────────┘
  • 秒杀技巧:若题干展示的中间状态序列中,前几个元素呈现单调有序,但序列两端并没有出现全局最大值或最小值,且无法断定任何一个元素已经归位于其在最终全有序序列中的确切下标,应优先考虑插入排序或归并排序;反之,若末端或首端出现了全局极大值或极小值,迅速排除插入排序!

(2) 状态敏感型与状态惰性型算法精准分类套路

针对“待排数据基本有序”或“给定特定初始序列”的算法选型题,需牢记算法的状态敏感特性: * 高度状态敏感型(基本有序时效率极高): - 直接插入排序:最好时间复杂度退化为 \(O(n)\)$ \text{,比较次数} $\(n-1\),移动 0 次; - 冒泡排序(带提前结束标记版):最好时间复杂度退化为 \(O(n)\)$ \text{,比较次数} $\(n-1\),移动 0 次。 * 绝对状态惰性型(无论输入如何,时间复杂度纹丝不动): - 简单选择排序:无论是否有序,比较次数恒为 \(\frac{n(n-1)}{2}\)$ \text{,时间复杂度恒为} $\(O(n^2)\); - 二路归并排序:递归树与合并过程完全机械固定,时间复杂度恒为 \(O(n \log_2 n)\); - 堆排序:建堆与下滤筛选次数高度稳定,时间复杂度恒为 \(O(n \log_2 n)\); - 折半插入排序的比较次数:比较次数恒为 \(O(n \log_2 n)\)(但移动次数受输入状态轻微影响)。

(3) 比较次数与移动次数的非对称解题模型

在分析直接插入排序与简单选择排序的性能优劣时,切忌凭直觉混淆比较与移动: * 遇到“基本有序,为什么插入排序优于选择排序”:唯一核心原因在于比较次数的大幅缩减; * 遇到“为什么选择排序在某些特定场景仍有价值”:核心原因在于选择排序的移动次数被严格限制在 \(3(n-1) = O(n)\),若记录的数据域极大(如每个元素包含数千字节的大文本或大结构体),数据移动开销极度高昂时,选择排序的移动优势凸显。


2. 易错陷阱排查

  • 陷阱 1:误认为折半插入排序将时间复杂度降到了 \(O(n \log_2 n)\)
    病因剖析:折半查找确实将每趟定位的比较次数降为了 \(O(\log_2 i)\)$ \text{,总比较次数降为} $\(O(n \log_2 n)\)$ \text{。然而,数组的物理连续存储特性决定了腾出插入空位必须逐个平移元素,其移动次数在最坏与平均情况下依然是严格的} $\(\Theta(n^2)\)$ \text{。排序算法的总耗时由比较与移动共同决定,时间复杂度取决于二者的上限,故折半插入排序整体时间复杂度依然为} $\(O(n^2)\)。

  • 陷阱 2:误以为希尔排序包含直接插入排序,因而也是稳定的
    病因剖析:直接插入排序确实稳定,但希尔排序的跨步分组机制破坏了全局视角。相同关键字的记录在跨越步长 \(d > 1\) 的独立子序列重排时,由于跨步平移,原本在前的记录极易被跳跃到原本在后的记录之后。希尔排序是典型的不稳定排序。

  • 陷阱 3:混淆带哨兵机制中 \(A[0]\) 的存储内容与循环边界
    病因剖析:在带哨兵的直接插入排序代码中,\(A[0]\) 存放的是待插入元素本身。内层循环判定为 for (j = i - 1; A[0] < A[j]; --j)。考研选择题常在循环判断条件中挖坑,例如将条件篡改为 A[j] > A[0] && j >= 1(增加了冗余判断),或错写为 A[0] <= A[j](导致遇到相同元素依然继续左移,从而破坏了算法的稳定性,由稳定退化为不稳定)。

  • 陷阱 4:误以为直接插入排序必须在顺序表上执行
    病因剖析:直接插入排序与存储结构解耦良好,可以在单链表与双链表上顺畅实现。在链表上执行插入排序时,节点插入无需物理平移,指针修改耗时为 \(O(1)\)$ \text{,但查找插入点仍需} $\(O(n)\)$ \text{的顺序遍历,整体时间复杂度仍为} $\(O(n^2)\)。与之相对,折半插入排序则严格要求顺序存储结构,无法在链表上运行。


五、 考点速记清单

  1. 直接插入排序关键指标:
  2. 最好时间复杂度:\(O(n)\)$ \text{(完全正序,比较} $\(n-1\) 次,移动 0 次);
  3. 最坏时间复杂度:\(O(n^2)\)$ \text{(完全逆序,比较} $\(\approx \frac{n^2}{2}\)$ \text{次,移动} $\(\approx \frac{n^2}{2}\) 次);
  4. 平均时间复杂度:\(O(n^2)\)$ \text{(比较与移动均约为} $\(\frac{n^2}{4}\) 次);
  5. 空间复杂度:\(O(1)\)(原地排序);
  6. 稳定性:稳定。
  7. 折半插入排序关键指标:
  8. 比较次数:恒为 \(O(n \log_2 n)\)(与初始序列状态无关);
  9. 移动次数:最好 0 次,最坏与平均 \(O(n^2)\) 次;
  10. 总时间复杂度:\(O(n^2)\)$ \text{;空间复杂度:} $\(O(1)\);
  11. 稳定性:稳定;
  12. 存储约束:仅支持顺序存储,无法应用于链表。
  13. 希尔排序关键指标:
  14. 时间复杂度:平均约 \(O(n^{1.3})\)$ \text{,最坏} $\(O(n^2)\)$ \text{或} $\(O(n^{1.5})\)(取决于增量序列);
  15. 空间复杂度:\(O(1)\);
  16. 稳定性:不稳定;
  17. 增量收敛终点:最后一个增量必须严格为 \(d_t = 1\)。
  18. 两类经典反常识特性:
  19. 插入排序(直接、折半、希尔)在每一趟结束时,均不能确定任何一个元素的最终全局绝对位置;
  20. 基本有序时直接插入排序效率碾压简单选择排序,本质原因是插入排序比较次数锐减到 \(O(n)\)$ \text{,而选择排序比较次数死板锁定在} $\(\frac{n(n-1)}{2}\)。
  21. 工程核心价值口诀:
  22. 数据量小或基本有序,首选直接插入;
  23. 比较代价极高且支持随机访问,采用折半插入;
  24. 海量流式数据维护 Top-K,固定有序窗口单次 \(O(k)\) 插入淘汰。