原理

在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。（与手动整理一副牌的过程非常相似）

设数组的长度为 𝑛 ：

1. 初始状态下，数组的第 1 个元素已完成排序。
2. 选取数组的第 2 个元素作为 base ，将其插入到正确位置后， 数组的前 2 个元素已排序。
3. 选取第 3 个元素作为 base ，将其插入到正确位置后， 数组的前 3 个元素已排序。
4. 以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后， 所有元素均已排序。

示例

“4 1 3 1 5 2”：

初始状态：有序部分：[4] 无序部分：[1, 3, 1, 5, 2]

第一轮：

1. 从无序部分取出第一个元素“1”。
2. 将“1”与有序部分的“4”比较，因为 1<4，所以将“4”向后移动一位，把“1”插入到有序部分的最前面。 有序部分：[1, 4] 无序部分：[3, 1, 5, 2]
3. 即 “1 4 3 1 5 2”

第二轮：

1. 从无序部分取出第一个元素“3”。
2. 将“3”与有序部分的“1”和“4”比较，1<3<4，所以将“4”向后移动一位，把“3”插入到“1”和“4”之间。 有序部分：[1, 3, 4] 无序部分：[1, 5, 2]
3. 即 “1 3 4 1 5 2”

第三轮：

1. 从无序部分取出第一个元素“1”。
2. 将“1”与有序部分的“1”、“3”和“4”比较，发现已经有“1”了，不需要移动其他元素，直接把这个“1”插入到已有的“1”后面。 有序部分：[1, 1, 3, 4] 无序部分：[5, 2]
3. 即 “1 1 3 4 5 2”

第四轮：

1. 从无序部分取出第一个元素“5”。
2. 将“5”与有序部分的“1”、“1”、“3”和“4”比较，4<5，所以将“5”插入到“4”后面。 有序部分：[1, 1, 3, 4, 5] 无序部分：[2]
3. 即 “1 1 3 4 5 2”

第五轮：

1. 从无序部分取出唯一的元素“2”。
2. 将“2”与有序部分的“1”、“1”、“3”、“4”和“5”比较，1<2<3，所以将“3”向后移动一位，把“2”插入到“1”和“3”之间。 有序部分：[1, 1, 2, 3, 4, 5] 无序部分：[]，
3. 即 “1 1 2 3 4 5”

排序完成。

代码（C）

/* 插入排序 */
void insertionSort(int nums[], int size) {
    // 外循环：已排序元素数量为 1, 2,..., n
    for (int i = 1; i < size; i++) {
        // i 从 1 开始，因为第0元素本身就是已排序的。
        // 每一轮循环，将第 i 个元素插入到已排序部分的正确位置。

        int base = nums[i], j = i - 1;
        // base 保存当前要插入到已排序部分的元素值。
        // j 初始化为已排序部分的最后一个元素的索引。

        // 内循环：将 base 插入到已排序部分的正确位置
        while (j >= 0 && nums[j] > base) {
            // 当 j 大于等于 0 且已排序部分的当前元素大于 base 时，执行以下操作。
            // 将 nums[j] 向右移动一位
            nums[j + 1] = nums[j];
            j--;
            // j 递减，继续向前比较。
        }

        // 将 base 赋值到正确位置
        nums[j + 1] = base;
        // 此时 j + 1 就是 base 应该插入的位置。
    }
}

复杂度

时间复杂度：最差情况为

空间复杂度：为