一 算法原理
插入排序是稳定的原地排序算法，核心思想是逐步构建有序序列。对于未排序部分的每个元素，在已排序序列中从后向前扫描，找到合适位置插入。时间复杂度为：
1）最优：O(n)（已有序）
2）最差：O(n^2)（完全逆序）
3）平均：O(n^2)
二 排序过程
以数组 [6 5 7 8 2] 为例的逐步过程。
1. 初始状态
[6 | 5 7 8 2] // 已排序区:6，未排序区:5 7 8 2
2. 插入5
5 < 6 → 交换
[5 6 | 7 8 2] // 已排序区:5 6
3. 插入7
7 > 6 → 不移动
[5 6 7 | 8 2] // 已排序区:5 6 7
4. 插入8
8 > 7 → 不移动
[5 6 7 8 | 2] // 已排序区:5 6 7 8
5. 插入2
2 < 8 → 后移8
2 < 7 → 后移7
2 < 6 → 后移6
2 < 5 → 后移5
插入到首位
[2 5 6 7 8] // 排序完成
三 C++ 代码实现
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) { // 从第二个元素开始遍历
int temp = arr[i]; // 保存当前待插入元素
int j = i - 1; // 已排序区的末尾索引
// 从后向前扫描，寻找插入位置
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j]; // 元素后移
j--;
}
if(j!=(i-1))//j 已经变化，说明需要插入
arr[j + 1] = temp; // 插入到正确位置
}
}
int main() {
int arr[] = {6, 5, 7, 8, 2};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
cout << "排序结果: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
四 关键代码解析
1. 外层循环 (i 从1到n-1)
逐个处理未排序区的元素。
2. 内层循环(while (j >= 0 && arr[j] > temp))
通过后移操作腾出插入位置
3. 时间复杂度分析
- 最优情况（已有序）：仅需比较n-1次 O(n)
- 最差情况（完全逆序）：总比较次数n(n-1)/2 O(n^2)
五 总结
插入排序适合：
1）小规模数据（n <1000）；
2）数据基本有序的场景；
3）需要稳定排序的场景。
通过逐步调整元素位置，以线性时间复杂度完成局部排序，最终达成全局有序。
