插入类排序

概念

插入类排序的基本思路只有一个动作：把当前元素插到前面已经排好的"有序区"里的正确位置。

• 直接插入排序（straight insertion sort）：从有序区末尾往前逐个比较，边比边后移，找到位置就插入。
• 折半插入排序（binary insertion sort）：有序区既然已经有序，找位置就不必逐个比——用折半查找定位。
• 希尔排序（Shell sort）：先按一个较大的增量把序列分成若干子序列各自插入排序，再逐步缩小增量，最后增量 = 1 时整体有序。

三者的关系是层层递进的：折半插入只优化了"找位置"这一步，希尔则把"每次只移动一位"变成了"每次跨越一大段"。只有希尔排序真正突破了 O(n²)。

一句话记忆：直接插入是"打扑克摸牌插牌"，折半插入是"先折半数清该插哪再插"，希尔是"先隔几个位置比一比，把大的乱的先大致理顺"。

原理

一、直接插入排序

把序列看成 [已排好的有序区] [待处理的元素 x | 未处理的区]，每一趟取 $x$ 与有序区从后往前比较：

1. 若 $x$ 比当前元素小，就把当前元素后移一位，继续往前比；
2. 直到遇到不比 $x$ 大的元素（或走到头），把 $x$ 放进它后面的空位。

哨兵技巧：把 a[0] 空出来，临时存放待插入的 $x$。这样内层循环不必判断下标越界——$x$ 与"哨兵自己"比较必然不满足 <，循环自然终止。代价是数组要 0 号位空闲，且多一次赋值移动。

    初始:  [49  38  65  97  76  13  27  49*]
        ┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
    以 49 为有序区起点，从第 2 个元素起逐个插入 →

复杂度：

情况	比较次数	移动次数	时间
最好（原序列正序）	$n-1$	0	O(n)
最坏（原序列逆序）	${\displaystyle \frac{(n+2)(n-1)}{2}}$	${\displaystyle \frac{(n+4)(n-1)}{2}}$	O(n²)
平均	—	—	O(n²)

空间 O(1)，稳定（相等元素不会越过彼此：判断条件是 > 而非 >=）。

二、折半插入排序

有序区长度为 $i-1$ 时，用折半查找确定 $x$ 的插入位置，每趟比较次数从"最多 $i-1$ 次"降到"最多 $\lceil {\log }_{2}i\rceil$ 次"。

但移动次数一点没省——找到位置后仍要把后面所有元素整体后移，仍是 O(n²) 量级。所以总时间复杂度仍是 O(n²)，只是比较次数降到约 O(n log n)。

结论要点：折半插入只减少比较次数，不减少移动次数。 因此它适合"比较代价高、移动代价低"的场景（如记录很大但用指针数组存放时的反例）。

三、希尔排序

思路分两步：

1. 取一个增量 $d$（$d<n$），把下标相隔 $d$ 的元素看成一组，各组分别做直接插入排序；
2. 逐步缩小 $d$（如 $d=d/2$ 或 $d$ 取固定序列），重复第 1 步；
3. 当 $d=1$ 时，整表做一次直接插入排序，因为序列已"基本有序"，这一趟移动量很小，序列完成排序。

为什么能突破 O(n²)：直接插入排序的代价来自"每次只能把元素挪动一位"，遇到逆序对多的序列就会反复长距离搬运。希尔排序先用大增量比较远距离的元素，一次比较就能消除远距离的逆序，序列快速变得"基本有序"，最后 $d=1$ 的插入排序代价被压到接近 O(n)。

  例：n = 8，增量取 5, 3, 1

  d = 5：分成 5 组，每组内相隔 5 个位置
     (1,6) (2,7) (3,8) (4) (5)

  d = 3：分成 3 组
     (1,4,7) (2,5,8) (3,6)

  d = 1：整表一组 —— 最终一趟普通插入排序

性能取决于增量序列，这是希尔排序最特殊的一点：

