题目传送门
思路：
首先，我们假设数组的第一个元素是已经排好序的（虽然它只有一个元素，但确实是有序的）。
然后，我们从数组的第二个元素开始，逐一考虑每一个元素。
对于每一个元素，我们称它为“ base ”。我们将其与前面的已排序的元素逐一比较。
如果“base”比前面的某个元素小，我们就将那个元素向后移动一位，为“ base ”腾出位置。
我们继续这样的比较和移动，直到找到“ base ”应该插入的位置，或者已经比较完了所有的已排序元素。
最后，将“ base ”插入到找到的位置。重复这个过程，直到考虑完数组中的所有元素。
那么代码就如下所示（附超详细代码注释）：
CODE
#include <bits/stdc++.h>
using namespace std;
/* 插入排序 */
void insertionSort(vector<int> &nums) {
// 外循环：从第二个元素开始，遍历整个数组
// 已排序区间为 [0, i-1]，初始时只有一个元素（即 nums[0]）
for (......) {
// 将当前元素 nums[i] 赋值给 base，表示我们要将这个元素插入到已排序区间中
int base = nums[i], j = ...;
// 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
// j 是已排序区间的最后一个元素的索引
while (......) {
// 如果 j 还在已排序区间内，并且 nums[j] 比 base 大
// 将 nums[j] 向右移动一位，为 base 腾出位置
nums[...] = nums[...];
j--; // 继续向前比较
}
// 当找到合适的位置时（即 nums[j] 不大于 base，或者 j 已经小于 0），将 base 插入
nums[j + 1] = base;
}
}
int main() {
int n;
cin >> n; // 输入数组的长度
vector<int>v(n);
// 创建一个长度为 n 的数组
// 读取数组中的每个元素
for (......) {
cin >> ...;
}
// 对数组进行插入排序
insertionSort(v);
// 输出排序后的数组
for (......) {
cout << ... << " ";
}
return 0;
}
希望给你带来帮助，如果你 AC 了，请留下一个赞吧；如果没有 AC ，欢迎提问。