插入排序（Insertion Sort）深度解析：《Hello 算法》排序章节的稳定基石与实战指南

2026-09-07 11:54:56作者：明树来

导读

本文以《Hello 算法》英文文档 insertion_sort.md 为主体，系统讲解插入排序（Insertion Sort）的思想、完整算法流程、复杂度与稳定性分析，并对照本仓库 en/codes 下十余种语言的源码实现逐行解读。读完本文，你将能独立看懂并手写任何主流语言的插入排序，理解它“在小数据上反而比快排更快”“常用于语言内建排序函数底段”的工程结论，以及它为何在冒泡、选择、插入三种 $O (n^{2})$ 排序中胜出。

1. 核心思想：像整理扑克牌一样排序

插入排序是一种非常直观的简单排序算法，其工作方式与人手整理扑克牌的过程高度相似：每一轮从“未排序区间”中取出一个基准元素 base，把它与左侧“已排序区间”中的元素逐个比较，然后插入到正确的位置。

在 insertion_sort.md 中，作者用下图刻画了“单次插入操作”的完整细节：先将 base 临时存储，把已排序区间中所有大于 base 的元素依次右移一位（nums[j + 1] = nums[j]），最后把 base 赋值到腾出的目标下标，数组变为有序。

图注要点：图中以虚线框出已排序区间（如 1, 1, 2, 4, 5），最右侧的待插元素 3 被标记为 base；插入完成后数组变为 [1, 1, 2, 3, 4, 5]。

1.1 算法整体流程

插入排序的整体流程如下图所示，其推进方式是一种典型的“扩大已排序前缀”策略：

初始时，数组的第一个元素天然处于“已排序”状态；
取第二个元素作为 base，将其插入正确位置后，前 2 个元素有序；
取第三个元素作为 base，插入后前 3 个元素有序；
依此类推，最后一轮取最后一个元素作为 base 并插入后，整个数组有序。

图中每一轮都会标注当前的已排序区间 [0, k]，并用绿色标出本轮待插入的 base，直观地展示了“前 k+1 个元素逐轮有序”的不变式。

1.2 参考实现（多语言）

文档正文给出的示例代码，在本仓库 en/codes/chapter_sorting 目录下针对每种受支持语言均有完整可运行实现。下面是 Python 版本 insertion_sort.py：

def insertion_sort(nums: list[int]):
    """Insertion sort"""
    # Outer loop: sorted interval is [0, i-1]
    for i in range(1, len(nums)):
        base = nums[i]
        j = i - 1
        # Inner loop: insert base into the correct position within the sorted interval [0, i-1]
        while j >= 0 and nums[j] > base:
            nums[j + 1] = nums[j]  # Move nums[j] to the right by one position
            j -= 1
        nums[j + 1] = base  # Assign base to the correct position

结构上可以将代码拆解为两个层次理解：

外层循环（i 从 1 到 n-1）：维护“已排序区间为 [0, i-1]”这一不变式，每轮把下标 i 的元素取出作为 base，即文档中所说的“扩大已排序前缀”；
内层循环（j 从 i-1 向左扫描）：只要左侧元素大于 base，就把它右移一位（元素后移）；循环终止时的 j + 1 即为 base 的插入位置。

关键点在于：右移与比较合并到了同一个循环中，base 已经被暂存，因此覆盖 nums[j+1] 不会丢失数据，这正是插入排序可以做到单次“赋值”完成一次移动的原因（见第 4 节）。

同样逻辑在其他语言的实现中完全一致，例如 insertion_sort.cpp、insertion_sort.java：

/* Insertion sort */
void insertionSort(vector<int> &nums) {
    // Outer loop: sorted interval is [0, i-1]
    for (int i = 1; i < nums.size(); i++) {
        int base = nums[i], j = i - 1;
        // Inner loop: insert base into the correct position within the sorted interval [0, i-1]
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j]; // Move nums[j] to the right by one position
            j--;
        }
        nums[j + 1] = base; // Assign base to the correct position
    }
}