增量序列	时间复杂度
$\lfloor n/2\rfloor ,\lfloor n/4\rfloor ,\dots ,1$（折半缩小）	平均约 $O(n^{1.5})$
Hibbard：$2^k-1$	$O(n^{1.5})$
Sedgewick 序列	最坏 $O(n^{4/3})$

无论哪种，至今没有证明出最优增量序列。其他性质：不稳定、只能用于顺序存储（要按增量"跳着"访问，链式存储做不了随机访问）。

示例

以下推演统一使用序列 49, 38, 65, 97, 76, 13, 27, 49*（末尾的 49* 与开头的 49 相等，专门用来观察稳定性）。

例 1：直接插入排序逐趟推演

趟次	待插入	动作	结果
初始	—	—	49 38 65 97 76 13 27 49*
1	38	49 后移，38 放首位	38 49 65 97 76 13 27 49*
2	65	65 > 49，原地不动	38 49 65 97 76 13 27 49*
3	97	97 > 65，原地不动	38 49 65 97 76 13 27 49*
4	76	97 后移，76 插到 65 后	38 49 65 76 97 13 27 49*
5	13	97、76、65、49、38 全后移，13 放首位	13 38 49 65 76 97 27 49*
6	27	97、76、65、49、38 后移，27 插到 13 后	13 27 38 49 65 76 97 49*
7	49*	97、76、65 后移，49* 插到 49 之后	13 27 38 49 49* 65 76 97

关键观察：第 7 趟插入 49* 时，49* 排在原来的 49 之后——两个相等元素相对次序没变，这正是直接插入排序稳定的原因（内层判断用 a[j] > x，遇相等即停，不会把 49* 越过 49）。

例 2：精确次数计算（n = 8，逆序输入）

对 8 个元素的逆序序列（如 8 7 6 5 4 3 2 1）做直接插入排序，求比较次数与移动次数。

第一步，逐趟分析（第 $i$ 趟插入第 $i$ 个元素，$i=2,\dots ,8$）：

元素 $i$ 前面有 $i-1$ 个元素，全是逆序排列故全部大于它：需要 $i-1$ 次"元素比较 + 后移"，再加 1 次与哨兵的比较（终止条件）→ 该趟比较 $i$ 次、移动 $i-1+2=i+1$ 次（$+2$ 是"存入哨兵"与"从哨兵取出放回"）。

第二步，比较次数求和：

$$\sum _{i=2}^{n}i=2+3+\cdots +8=\frac{(2+8)\times 7}{2}=35=\frac{(n+2)(n-1)}{2}=\frac{10\times 7}{2}$$

第三步，移动次数求和：

$$\sum _{i=2}^n(i+1)=3+4+\cdots +9=\frac{(3+9)\times 7}{2}=42=\frac{(n+4)(n-1)}{2}=\frac{12\times 7}{2}$$

结论：逆序 n = 8 时，比较 35 次、移动 42 次。而正序时比较仅 $n-1=7$ 次、移动 0 次——相差 5 倍以上，这就是"初始有序度"对插入排序的巨大影响。

例 3：希尔排序逐趟推演

增量取 5, 3, 1：

第一步，$d=5$（组内直接插入）：

• 组 $(49,13)$ → $49>13$ 交换 → 第 1、6 位变 13 和 49
• 组 $(38,27)$ → $38>27$ 交换 → 第 2、7 位变 27 和 38
• 组 $(65,{49}^{\ast })$ → $65>49$ 交换 → 第 3、8 位变 49 和 65
• 组 $(97)$、$(76)$ 单元素，无需处理

    d=5 后:  13  27  49  97  76  49*  38  65

第二步，$d=3$：

• 组 $(13,97,38)$ → 排为 $(13,38,97)$ → 第 1、4、7 位 = 13, 38, 97
• 组 $(27,76,65)$ → 排为 $(27,65,76)$ → 第 2、5、8 位 = 27, 65, 76
• 组 $(49,{49}^{\ast })$ → 已有序

    d=3 后:  13  27  49  38  65  49*  97  76

