插入排序（Insertion Sort）是一种简单直观的排序算法，它的核心思想类似于我们整理扑克牌时的操作：将未排序的元素逐个插入到已排序部分的正确位置，从而逐步构建整个有序数组。这种算法适合小规模数据的排序，实现起来也比较容易理解。
基本思路¶
想象你手中有一副打乱的扑克牌，你会一张一张地将牌插入到正确的位置：
1. 从第2张牌开始（默认第1张牌已排序），将当前牌记为「待插入元素」。
2. 将待插入元素与已排序部分的牌从后往前比较：
- 如果已排序的牌比待插入元素大，就把这张已排序的牌后移一位。
- 重复此过程，直到找到一个比待插入元素小的牌，或者已经比较到最左边。
3. 将待插入元素插入到这个位置，此时已排序部分长度增加1。
4. 重复步骤1-3，直到所有牌都插入完毕。
Java代码实现¶
以下是使用Java实现插入排序的完整代码，包含详细注释：
public class InsertionSort {
// 插入排序方法
public static void insertionSort(int[] arr) {
// 数组为空或只有一个元素时，本身已排序，无需操作
if (arr == null || arr.length <= 1) {
return;
}
// 从第2个元素开始（索引1），逐步将元素插入到已排序部分
for (int i = 1; i < arr.length; i++) {
// 保存当前待插入的元素
int current = arr[i];
// j表示已排序部分的最后一个元素的索引，初始为i-1
int j = i - 1;
// 比较已排序部分的元素，若比current大则后移
// 循环终止条件：j >= 0 且 arr[j] > current
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j]; // 将已排序元素后移一位
j--; // 继续向前比较前一个元素
}
// 找到插入位置，将current放入arr[j+1]
arr[j + 1] = current;
}
}
// 测试方法：验证排序是否正确
public static void main(String[] args) {
int[] arr = {5, 2, 4, 6, 1, 3};
System.out.println("排序前：" + java.util.Arrays.toString(arr));
insertionSort(arr);
System.out.println("排序后：" + java.util.Arrays.toString(arr));
}
}
代码执行过程解析¶
以数组 {5, 2, 4, 6, 1, 3} 为例，逐步演示插入排序的过程：
初始数组：[5, 2, 4, 6, 1, 3]¶
第1轮（i=1，current=2）：¶
- 已排序部分：
[5] - 比较：
arr[0]=5 > 2，所以将5后移到arr[1]，j变为-1 - 插入位置：
arr[0] = 2 - 结果：
[2, 5, 4, 6, 1, 3]
第2轮（i=2，current=4）：¶
- 已排序部分：
[2, 5] - 比较：
arr[1]=5 > 4，将5后移到arr[2]，j=0 - 比较：
arr[0]=2 <= 4，停止循环 - 插入位置：
arr[1] = 4 - 结果：
[2, 4, 5, 6, 1, 3]
第3轮（i=3，current=6）：¶
- 已排序部分：
[2, 4, 5] - 比较：
arr[2]=5 <= 6，无需移动 - 插入位置：
arr[3] = 6 - 结果：
[2, 4, 5, 6, 1, 3]（数组未变化）
第4轮（i=4，current=1）：¶
- 已排序部分：
[2, 4, 5, 6] - 比较：
arr[3]=6 > 1→ 后移6到arr[4]，j=2 - 比较：
arr[2]=5 > 1→ 后移5到arr[3]，j=1 - 比较：
arr[1]=4 > 1→ 后移4到arr[2]，j=0 - 比较：
arr[0]=2 > 1→ 后移2到arr[1]，j=-1 - 插入位置：
arr[0] = 1 - 结果：
[1, 2, 4, 5, 6, 3]
第5轮（i=5，current=3）：¶
- 已排序部分：
[1, 2, 4, 5, 6] - 比较：
arr[4]=6 > 3→ 后移6到arr[5]，j=3 - 比较：
arr[3]=5 > 3→ 后移5到arr[4]，j=2 - 比较：
arr[2]=4 > 3→ 后移4到arr[3]，j=1 - 比较：
arr[1]=2 <= 3，停止循环 - 插入位置：
arr[2] = 3 - 最终结果：
[1, 2, 3, 4, 5, 6]
算法特性总结¶
-
时间复杂度：
- 最好情况（数组已排序）：O(n)（仅需n-1次比较）
- 最坏情况（数组逆序）：O(n²)（n-1次内层循环，每次比较n次）
- 平均情况：O(n²) -
空间复杂度：O(1)（原地排序，仅需一个临时变量保存待插入元素）
-
稳定性：稳定排序（相等元素的相对顺序不会改变）
-
适用场景：适合小规模数据或几乎有序的数据，因为小规模数据的O(n²)影响较小。
总结¶
插入排序的核心是“逐步插入”，通过将元素与已排序部分比较并移动，最终构建有序数组。Java实现时需要注意保存待插入元素（避免覆盖），以及正确处理边界条件（j的终止条件）。这种算法虽然时间复杂度较高，但实现简单，稳定性和原地性使其在小规模数据排序中表现良好。