需要说明的语言差异：C 语言中数组不携带长度信息，因此 insertion_sort.c 的函数签名多了一个 int size 参数（void insertionSort(int nums[], int size)）；Go 版本 insertion_sort.go 则通过 len(nums) 直接取得长度。除此之外，各语言的内外层循环骨架与 base 右移逻辑完全同构。

本仓库各语言插入排序实现文件汇总如下，可直接对照阅读：

语言	文件路径
Python	insertion_sort.py
C++	insertion_sort.cpp
Java	insertion_sort.java
C	insertion_sort.c
Go	insertion_sort.go
Rust	insertion_sort.rs
TypeScript	insertion_sort.ts
JavaScript	insertion_sort.js
C#	insertion_sort.cs
Swift	insertion_sort.swift
Dart	insertion_sort.dart
Kotlin	insertion_sort.kt
Ruby	insertion_sort.rb

2. 算法特性：自适应、原地、稳定

insertion_sort.md 的第 28 行起给出了插入排序的三个核心算法特性，下面逐条展开。

2.1 时间复杂度 $O (n^{2})$ ，且是自适应排序

最坏情况：若输入数组完全逆序，内层循环在每一轮几乎都要扫描完整个已排序区间。第 $i$ 轮需要 $i$ 次比较/移动，各轮分别需要 $n-1, n-2, \dots, 2, 1$ 次迭代，求和为 $(n - 1) n / 2$ ，故最坏时间复杂度为 $O (n^{2})$ 。

最好情况：若输入数组已经完全有序，每一轮内层循环在第一次比较（nums[j] > base 为假）时就立即终止，算法只做 $n - 1$ 次外层迭代即完成排序，达到最优的 $O (n)$ 。

平均情况：约为 $O (n^{2})$ 。

这种“数据越有序，耗时越少”的特性正是文档（也是本书 sorting_algorithm.md 的术语体系）所称的 自适应排序（adaptive sorting）：算法能够利用输入数据中已存在的有序信息来减少计算量，其最好时间复杂度显著优于平均复杂度。

2.2 空间复杂度 $O (1)$ ，原地排序

整个排序过程中仅额外使用了指针/下标 i、j 与暂存变量 base，均为常数规模，故空间复杂度为 $O (1)$ ，属于原地排序（in-place sorting）。相比归并排序等需要辅助数组的算法，它不占用额外内存。

2.3 稳定排序

插入排序通过条件 nums[j] > base 严格用“大于”才后移，也就是说：当遇到与 base 相等的元素时立即停止右移，base 会被放到这些相等元素的右侧，因此相等元素的相对次序保持不变，属于稳定排序（stable sorting）。

稳定性是多级排序（如先按姓名排、再按年龄排）的必要条件。在 sorting_algorithm.md 中作者用了一个 (姓名, 年龄) 元组示例说明：若先用不稳定算法按年龄排序，可能会破坏“输入数据已按姓名有序”这一性质；而插入排序的稳定性使其可以安全地用于此类多级排序场景。

2.4 特性速览表

评价维度	插入排序结论
最好时间复杂度	$O (n)$ （数据已有序，内层循环提前终止）
最坏/平均时间复杂度	$O (n^{2})$
空间复杂度	$O (1)$ （原地排序）
稳定性	稳定（相等元素放在右侧，相对次序不变）
适应性	自适应（可利用输入数据的既有有序性）
比较方式	基于比较的排序

3. 为什么小数据集上插入排序反而比快速排序快？

这是 insertion_sort.md 中最具工程指导意义的一个结论：插入排序的复杂度是 $O (n^{2})$ ，而后续章节将学习的快速排序是 $O(n \log n)$ ，但插入排序在小数据集上通常更快。

其原因与“线性查找与二分查找各有所长”的结论（见 searching_algorithm_revisited.md）在原理上一脉相承：快速排序这类 $O(n \log n)$ 算法本质是分治策略，每一层递归、每轮分区都需要执行较多“基础操作（primitive operations）”。当数据规模 $n$ 很小时， $n^{2}$ 与 $n \log n$ 的数值差距不大，渐近复杂度不再起决定作用，每轮迭代所执行的基础操作数量反而成为主导因素——此时常数更大的快排反而不如实现极简的插入排序。