第三步，$d=1$：整表做一次直接插入排序（此时已基本有序，移动量很小）：

    d=1 后:  13  27  38  49  49*  65  76  97

注意 49 与 49* 在 d = 3 那一趟被放进了同一组 $(49,{49}^{\ast })$，此时它们已归位；若增量序列导致相等元素在不同组中互相跳跃，相对次序就可能颠倒——这是希尔排序不稳定的根源。本例的 49, 49* 恰好侥幸保持了次序，但一般情形不能保证。

C 语言：三种插入排序

#include <stdio.h>

/* ---------- 1. 直接插入排序（下标 0 当哨兵） ---------- */
void insertSort(int a[], int n) {
    for (int i = 2; i <= n; i++) {
        a[0] = a[i];                 /* 哨兵：兼作临时变量与越界挡板 */
        int j = i - 1;
        while (a[j] > a[0]) {        /* 遇哨兵必停，不必判 j >= 1 */
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = a[0];
    }
}

/* ---------- 2. 折半插入排序 ---------- */
void binaryInsertSort(int a[], int n) {
    for (int i = 2; i <= n; i++) {
        a[0] = a[i];
        int low = 1, high = i - 1;
        while (low <= high) {                     /* 折半找插入位置 */
            int mid = (low + high) / 2;
            if (a[mid] > a[0]) high = mid - 1;    /* 位置在左半区 */
            else               low = mid + 1;     /* 相等时往右走，保证稳定 */
        }                                         /* 循环结束时 high+1 == low */
        for (int j = i - 1; j >= high + 1; j--)   /* 统一后移，不再边比边移 */
            a[j + 1] = a[j];
        a[high + 1] = a[0];
    }
}

/* ---------- 3. 希尔排序（增量折半缩小） ---------- */
void shellSort(int a[], int n) {
    for (int d = n / 2; d >= 1; d /= 2) {
        for (int i = d + 1; i <= n; i++) {        /* 各组轮流插入 */
            a[0] = a[i];
            int j = i - d;
            while (j > 0 && a[j] > a[0]) {        /* 跨增量比较（需判边界） */
                a[j + d] = a[j];
                j -= d;
            }
            a[j + d] = a[0];
        }
    }
}

int main(void) {
    int s1[9] = {0, 49, 38, 65, 97, 76, 13, 27, 49};
    int s2[9] = {0, 49, 38, 65, 97, 76, 13, 27, 49};
    int s3[9] = {0, 49, 38, 65, 97, 76, 13, 27, 49};

    insertSort(s1, 8);
    binaryInsertSort(s2, 8);
    shellSort(s3, 8);

    printf("直接插入: "); for (int i = 1; i <= 8; i++) printf("%d ", s1[i]); printf("\n");
    printf("折半插入: "); for (int i = 1; i <= 8; i++) printf("%d ", s2[i]); printf("\n");
    printf("希尔排序: "); for (int i = 1; i <= 8; i++) printf("%d ", s3[i]); printf("\n");
    /* 三者结果相同：13 27 38 49 49 65 76 97 */
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出三行相同的 13 27 38 49 49 65 76 97——三种算法结果一致，差别只在比较/移动次数与稳定性。

Python 对照

def insertion_sort(a):
    """直接插入：不设哨兵，用 Python 的边界检查代替"""
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and a[j] > x:   # 注意 > 而非 >=，保证稳定
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a

def binary_insertion_sort(a):
    """折半插入：bisect 定位 + 整体后移"""
    import bisect
    for i in range(1, len(a)):
        x = a[i]
        pos = bisect.bisect_right(a[:i], x)   # bisect_right 保证稳定
        a[pos + 1:i + 1] = a[pos:i]
        a[pos] = x
    return a

def shell_sort(a, gaps=None):
    """希尔排序：默认用 5,3,1（演示用），实际可取 n//2, n//4, ..."""
    a = a[:]
    if gaps is None:
        n = len(a); gaps = []
        d = n // 2
        while d >= 1:
            gaps.append(d); d //= 2
    for d in gaps:
        for i in range(d, len(a)):
            x, j = a[i], i - d
            while j >= 0 and a[j] > x:
                a[j + d] = a[j]
                j -= d
            a[j + d] = x
    return a

src = [49, 38, 65, 97, 76, 13, 27, 49]
print(insertion_sort(src[:]))
print(binary_insertion_sort(src[:]))
print(shell_sort(src[:]))
print(shell_sort(src[:], gaps=[5, 3, 1]))   # 与正文推演一致

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

考点

1. 必背结论

算法	最好时间	最坏时间	平均时间	空间	稳定性	备注
直接插入	O(n)	O(n²)	O(n²)	O(1)	稳定	正序时比较 n−1 次、移动 0 次
折半插入	O(n log n)（比较）	O(n²)	O(n²)	O(1)	稳定	只省比较，不省移动
希尔排序	—	依赖增量序列	约 $O(n^{1.3})$	O(1)	不稳定	只能顺序存储

• 直接插入排序适合基本有序、元素个数较少的序列；这是它优于快排、归并的现实场景。
• 折半插入的比较次数与初始序列基本无关（只与元素个数有关），这与直接插入恰好相反。
• 希尔排序的时间复杂度与增量序列有关，且是三者中唯一不稳定的。

2. 手算套路

• 手写逐趟结果：把序列画成一竖排，用一个竖线分隔"有序区 | 无序区"，逐趟把竖线右移一格，写字比心算快很多。
• 数比较/移动次数：先判断"该趟要移动几个元素"，再统一加哨兵的 2 次移动。别在逐趟过程里数，容易漏。
• 希尔排序推演：先按增量把下标分组写出来（如 $d=5$ 时列出 $(1,6)(2,7)(3,8)(4)(5)$），再组内插入，最后拼回去。

3. 易错点

• 把哨兵那 2 次移动漏掉：带哨兵实现里，每趟都有 a[0]=a[i] 和 a[j+1]=a[0] 两次移动，移动次数公式 $(n+4)(n-1)/2$ 已含这 2 次；若按"仅元素后移"算则是 $(n+4)(n-1)/2-2(n-1)$。题目问的是哪一种，要看它给的实现代码。
• "折半插入更快"是错的：总比较次数降为 O(n log n)，但移动次数与直接插入相同，移动占主导，所以总时间仍是 O(n²)。
• 希尔排序的稳定性：常有人因为"分组内部是插入排序，插入排序稳定"就误判希尔稳定。反例：序列 2, 1, 1*，取 $d=2$，组 $(2,1^{\ast })$ 排序后会变成 1*, 1, 2，1 与 1* 次序颠倒。
• 希尔排序不能用于链式存储：需要按下标跳跃访问，链表不支持随机存取。
• 直接插入排序的稳定性来自判断条件：写成 while (a[j] >= a[0]) 会变成不稳定排序，同时移动次数增加。考试分析稳定性时，一定要看代码里那个 > / >=。
• "基本有序时插入排序最快"这个结论对快排不成立：快排取首元素为枢轴时，正序输入反而退化成最坏情况 O(n²)。这一点在第 41 篇反复出现。

小结

• 插入类排序只有一个核心动作：把当前元素插进前面有序区的正确位置。
• 直接插入：正序 O(n)、逆序 O(n²)，稳定；比较与移动的精确公式是真题常客。
• 折半插入：只把"找位置"从 O(i) 降到 O(log i)，移动次数不变，总时间仍 O(n²)，仍稳定。
• 希尔排序：靠缩小增量让序列先"基本有序"，从而突破 O(n²)；代价是不稳定、只能顺序存储、复杂度依赖增量序列。
• 三者共同的天花板：都靠"移动元素"腾位置，因此谁也无法在不借助额外结构的情况下做到 O(n log n)。
• 下一步：换一类思路——不再搬运元素，而是交换元素，这就是冒泡与快速排序。

下一篇：交换类排序：冒泡、快速排序