插入排序#

插入类排序的核心思想：将元素插入到已排序序列的合适位置。代表算法有直接插入排序、折半插入排序和希尔排序。

直接插入排序#

核心思想#

将待排序序列分为已排序和未排序两部分，初始时已排序部分只有第一个元素
每次从未排序部分取出第一个元素，在已排序部分中从后向前扫描，找到合适位置插入
有序区不断扩大，直到全部元素有序

代码实现#

带哨兵的实现（⭐ 考研重点）：

1
void InsertSort(int A[], int n) {
2
    int i, j;
3
    for (i = 2; i <= n; i++) {
4
        if (A[i] < A[i - 1]) {
5
            A[0] = A[i];              // A[0]作为哨兵
6
            for (j = i - 1; A[0] < A[j]; j--)
7
                A[j + 1] = A[j];
8
            A[j + 1] = A[0];
9
        }
10
    }
11
}

哨兵的作用：免去内层循环每次判断 j >= 1 是否越界，简化边界条件。

复杂度#

指标	值	说明
最好时间	O(n)	序列已有序，每趟只比较 1 次
最坏时间	O(n²)	序列逆序
平均时间	O(n²)	平均比较和移动次数约 n²/4
空间	O(1)	仅常数级辅助空间
稳定性	稳定	相等元素不交换

折半插入排序#

改进点#

用折半查找替代顺序查找来定位插入位置，比较次数降为 O(log i)，但移动次数不变。

关键代码#

1
void BinaryInsertionSort(int a[], int n) {
2
    int i, j, low, high, mid, temp;
3
    for (i = 1; i < n; i++) {
4
        temp = a[i];
5
        low = 0; high = i - 1;
6
        while (low <= high) {
7
            mid = (low + high) / 2;
8
            if (a[mid] > temp) high = mid - 1;
9
            else low = mid + 1;    // 相等时进入右半，保证稳定性
10
        }
11
        for (j = i - 1; j >= low; j--)
12
            a[j + 1] = a[j];
13
        a[low] = temp;
14
    }
15
}

与直接插入的对比#

维度	直接插入	折半插入
比较次数	最好 O(n)，最坏 O(n²)	总 O(n log n)
移动次数	O(n²)	O(n²)
总时间复杂度	O(n²)	O(n²)
稳定性	稳定	稳定

⚠️ 易错：折半插入只减少比较次数，不减少移动次数，时间复杂度仍为 O(n²)。

希尔排序#

核心思想#

选定增量序列 d₁ > d₂ > … > dₖ = 1
每趟按当前增量 dᵢ 将序列分组，对各组执行直接插入排序
增量不断缩小，最后一趟 d=1 时对”几乎有序”的序列做插入排序

代码实现#

1
void ShellSort(int A[], int n) {
2
    for (int d = n / 2; d >= 1; d /= 2) {
3
        for (int i = d; i < n; i++) {
4
            int temp = A[i];
5
            int j = i - d;
6
            while (j >= 0 && A[j] > temp) {
7
                A[j + d] = A[j];
8
                j -= d;
9
            }
10
            A[j + d] = temp;
11
        }
12
    }
13
}

增量序列#

序列	公式	最坏时间
Shell 原始	dᵢ = n/2ⁱ	O(n²)
Hibbard	dᵢ = 2ⁱ - 1	O(n^1.5)
Knuth	dᵢ = (3ⁱ - 1)/2	O(n^1.5)

⭐ 考试默认使用 Shell 原始序列（d = n/2, n/4, …, 1），最后一个增量必须为 1。

复杂度#

指标	值
最坏时间	O(n²)（Shell 原始序列）
平均时间	~O(n^1.3)
空间	O(1)
稳定性	不稳定（相同元素可能分到不同组）
适用性	仅限顺序表（需随机访问）

⚠️ 易错：希尔排序不稳定，相同元素可能分到不同组中，各组独立排序后相对顺序可能改变。

考研高频考点#

⭐ 给定序列写出每趟直接插入/希尔排序的结果（选择题/填空题）
⭐ 哨兵的作用及带哨兵代码的手写（代码题）
⭐ 希尔排序与直接插入排序的关系与对比
⭐ 折半插入排序的比较次数与初始序列无关（仅取决于 n）
⭐ 希尔排序不能用于链表（需要随机访问）
直接插入在基本有序序列上的时间复杂度 O(n)（408 经典选择题）

关联页面#

排序基础概念 — 稳定性、分类、趟的概念
交换排序 — 冒泡、快速排序
选择排序 — 简单选择、堆排序
归并排序

音乐

音乐

插入排序#

直接插入排序#

核心思想#

代码实现#

复杂度#

折半插入排序#

改进点#

关键代码#

与直接插入的对比#

希尔排序#

核心思想#

代码实现#

增量序列#

复杂度#

考研高频考点#

关联页面#

文章分享

评论区