插入排序认为待排序数组可视作"已排好序的前缀 + 未排序的后缀"。每次从后缀中取出一个元素的 key，把它插入到前缀中适当位置。

Ph1zの理解： 打扑克牌时，你每摸一张牌，就从右往左找到它该插的位置，插进去——这就是插入排序。手牌始终有序，每张新牌只是"插入"到正确位置。

代码

Algorithm InsertionSort(A, n):
    Input: An array A of n elements
    Output: Array A sorted in ascending order

    // 从第二个元素开始遍历（下标从 1 到 n-1）
    for i = 1 to n - 1 do
        key = A[i]                  // 记录当前要插入的元素
        j = i - 1                   // 从当前元素的前一个位置开始向前比较

        // 向前寻找插入位置，并将大于 key 的元素向后移动
        while j >= 0 and A[j] > key do
            A[j + 1] = A[j]         // 元素后移
            j = j - 1               // 继续向前比较
        end while

        // 将 key 插入到正确的位置
        A[j + 1] = key
    end for

    return A

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = a[i];          // 当前待插入元素
        int j = i - 1;           // 从已排序区末尾向前扫描
        
        // 寻找插入位置，并将大于 key 的元素后移
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;          // 插入到正确位置
    }
}

优化代码

void binaryInsertionSort(int a[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = a[i];          // 当前待插入元素
        int left = 0;            // 二分查找左边界
        int right = i - 1;       // 二分查找右边界

        // 1. 二分查找插入位置（left 最终为插入点）
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出
            if (a[mid] > key) {
                right = mid - 1; // 插入点在左侧
            } else {
                left = mid + 1;  // 插入点在右侧（保持稳定）
            }
        }

        // 2. 将 [left, i-1] 的元素整体后移一位
        for (int j = i - 1; j >= left; --j) {
            a[j + 1] = a[j];
        }

        // 3. 将 key 放入正确位置
        a[left] = key;
    }
}

正确性证明：循环不变式

循环不变式： 在外层循环每轮开始时，a[0..i-1] 已经有序，并且恰好包含原数组中前 i 个元素的所有值。

• 初始化： i = 1 时，a[0] 显然有序；不变式成立。
• 保持： 设当前 key = a[i]，内层循环把所有大于 key 的元素右移，直到找到正确插入位置 j + 1，此时前缀 a[0..i] 仍然有序。
• 终止： 当 i = n 时，整个数组有序。

Ph1zの理解： 循环不变式就像"归纳假设"——你要证明三件事：开始时对、每步保持对、结束时恰好是你想要的。数学归纳捏

因此插入排序是正确的。 ✓

复杂度分析

情况	时间复杂度	直觉
最好	$O(n)$	数组本来有序，key 每次直接放回原位，内层循环几乎不执行
最坏	$O(n^2)$	逆序，每个 key 要一直移到最前面，内层循环执行 $i$ 次
平均	$O(n^2)$	随机数据，key 平均要移动 $i/2$ 次

空间复杂度： $O(1)$。

稳定性： 稳定。因为只有 a[j] > key 时才右移，等于 key 的元素不移动，故相同关键字顺序保持。

插入排序的实战价值： 虽然理论上是 $O(n^2)$，但对近乎有序的数组极快（接近 $O(n)$），而且常数因子极小。所以很多高级排序（如 TimSort）在小段或近乎有序段会退回插入排序——不是"落后"，而是"精明"。