【基础4】插入排序
核心思想
插入排序是一种基于元素比较的原地排序算法，其核心思想是将数组分为“已排序”和“未排序”两部分，逐个将未排序元素插入到已排序部分的正确位置。
例如扑克牌在理牌的时候，一般会将大小王、2、A、花牌等按大小顺序插入到左边，3、4等小牌会往右边靠，这和插入排序是同一个原理
复杂度
时间复杂度
| 场景 | 时间复杂度 | 具体说明 |
|---|---|---|
| 最佳情况 | O(n) | 数组已完全有序，每次只需比较一次（无需移动元素） |
| 最差情况 | O(n²) | 数组完全逆序，每个元素需比较并移动所有已排序元素（如 [5,4,3,2,1]） |
| 平均情况 | O(n²) | 部分有序数组的插入操作需要约 n²/4 次比较和移动 |
空间复杂度
O(1)：原地排序算法，仅需固定数量的额外空间（如 key 和索引变量 j）
代码实现（Java）
//插入排序，升序排序举例
void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;//不断向左移动，直到找到自己的位置while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}
}