插入排序：原理与优化全解析

一、核心原理把数组分为已排序区间和未排序区间从头开始依次把未排序区间的第一个元素向前插入到已排序区间的合适位置。类比打牌摸牌摸到一张往手里有序牌堆里插。二、算法流程默认第 0 个元素是已排序区间从第 1 个元素开始作为当前待插入元素向前遍历已排序元素比当前值大的向后挪一位找到空位把当前元素插入循环直到全部有序。三、时间复杂度最好情况数组已有序O(n)最坏 / 平均情况逆序O(n²)空间复杂度O(1)原地排序四、稳定性稳定排序相等元素相对位置不会改变。五、适用场景数据接近有序时效率极高小规模数据排序归并 / 快速排序的底层小规模子数组常改用插入排序。六、基础版插入排序 C 代码cpp#include iostream #include vector using namespace std; // 基础插入排序 void insertSort(vectorint arr) { int n arr.size(); for (int i 1; i n; i) { int cur arr[i]; // 当前待插入元素 int j i - 1; // 向前挪元素 while (j 0 arr[j] cur) { arr[j 1] arr[j]; j--; } // 插入到正确位置 arr[j 1] cur; } } int main() { vectorint a {5,2,4,6,1,3}; insertSort(a); for (auto x : a) cout x ; return 0; }七、优化二分插入排序普通插入是逐个向前比较可以用二分查找找插入位置减少比较次数但移动元素开销不变时间复杂度仍O(n²)。cpp// 二分查找找插入位置 int binarySearch(vectorint arr, int left, int right, int val) { while (left right) { int mid (left right) / 2; if (arr[mid] val) right mid - 1; else left mid 1; } return left; } // 二分插入排序 void binaryInsertSort(vectorint arr) { int n arr.size(); for (int i 1; i n; i) { int cur arr[i]; int pos binarySearch(arr, 0, i - 1, cur); // 元素后移 for (int j i; j pos; --j) { arr[j] arr[j - 1]; } arr[pos] cur; } }八、关键知识点总结原理将数组分已排序 / 未排序区间逐个把元素插入已排序区间合适位置。复杂度最好 O (n)平均 / 最坏 O (n²)空间 O (1)。稳定性稳定。特点原地排序、实现简单近有序数据极快大数据量不适合平方级复杂度。优化方向二分插入减少比较次数不改变时间复杂度量级。