for (int i = 0; i < n - 1; i++) { // 从第一个元素开始遍历到倒数第二个元素
int end = i; // 已排序部分的末尾索引
int tmp = arr[end + 1]; // 待插入元素（未排序部分的第一个元素）
while (end >= 0) { // 向前寻找插入位置
if (arr[end] > tmp) { // 若当前元素大于待插入元素，则后移
arr[end + 1] = arr[end];
end--;
} else { // 找到合适位置，退出循环
break;
}
}
arr[end + 1] = tmp; // 插入元素到正确位置
}
}
复制代码
步骤说明：
外层循环：遍历每个待插入元素（从第二个元素开始）。
内层循环：从后向前比较，若当前元素比待插入元素大，则将其后移。
插入操纵：找到第一个比待插入元素小的位置，将元素插入其后。
复杂度分析：
时间复杂度：
最好环境（已有序）：O(n)，只需比较无需移动。
最坏环境（逆序）：O(n²)，每次插入需移动全部已排序元素。
空间复杂度：O(1)，原地排序。
实用场景：
数据量小或基本有序时效率高，稳定且简单。 二、希尔排序（Shell Sort）
算法头脑：
希尔排序是对直接插入排序的一种改进算法，它通过将待排序的数组按照一定的隔断（称为增量）举行分组，对每组分别举行直接插入排序，逐步缩小增量，当 gap > 1 时都是预排序，⽬的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，如许就会很快。如许整体⽽⾔，可以达到优化的结果。
代码解析：
void ShellSort(int* arr, int n) {
int gap = n; // 初始间隔设为数组长度
while (gap > 1) { // 循环直到间隔为1（最后一次完整插入排序）
gap = gap / 3 + 1; // 动态调整间隔（常见增量方式）
for (int i = 0; i < n - gap; i++) { // 对所有间隔分组进行插入排序
