一、算法概述
插入排序是一种简单直观的排序算法，其核心思想是 将待排序元素逐个插入到已排序序列的适当位置，从而构建完整的有序序列 。该算法类似于玩扑克牌时整理手牌的过程。
插入排序的核心逻辑，就和我们整理手中的扑克牌如出一辙。
开局摸牌时，左手先攥住第一张牌，它天然有序。后续每摸一张新牌，就从右往左和左手里的牌逐一比对，把它插入到比它小的牌右边、比它大的牌左边的位置。重复这个动作，直到所有牌都被插入左手，最终就能得到一副有序的牌。
对应到算法中，数组的第一个元素就是 “初始手牌”，从第二个元素开始，逐个将元素插入前面已排序的区间，最终实现整体有序。
二、核心实现步骤
1. 区间划分
- 将数组分为两个逻辑区间：
- 已排序区间 ：初始为 [0, 0] （单个元素默认有序）
- 未排序区间 ：初始为 [1, n-1] （n为数组长度）
- 变量 i 作为 未排序区间的起始索引
2. 外层循环：遍历未排序元素
for (int i = 1; i < arr.length; i++) { // 插入排序逻辑}- 从下标1开始遍历，共执行 n-1 次
- 每次处理一个未排序元素，将其插入到已排序区间的合适位置
3. 保存待插入元素
int tmp = arr[i];- 将要插入的元素值保存到临时变量 tmp
- 避免在后续移动元素时被覆盖
4. 内层循环：寻找插入位置
int j = i;while (j > 0 && tmp < arr[j - 1]) { arr[j] = arr[j - 1]; j--;}- 从当前位置 i 开始向左比较
- 条件 j > 0 确保不越界
- 条件 tmp < arr[j - 1] 寻找比 tmp 小的元素
- 元素后移 ：将比 tmp 大的元素向右移动一位，为插入腾出空间
5. 执行插入操作
if (j != i) { arr[j] = tmp;}- 只有当位置发生变化（ j != i ）时才执行插入
- 将 tmp 插入到找到的合适位置 j
- 插入后，已排序区间长度加1
三、排序过程示例
以数组 {11, 3, 5, 2, 13} 为例，排序过程如下：
初始状态
- 已排序区间： [11]
- 未排序区间： [3, 5, 2, 13]
第1轮（i=1，tmp=3）
- j=1 ，比较 3 < 11 ，成立
- 元素后移： arr[1] = arr[0] → 数组变为 [11, 11, 5, 2, 13]
- j-- → j=0 ，循环结束
- 插入 tmp ： arr[0] = 3 → 数组变为 [3, 11, 5, 2, 13]
- 已排序区间： [3, 11]
第2轮（i=2，tmp=5）
- j=2 ，比较 5 < 11 ，成立
- 元素后移： arr[2] = arr[1] → 数组变为 [3, 11, 11, 2, 13]
- j-- → j=1 ，比较 5 < 3 ，不成立，循环结束
- 插入 tmp ： arr[1] = 5 → 数组变为 [3, 5, 11, 2, 13]
- 已排序区间： [3, 5, 11]
第3轮（i=3，tmp=2）
- j=3 ，比较 2 < 11 ，成立
- 元素后移： arr[3] = arr[2] → 数组变为 [3, 5, 11, 11, 13]
- j-- → j=2 ，比较 2 < 5 ，成立
- 元素后移： arr[2] = arr[1] → 数组变为 [3, 5, 5, 11, 13]
- j-- → j=1 ，比较 2 < 3 ，成立
- 元素后移： arr[1] = arr[0] → 数组变为 [3, 3, 5, 11, 13]
- j-- → j=0 ，循环结束
- 插入 tmp ： arr[0] = 2 → 数组变为 [2, 3, 5, 11, 13]
- 已排序区间： [2, 3, 5, 11]
第4轮（i=4，tmp=13）
- j=4 ，比较 13 < 11 ，不成立，循环结束
- j == i ，无需插入
- 数组保持 [2, 3, 5, 11, 13]
- 已排序区间： [2, 3, 5, 11, 13]
四、算法特点
时间复杂度
- 最佳情况 ：O(n)（数组已完全有序，内层循环无需执行）
- 最坏情况 ：O(n²)（数组完全逆序，每个元素都需移动到最前面）
- 平均情况 ：O(n²)
空间复杂度
- O(1) ：原地排序，仅使用常数级额外空间
稳定性
- 稳定排序 ：相同元素的相对位置不会改变
插入排序的优势
- 对于 近乎有序的数组 ，效率很高（接近O(n)）
- 对于 小规模数据 ，性能表现良好
- 空间复杂度低 ，适合内存受限场景
- 实现简单 ，代码易于理解和维护
五、代码优化点
1. 避免不必要的赋值
if (j != i) { arr[j] = tmp;}- 当元素已经在正确位置时，避免重复赋值
- 减少了无效的写操作，提高效率
2. 边界条件处理
- 外层循环从 i=1 开始，避免了对单个元素的无效处理
- while循环条件 j > 0 确保数组不越界
3. 清晰的变量命名
- tmp ：明确表示要插入的临时元素
- i 和 j ：分别表示未排序区间起始和插入位置
- 代码可读性强，易于理解
六、与选择排序的对比
特性 插入排序 选择排序 时间复杂度（最佳） O(n) O(n²) 时间复杂度（最坏） O(n²) O(n²) 空间复杂度 O(1) O(1) 稳定性 稳定 不稳定 适用场景 近乎有序数据、小规模数据 小规模数据 核心思想 逐个插入构建有序序列 选择最小元素交换到已排序末尾
七、总结
插入排序是一种高效的基础排序算法，尤其适合处理近乎有序或小规模的数据。其核心思想是通过将元素逐个插入到已排序序列的适当位置，逐步构建完整的有序序列。该算法实现简单，空间复杂度低，是学习排序算法的重要基础。
通过分析给定代码，可以清晰地理解插入排序的工作原理：从第二个元素开始，每次将当前元素插入到左侧已排序序列的合适位置，直到所有元素排序完成。这种"增量构建"的思路
