1. 概述
在这篇文章中，我们将深入探讨 插入排序算法（Insertion Sort）及其 Java 实现方式。
插入排序是一种适用于少量数据排序的高效算法。它的设计灵感来源于现实生活中玩纸牌时的排序方式：
- 假设我们左手为空，桌面上放着一堆乱序的牌。
- 每次从桌面拿起一张牌，插入到左手已经排好序的部分中合适的位置。
- 插入时从右往左比较，找到正确位置后插入。
下面我们将通过伪代码和实际代码来理解其工作原理。
2. 算法伪代码
我们用一个名为 INSERTION-SORT 的过程来表示插入排序算法，输入是一个包含 n 个元素的数组 A[1..n]。该算法是原地排序（in-place），即直接在原数组上进行排序操作。
排序完成后，数组 A 中的元素会变成原始序列的一个有序排列：
INSERTION-SORT(A)
for i=2 to A.length
key = A[i]
j = i - 1
while j > 0 and A[j] > key
A[j+1] = A[j]
j = j - 1
A[j + 1] = key
算法解析
- 变量
i表示当前待处理元素的索引。 - 我们从第二个元素开始处理，因为只有一个元素的数组天然有序。
- 元素
A[i]被称为key，我们需要在已排序部分中为其找到合适的插入位置。 - 如果
key小于A[j]，则将A[j]向右移动一位。 - 重复该过程，直到找到小于等于
key的元素，或到达数组边界。
⚠️ 注意：在每次处理 key 之前，A[1..j-1] 部分已经完成排序。
3. 命令式实现（Imperative）
我们定义一个方法 insertionSortImperative 来实现插入排序的命令式版本，接收一个整型数组作为参数。从数组的第二个元素开始遍历。
在任意时刻，我们可以将数组逻辑上划分为两部分：
- 左侧是已排序部分
- 右侧是尚未排序部分
✅ 关键点：在找到插入位置后，通过移动（shift）而非交换（swap）的方式为新元素腾出空间。
public static void insertionSortImperative(int[] input) {
for (int i = 1; i < input.length; i++) {
int key = input[i];
int j = i - 1;
while (j >= 0 && input[j] > key) {
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = key;
}
}
测试代码
@Test
void givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc() {
int[] input = {6, 2, 3, 4, 5, 1};
InsertionSort.insertionSortImperative(input);
int[] expected = {1, 2, 3, 4, 5, 6};
assertArrayEquals("the two arrays are not equal", expected, input);
}
✅ 测试结果表明，该方法能正确地将数组 <6, 2, 3, 4, 5, 1> 按升序排序。
4. 递归实现（Recursive）
递归版本的方法名为 insertionSortRecursive，同样接收一个整型数组作为参数。
与命令式版本不同的是，它会调用一个重载方法，传入第二个参数表示当前要排序的元素数量。
我们希望对整个数组排序，因此传入数组长度：
public static void insertionSortRecursive(int[] input) {
insertionSortRecursive(input, input.length);
}
递归实现稍微复杂一些：
- 递归终止条件：当排序元素数量 ≤ 1 时，直接返回。
- 每次递归调用处理前
i-1个元素，然后将第i个元素插入到已排序部分中。
private static void insertionSortRecursive(int[] input, int i) {
if (i <= 1) {
return;
}
insertionSortRecursive(input, i - 1);
int key = input[i - 1];
int j = i - 2;
while (j >= 0 && input[j] > key) {
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = key;
}
递归调用栈示意（输入数组长度为6）
insertionSortRecursive(input, 6)
insertionSortRecursive(input, 5) and insert the 6th item into the sorted array
insertionSortRecursive(input, 4) and insert the 5th item into the sorted array
insertionSortRecursive(input, 3) and insert the 4th item into the sorted array
insertionSortRecursive(input, 2) and insert the 3rd item into the sorted array
insertionSortRecursive(input, 1) and insert the 2nd item into the sorted array
测试代码
@Test
void givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc() {
int[] input = {6, 4, 5, 2, 3, 1};
InsertionSort.insertionSortRecursive(input);
int[] expected = {1, 2, 3, 4, 5, 6};
assertArrayEquals("the two arrays are not equal", expected, input);
}
✅ 递归版本同样能正确排序数组 <6, 2, 3, 4, 5, 1>。
5. 时间与空间复杂度分析
- 时间复杂度：插入排序的时间复杂度为 ✅
O(n²)。在最坏情况下（数组完全逆序），每个元素都要与前面所有元素比较。 - 空间复杂度：
- 命令式实现为 ✅
O(1)，原地排序，无需额外空间。 - 递归实现为 ✅
O(n)，由于递归调用栈的深度为 n。
- 命令式实现为 ✅
6. 总结
本文介绍了插入排序的两种实现方式：命令式与递归式。该算法适合用于排序少量数据（通常不超过 100 个元素）。
虽然它的时间复杂度为 O(n²)，但其 原地排序 的特性使其在某些场景下仍具优势，比如相比需要额外空间的归并排序。
📌 小贴士：插入排序虽然效率不高，但其实现简单、稳定，是很多高级排序算法（如快速排序）的子过程。
完整代码可参考：GitHub 项目地址