Appearance
直接插入排序
为什么需要直接插入排序
直接插入排序是最直观、最易理解的排序算法之一。它的思想来源于日常生活——就像打扑克牌时，每摸到一张新牌，就将它插入手中已排好序的牌的正确位置。
在 408 考研中，直接插入排序是排序章节的起点，也是理解希尔排序的基础。掌握它的原理和性能特征，是分析更复杂排序算法的前提。
核心思想
直接插入排序的核心思想：
- 将待排序序列分为「已排序」和「未排序」两部分：初始时已排序部分只有第一个元素
- 逐个插入：每次从未排序部分取出第一个元素，在已排序部分中从后向前扫描，找到合适位置插入
- 有序区不断扩大：每插入一个元素，已排序部分长度加 1，直到全部元素有序
排序过程示意（升序）：
初始: [49] | 38 65 97 76 13 27
第1趟: [38 49] | 65 97 76 13 27
第2趟: [38 49 65] | 97 76 13 27
第3趟: [38 49 65 97] | 76 13 27
第4趟: [38 49 65 76 97] | 13 27
第5趟: [13 38 49 65 76 97] | 27
第6趟: [13 27 38 49 65 76 97]其中 [] 内为已排序部分，| 右侧为未排序部分。
交互可视化
通过下方的交互动画，你可以逐步观察直接插入排序的执行过程：
操作详解
算法思路
关键步骤：
- 从第 2 个元素开始，将其作为待插入元素
temp - 在已排序部分中从后向前扫描，将大于
temp的元素依次后移 - 找到
temp应插入的位置，将其放入 - 重复以上过程直到所有元素排完
不带哨兵的实现：
c
void InsertSort(int A[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) { // 从第2个元素开始
if (A[i] < A[i - 1]) { // 若当前元素小于前驱
temp = A[i]; // 暂存待插入元素
for (j = i - 1; j >= 0 && A[j] > temp; j--)
A[j + 1] = A[j]; // 元素后移
A[j + 1] = temp; // 插入到正确位置
}
}
}带哨兵的实现（⭐ 考研重点）：
将 A[0] 作为哨兵，数据元素从 A[1] 开始存储。哨兵的作用是免去查找过程中每次循环都要判断 j >= 1 是否越界，从而简化边界条件、提高效率。
c
void InsertSort(int A[], int n) {
int i, j;
for (i = 2; i <= n; i++) { // A[1]~A[n]存放元素
if (A[i] < A[i - 1]) {
A[0] = A[i]; // A[0]作为哨兵
for (j = i - 1; A[0] < A[j]; j--)
A[j + 1] = A[j]; // 元素后移
A[j + 1] = A[0]; // 插入到正确位置
}
}
}注意：使用哨兵时，
A[0]不存放实际数据，数组需多分配一个空间。
排序过程详解
以序列 [49, 38, 65, 97, 76, 13, 27] 为例，展示每一趟的操作：
| 趟数 | 待插入元素 | 比较与移动过程 | 排序结果 |
|---|---|---|---|
| 1 | 38 | 38 < 49，49 后移，38 插入位置 1 | [38, 49, 65, 97, 76, 13, 27] |
| 2 | 65 | 65 > 49，无需移动 | [38, 49, 65, 97, 76, 13, 27] |
| 3 | 97 | 97 > 65，无需移动 | [38, 49, 65, 97, 76, 13, 27] |
| 4 | 76 | 76 < 97，97 后移；76 > 65，插入 | [38, 49, 65, 76, 97, 13, 27] |
| 5 | 13 | 依次与 97、76、65、49、38 比较并后移 | [13, 38, 49, 65, 76, 97, 27] |
| 6 | 27 | 依次与 97、76、65、49、38 比较并后移；27 > 13 | [13, 27, 38, 49, 65, 76, 97] |
每一趟排序后，前 i+1 个元素构成有序序列。共需 n-1 趟排序。
稳定性分析
直接插入排序是稳定的排序算法。
原因：在从后向前扫描已排序部分时，遇到与待插入元素相等的元素就会停止扫描，将待插入元素放在相等元素的后面。因此，相同关键字的元素在排序前后的相对顺序不会改变。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间复杂度 | O(n) | 序列已有序，每趟只比较 1 次，不移动 |
| 最坏时间复杂度 | O(n²) | 序列逆序，每趟比较 i 次并移动 i+1 次 |
| 平均时间复杂度 | O(n²) | 平均比较和移动次数约为 n²/4 |
| 空间复杂度 | O(1) | 仅需常数级辅助空间（temp / 哨兵） |
适用场景：直接插入排序在序列基本有序或数据量较小时效率较高，是小规模排序的首选算法。
考研高频考点
- ⭐ 哨兵的作用及带哨兵代码的手写（代码题/填空题高频）
- ⭐ 最好/最坏/平均时间复杂度及对应的输入情况（选择题必考）
- ⭐ 稳定性判断及原因说明（简答题/选择题高频）
- ⭐ 给定序列写出每趟排序结果（选择题/填空题）
- 与希尔排序的关系与对比（希尔排序是插入排序的改进）
- 适用场景分析：基本有序 / 小规模数据时优于 O(n log n) 算法