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

一、核心原理

把数组分为已排序区间和未排序区间从头开始，依次把未排序区间的第一个元素，向前插入到已排序区间的合适位置。类比：打牌摸牌，摸到一张往手里有序牌堆里插。

二、算法流程

1. 默认第 0 个元素是已排序区间；
2. 从第 1 个元素开始作为当前待插入元素；
3. 向前遍历已排序元素，比当前值大的向后挪一位；
4. 找到空位，把当前元素插入；
5. 循环直到全部有序。

三、时间复杂度

• 最好情况（数组已有序）：O(n)
• 最坏 / 平均情况（逆序）：O(n²)
• 空间复杂度：O(1)原地排序

四、稳定性

稳定排序相等元素相对位置不会改变。

五、适用场景

1. 数据接近有序时效率极高；
2. 小规模数据排序；
3. 归并 / 快速排序的底层小规模子数组常改用插入排序。

六、基础版插入排序 C++ 代码

cpp

#include <iostream> #include <vector> using namespace std; // 基础插入排序 void insertSort(vector<int>& 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() { vector<int> a = {5,2,4,6,1,3}; insertSort(a); for (auto x : a) cout << x << " "; return 0; }

七、优化：二分插入排序

普通插入是逐个向前比较，可以用二分查找找插入位置，减少比较次数；但移动元素开销不变，时间复杂度仍O(n²)。

cpp

// 二分查找找插入位置 int binarySearch(vector<int>& 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(vector<int>& 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; } }

八、关键知识点总结

1. 原理：将数组分已排序 / 未排序区间，逐个把元素插入已排序区间合适位置。
2. 复杂度：最好 O (n)，平均 / 最坏 O (n²)，空间 O (1)。
3. 稳定性：稳定。
4. 特点：
   • 原地排序、实现简单；
   • 近有序数据极快；
   • 大数据量不适合，平方级复杂度。
5. 优化方向：二分插入减少比较次数，不改变时间复杂度量级。