从头实现插入排序

插入排序（insertion sort）模拟了人们整理扑克牌的方式: 将数组分为已排序和未排序两部分；从未排序部分取出一个元素，插入到已排序部分的适当位置；初始时已排序部分只有第一个元素。

思路：将数组视为由两个部分组成，已排序部分和未排序部分。从第 2 个元素开始遍历数组元素，逐步将每个待排序的元素插入到已排序部分的合适位置。在每一轮操作中，算法将未排序部分的第一个元素插入到已排序部分中的合适位置。在插入元素时，已排序部分始终保持有序。待到数组未排序部分的元素遍历完毕，数组完全排序。

框架：

#include <algorithm>
#include <iostream>
#include <vector>

void InsertionSort(std::vector<int> &A) {

}

int main() {
    std::vector<int> A{9, 1, 5, 8, 3, 7, 4, 6, 2};
    InsertionSort(A);
    std::ranges::for_each(A, [](int value) { std::cout << value << ' '; });
    return 0;
}

从第2个元素开始遍历数组的每个元素。将数组中的元素看作两部分，“已排序”的和“未排序”的。在初始状态下，将数组的第1个元素视为“已排序”的部分，因为只有1个元素，所以可以认为是有序的。

void InsertionSort(std::vector<int> &A) {
    for (int i = 1; i < A.size(); ++i) {

    }
}

为了将“当前遍历元素”并入“已排序”部分，可能会向右移动一些已排序部分的元素，为了避免当前元素被从左侧移动而来的元素覆盖掉，新建一个变量key把当前元素保存下来。

void InsertionSort(std::vector<int> &A) {
    for (int i = 1; i < A.size(); ++i) {
        int key = A[i];

    }
}

从“当前待插入元素”左侧的位置开始向左遍历“已排序部分”的元素，直到找到合适的插入位置或遍历完已排序部分。用变量j记录内层循环当前元素索引。对“已排序部分”的元素的遍历，当元素小于等于“当前待插入元素”时停下，且首先需要保证索引不会越界（超出数组左侧边界）。

void InsertionSort(std::vector<int> &A) {
    for (int i = 1; i < A.size(); ++i) {
        int key = A[i];

        int j = i - 1;
        while (j >= 0 && key < A[j]) {

        }
    }
}

如果代码能够运行到内层循环的循环体内，说明待插入元素比当前元素更小，则当前“已排序部分”的元素向右移动一位，它原来所在的位置便空了出来，给待插入元素腾出位置。注意更新变量j使其持续反映当前索引。

void InsertionSort(std::vector<int> &A) {
    for (int i = 1; i < A.size(); ++i) {
        int key = A[i];

        int j = i - 1;
        while (j >= 0 && key < A[j]) {
            A[j + 1] = A[j];
            --j;
        }
        
    }
}

在内层循环（对“已排序部分”的元素的遍历）结束后，变量j所指位置右侧一位就是“当前待插入元素”的插入位置。

void InsertionSort(std::vector<int> &A) {
    for (int i = 1; i < A.size(); ++i) {
        int key = A[i];

        int j = i - 1;
        while (j >= 0 && key < A[j]) {
            A[j + 1] = A[j];
            --j;
        }
        A[j + 1] = key;
    }
}

完整代码：

#include <algorithm>
#include <iostream>
#include <vector>

void InsertionSort(std::vector<int> &A) {
    for (int i = 1; i < A.size(); ++i) {
        int key = A[i];

        int j = i - 1;
        while (j >= 0 && key < A[j]) {
            A[j + 1] = A[j];
            --j;
        }
        A[j + 1] = key;
    }
}

int main() {
    std::vector<int> A{9, 1, 5, 8, 3, 7, 4, 6, 2};
    InsertionSort(A);
    std::ranges::for_each(A, [](int value) { std::cout << value << ' '; });
    return 0;
}