文档明确指出：许多编程语言（如 Java）的内建排序函数正是采用这种混合策略——对于大数组使用快速排序等分治排序算法，对于短数组直接回退到插入排序。这解释了为什么虽然三者同为 $O (n^{2})$ ，插入排序却成为工业级排序库中“小数组兜底”的首选。

4. 同门对比：插入排序 vs 冒泡排序 vs 选择排序

冒泡排序、选择排序与插入排序的时间复杂度同为 $O (n^{2})$ ，但在实际工程中插入排序的使用频率远高于前两者。文档给出了三点理由，下面结合源码逐一说明。

4.1 移动开销更小：1 次赋值 vs 3 次赋值

冒泡排序通过“交换元素（swap）”推进排序，而一次 swap 通常需要借助临时变量、执行 3 次赋值（3 个基础操作）；插入排序通过“元素后移 + 回填 base”实现，单次移动只需 1 次赋值。从 insertion_sort.md 第 44 行的分析可知，同样的移动量下冒泡排序的计算开销明显高于插入排序。这既是文档论点，也可从上述各语言源码中直接核对：冒泡排序的 swap 对应 3 行赋值，而插入排序内层循环每一轮移动只执行 nums[j + 1] = nums[j] 一条赋值语句。

4.2 对部分有序数据更友好

选择排序无论输入是否有序，都必须完整扫描未排序区间找出极值，复杂度恒为 $O (n^{2})$ ，不具适应性；而插入排序一旦发现左侧元素不大于 base 就会提前终止内层循环。因此当输入是“部分有序”的数据时，插入排序通常比选择排序高效得多——这与第 2.1 节的自适应特性互为表里。

4.3 稳定性差异决定适用面

选择排序不是稳定排序，无法用于多级排序场景；而插入排序稳定。这一差异把“能否承担多级排序”的适用边界清晰地划分了出来。此外，选择排序的实现还会“越过”相等元素（从稳定性角度破坏原有顺序），因此即便不考虑效率，二者在语义上也并不等价。

5. 动手验证：如何运行仓库中的插入排序

仓库中的每个实现都带有可直接运行的 driver code，这里以最容易上手的两条路径说明。

Python（无需编译，直接执行 insertion_sort.py）：

cd en/codes/python/chapter_sorting
python insertion_sort.py
# After insertion sort, nums = [1, 1, 2, 3, 4, 5]

代码内部使用测试数组 nums = [4, 1, 3, 1, 5, 2]，其中包含重复元素 1——这恰好可以顺带验证稳定性：两个 1 排序后保持原有相对次序。

C++：各章节统一通过 CMake 组织，chapter_sorting/CMakeLists.txt 中已登记该可执行目标，可配合 en/codes 顶层的构建脚本编译运行；C 语言目录 chapter_sorting/CMakeLists.txt 同理。Go 目录下另提供了对应的单测文件 insertion_sort_test.go，可供读者自行运行验证排序结果。

6. 延伸阅读：在《Hello 算法》排序章节中的位置

插入排序是本书排序部分的第一个具体算法，与其配套的周边文档包括：

先了解评价维度与术语：本书 sorting_algorithm.md 系统给出了执行效率、原地性、稳定性、自适应性等评估指标，并指出“目前不存在同时满足快速、原地、稳定、自适应、通用”的理想排序算法，这正是后续逐个考察各排序算法的出发点；
同量级对比：阅读 bubble_sort.md 与 selection_sort.md，可结合本文第 4 节理解三者差异；
分治排序的后续章节：quick_sort.md（理解第 3 节“常数因子”论点的最佳参照）、merge_sort.md（对照其 $O (n)$ 空间开销）；
章节回顾与练习：exercises.md 提供自测题目，summary.md 对该章各排序算法做了横向总结。