第 25 课：插入排序

过年了，蛙蛙和家里人一起打扑克牌，他发现自己总是将扑克牌有序地拿在手上，当抓到一张新牌的时候，也会将此牌有序放置。类似于蛙蛙这种排序方式，称为插入排序。

25.1 插入排序的概念及步骤

概念

插入排序（insertion sort）是一种简单、直观且稳定的排序算法。

如果有一个已经有序的数据序列，要求在这个数据序列中插入一个数，插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序。

插入排序的基本操作就是将一个数据插入已经排好序的有序数列中，从而得到一个新的、个数加 1 的有序数列，该算法适用于少量数据的排序。

步骤

1. 从第一个元素开始，该元素被认为已排序。

2. 取出下一个元素，在已排序的序列中从后往前扫描。

3. 如果已排序的序列中该元素大于新元素，将该元素移到下一个位置。

4. 重复步骤 3)，直到找到已排序的元素小于或者等于新元素的位置。

5. 将新元素插入后，重复步骤 2) ~ 5)。

25.2 演示及实现

接下来我们以对序列 [5, 6, 3, 1, 8, 7] 从小到大排序为例来讲解插入排序的具体过程。

第一步：有序序列为 [5]，从第二个数 6 开始进行插入排序。因为 5 是小于 6 的，所以位置不用改动，在第二个位置插入数字 6，得到有序序列 [5, 6]。

第二步：有序序列为 [5, 6]，从第三个数 3 开始进行插入排序。由于 5、6 均大于 3，因此数字 5、6 各需要往后挪一个位置，然后再将 3 放到第一个位置，得到有序序列 [3, 5, 6]。

第三步：有序序列为 [3, 5, 6]，从第四个数 1 开始进行插入排序。由于 3、5、6 均大于 1，因此数字 3、5、6 需要往后挪一个位置，然后再将 1 放到第一个位置，得到有序序列 [1, 3, 5, 6]。

第四步：有序序列为 [1, 3, 5, 6]，从第五个数 8 开始进行插入排序。由于 1、3、5、6 都是小于 8 的，所以位置不用改动，在最后一个位置插入数字 8，得到有序序列 [1, 3, 5, 6, 8]。

第五步：有序序列为 [1, 3, 5, 6, 8]，从第六个数 7 开始进行插入排序。因为 1、3、5、6 都是小于 7 的，所以位置不用改动。由于 8 大于 7，因此把它往后挪一个位置，然后在 6 和 8 之间插入数字 7，得到有序序列 [1, 3, 5, 6, 7, 8]。

至此，整个插入排序过程完成。

代码实现

#include <iostream>
using namespace std;
int arr[10005];
int main()
{
    // key 用于暂存当前要插入的元素，j 用于遍历已排序部分
    int n, key, j;
    cin >> n;
    // 读取 n 个元素，并将它们存储到数组 arr 中
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    // 从第二个元素（下标为 1）开始进行插入排序，第一个元素（下标为 0）可看作已排序
    for (int i = 1; i < n; i++)
    {
        // 暂存当前要插入的元素
        key = arr[i];
        // j 初始化为 i - 1，指向已排序部分的最后一个元素
        j = i - 1;
        // 当 j 大于或等于 0 且当前要插入的元素小于已排序部分的元素时
        while (j >= 0 && key < arr[j])
        {
            // 将已排序部分中大于 key 的元素向后移动一位
            arr[j + 1] = arr[j];
            // j 减 1，继续向前比较
            j--;
        }
        // 找到合适的位置后，将 key 插入该位置
        arr[j + 1] = key;
    }
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

25.3 实例讲解

例 1：批改试卷

在一次考试过后，老师将批改完的试卷按分数从低到高的顺序整理好了，但是整理完之后老师发现有 m 份试卷掉在地上没有批改，于是就拿起来重新批改并打上分数。

请你帮老师将重新批改好的试卷插入已经整理好的试卷之中，而不改变试卷分数的高低顺序。

【输入格式】输入三行。第 1 行为正整数 n 和 m，分别表示试卷的份数（除去漏改的 m 份）以及漏改试卷的份数（0 < n ≤ 40000，0 ≤ m ≤ 500）。

第 2 行为 n 个整数，分别表示 n 份试卷按分数由低到高的顺序排列的分数（0 ~ 100000）。

第 3 行为 m 个整数，分别表示 m 份遗忘试卷的分数（0 ~ 100000）。

【输出格式】输出一行，n + m 个有序（由低到高）整数，为整理完成的试卷的分数。

【输入样例】

10 2
45 55 60 65 70 75 80 85 90 95
80 97

【输出样例】

45 55 60 65 70 75 80 80 85 90 95 97

注：原书输入样例只保留了第 1 行“10 2”，第 2、3 行缺失，此处根据题目解析中的数组和输出样例补全。

解析

已批改试卷分数是数组 a 的前 n 个元素，为 [45, 55, 60, 65, 70, 75, 80, 85, 90, 95]；漏改试卷分数是数组 a 的第 n + 1 到第 n + m 个元素，为 [80, 97]。

1. 处理第一个漏改试卷分数 80。从 a 的开头遍历，当 i = 6（i 从 0 开始）时，a[6] = 80，80 不小于 80，所以继续向后遍历；当 i = 7 时，a[7] = 85，80 小于 85，所以插入位置为 i = 7。将 a 中第 7 个及后面的元素向后移动一位，然后将 80 放入第 7 的位置，此时 a 的前 n + 1 个元素变为 [45, 55, 60, 65, 70, 75, 80, 80, 85, 90, 95]。

2. 处理第二个漏改试卷分数 97。从 a 的开头遍历，当 i = 10 时，a[10] = 95，97 大于 95，继续向后遍历，发现已经遍历到数组末尾，所以插入位置为 i = 11。将 a 中第 11 个及后面的元素（没有）向后移动一位（不操作），然后将 97 放入第 11 的位置，此时 a 数组变为 [45, 55, 60, 65, 70, 75, 80, 80, 85, 90, 95, 97]。

最后输出 a 数组中的所有元素，即 45 55 60 65 70 75 80 80 85 90 95 97。

参考代码

#include <iostream>
using namespace std;
int a[41005];
int main()
{
    int n, key, j, m;
    cin >> n >> m;
    for (int i = 1; i <= m + n; i++)
        cin >> a[i];
    for (int i = n + 1; i <= m + n; i++)
    {
        key = a[i];
        j = i - 1;
        while (j >= 1 && key < a[j])
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
    for (int k = 1; k <= m + n; k++)
        cout << a[k] << " ";
    return 0;
}

注：原书代码中的输出语句写作 ' '（两空格的多字符字面量），此处统一改为 " "，与样例输出保持一致。