| 项目 | 值 |
|---|---|
| 核心思想 | 将待排序元素插入到已排序子序列的正确位置 |
| 最好时间 | $O(n)$（已有序，只比较不移动） |
| 最坏时间 | $O(n^2)$（逆序） |
| 平均时间 | $O(n^2)$ |
| 空间 | $O(1)$ |
| 稳定性 | ✅ 稳定 |
| 适用场景 | 基本有序的小规模数据 |
直接插入排序是最基本的插入排序算法。它将数组分为已排序和未排序两部分，每次从未排序部分取出第一个元素，插入到已排序部分的正确位置。
核心思想：从第 2 个元素开始，将当前元素与已排序部分从后往前逐个比较，找到合适位置后插入。
void InsertSort(int A[], int n) {
int i, j;
for (i = 2; i <= n; i++) { // 从第2个元素开始
if (A[i] < A[i-1]) { // 需要插入
A[0] = A[i]; // 暂存到哨兵
for (j = i-1; A[0] < A[j]; j--) // 从后往前找
A[j+1] = A[j]; // 后移
A[j+1] = A[0]; // 插入
}
}
}对 49, 38, 65, 97, 76, 13, 27, 49* 排序：
初始: [49] 38 65 97 76 13 27 49*
i=2: [38 49] 65 97 76 13 27 49* (38插入49前)
i=3: [38 49 65] 97 76 13 27 49* (65已在正确位置)
i=4: [38 49 65 97] 76 13 27 49* (97已在正确位置)
i=5: [38 49 65 76 97] 13 27 49* (76插入65和97之间)
i=6: [13 38 49 65 76 97] 27 49* (13插入最前)
i=7: [13 27 38 49 65 76 97] 49* (27插入13和38之间)
i=8: [13 27 38 49 49* 65 76 97] (49*插入49和65之间)| 性质 | 说明 |
|---|---|
| 最好时间 | $O(n)$，序列已有序，每轮只比较 1 次 |
| 最坏时间 | $O(n^2)$，序列逆序，每轮比较 i 次 + 移动 i-1 次 |
| 平均时间 | $O(n^2)$，约 $n^2/4$ 次比较和移动 |
| 空间复杂度 | $O(1)$，原地排序 |
| 稳定性 | 稳定（相等元素不交换） |
| 适用性 | 顺序表和链表均可 |
| 趟数 | n-1 趟 |