C++直接插入排序逐行解释

C++中的直接插入排序是一种简单直观的排序算法，它的工作原理是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。其过程是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

下面是一个简单的C++直接插入排序的逐行解释代码示例：

#include <iostream>
#include <vector>

using namespace std;

void insertionSort(vector<int>& arr) {
    int i, j, key;
    for (i = 1; i < arr.size(); i++) { // 从数组的第二个元素开始
        key = arr[i]; // 取出一个元素
        j = i - 1;
        // 将这个元素与它前面的元素进行比较，并将所有比它大的元素向后移动一位
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 将比key大的元素向后移动
            j = j - 1;
        }
        arr[j + 1] = key; // 将key插入到正确的位置
    }
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6};
    insertionSort(arr);

    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

逐行解释如下：
1. `#include <iostream>` 和 `#include <vector>` 是预处理指令，分别用于输入输出和动态数组。
2. `using namespace std;` 允许我们在不使用std::命名空间的情况下直接使用标准库中的名字。
3. 定义了一个名为`insertionSort`的函数，它接受一个整型的`vector`引用作为参数。
4. `for`循环从数组的第二个元素开始迭代，因为第一个元素默认是已排序的。
5. `key`变量保存当前正在处理的元素值。
6. 变量`j`初始化为当前元素的前一个元素的位置。
7. `while`循环用于将所有比`key`大的元素向后移动一个位置，为`key`腾出空间。
8. `arr[j + 1] = arr[j];`将`key`之前的元素向后移动。
9. `j = j - 1;`减少`j`的值，继续检查下一个元素。
10. 当找到`key`应插入的位置时，将其插入到`arr[j + 1]`。
11. `main`函数定义了一个包含整数的`vector`并调用`insertionSort`函数进行排序。
12. 使用`for`循环遍历并打印排序后的数组。