【3】插入排序算法

可以把插入排序看成整理扑克牌的过程。假设你手里有一堆乱七八糟的扑克牌，你的任务是把它们按从小到大的顺序排好。插入排序就是一张一张地把牌放到正确的位置。

具体来说，插入排序的过程如下：

1. 从未排序的牌中选择一张，把它插入已排序的牌中。

2. 从已排序的牌中从后往前依次比较，找到第一张比这张牌小的牌的位置。

3. 把这张牌插入到那个位置后面，即完成了一次插入操作。

4. 重复步骤1到3，直到所有的牌都被插入到正确的位置上。

我们要对数组{5, 2, 4, 6, 1, 3}进行排序。

首先，将第二个元素2与第一个元素5进行比较，2小于5，因此将2插入到第一个元素之前，得到{2, 5, 4, 6, 1, 3}。

接着，将第三个元素4与已排序的元素进行比较，4大于2，因此将4插入到第二个元素之后，得到{2, 4, 5, 6, 1, 3}。

然后，将第四个元素6与已排序的元素进行比较，6大于4、5，因此将其插入到已排序的数列中，得到{2, 4, 5, 6, 1, 3}。

接着，将第五个元素1与已排序的元素进行比较，1小于2、4、5、6，因此将1插入到第一个元素之前，得到{1, 2, 4, 5, 6, 3}。接着，将第六个元素3与已排序的元素进行比较，3小于4，因此将3插入到第二个元素之前，得到{1, 2, 3, 4, 5, 6}。

最终排序结果为{1, 2, 3, 4, 5, 6}。

以下是用C++代码演示插入排序过程的例子：

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
        // 输出每一轮排序后的数组
        for (int k = 0; k < n; k++) {
            cout << arr[k] << " ";
        }
        cout << endl;
    }
}

int main() {
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Original array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << "Insertion sort:" << endl;
    insertionSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

这段代码定义了一个 insertionSort 函数，用于对传入的数组进行插入排序，并在每一轮排序结束后输出排序后的数组。在主函数中，我们首先输出原始数组，然后调用 insertionSort 函数对数组进行排序，并输出最终结果。

运行代码，输出如下：

Original array: 5 2 4 6 1 3 
Insertion sort:
2 5 4 6 1 3 
2 4 5 6 1 3 
2 4 5 6 1 3 
1 2 4 5 6 3 
1 2 3 4 5 6 
Sorted array: 1 2 3 4 5 6