插入排序

插入排序的核心思想是将数组分为已排序和未排序两部分，依次取出未排序部分的元素，向前遍历已排序部分找到合适位置插入，不断扩大有序区间直至整个数组有序，适合小规模数据，时间复杂度最坏为 O (n²)。

August 18, 1946基础算法,排序1分钟阅读

插入排序（Insertion Sort） 是一种简单直观且稳定的基于比较的排序算法。它的工作原理非常类似于我们在打扑克牌时整理手中的牌：每次拿到一张新牌，都会将其插入到手牌中合适的位置，从而保持手中的牌始终是有序的。

分界概念：将数组分为两部分——已排序区间（初始时只有第一个元素）和未排序区间。
逐步插入：依次从“未排序区间”取出第一个元素，在“已排序区间”中从后往前（或从前往后）进行比较。
元素移位：如果已排序的元素大于待插入元素，就把该已排序元素向后移动一位。
确定位置：重复移位，直到找到一个小于或等于待插入元素的位置，将该元素放入。
循环迭代：重复上述步骤，直到“未排序区间”为空。

手绘风格插入排序完整流程图解 — 插入排序完整执行流程：逐次把未排序区间元素取出，通过比较与交换，插入到左侧已排序区间的正确位置，经过多轮迭代后整个数组变为有序。

#include <iostream>
#include <vector>

void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i]; // 当前需要插入的元素
        int j = i - 1;

        // 将大于 key 的元素向后移动一位
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 将 key 放到正确的位置
        arr[j + 1] = key;
    }
}

int main() {
    std::vector<int> data = {5, 2, 4, 6, 1};
    insertionSort(data);

    for (int num : data) {
        std::cout << num << " ";
    }
    return 0;
}

特性	指标 / 说明
最好时间复杂度	$O(n)$ （数组本身就是完全有序时，每轮只需比较一次）
最坏时间复杂度	$O(n^2)$ （数组完全逆序时，需要比较和移动 $\frac{n(n-1)}{2}$ 次）
平均时间复杂度	$O(n^2)$
空间复杂度	$O(1)$ （原地排序算法，不需要额外开辟数组空间）
稳定性	稳定（对于相同数值的元素，不会改变它们原有的相对顺序）

核心思想

参考代码

复杂度与算法特性分析