算法概述
插入排序（Insertion Sort）是一种直观且高效的稳定排序算法，其核心思想是将待排序元素逐个插入到已排序序列的正确位置。对于小规模数据或接近有序的数据，插入排序的性能甚至可以超越快速排序。本文将用Java实现基础插入排序，并引入折半查找优化定位插入点，将比较复杂度从O(n)降至O(log n)。
核心原理
假设数组前i个元素已经有序，第i+1个元素需要找到合适的位置插入。基础做法是从后向前线性扫描已排序区间；优化做法是使用二分查找在已排序区间中定位插入点，再通过批量移动元素完成插入。
完整Java实现
public class InsertionSort {
/**
* 基础插入排序：从后向前线性扫描找到插入位置
* 时间复杂度：最坏O(n²)，最好O(n)，平均O(n²)
* 空间复杂度：O(1)
* 稳定性：稳定
*/
public static void basicInsertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 从后向前扫描，将大于key的元素后移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
/**
* 折半插入排序：使用二分查找定位插入点
* 比较次数降至O(n log n)，移动次数仍为O(n²)
*/
public static void binaryInsertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
// 在arr[0..i-1]中使用二分查找定位插入点
int left = 0, right = i - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// left即为插入位置，将[left, i-1]的元素后移一位
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = key;
}
}
/**
* 带哨兵的插入排序优化：减少边界判断
*/
public static void sentinelInsertionSort(int[] arr) {
int n = arr.length;
// 找到最小元素放到arr[0]作为哨兵
int minIdx = 0;
for (int i = 1; i < n; i++) {
if (arr[i] < arr[minIdx]) {
minIdx = i;
}
}
int temp = arr[0];
arr[0] = arr[minIdx];
arr[minIdx] = temp;
for (int i = 2; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 有哨兵保护，无需j>=0判断
while (arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
int[] arr2 = arr1.clone();
int[] arr3 = arr1.clone();
basicInsertionSort(arr1);
System.out.println("基础插入排序: " + java.util.Arrays.toString(arr1));
binaryInsertionSort(arr2);
System.out.println("折半插入排序: " + java.util.Arrays.toString(arr2));
sentinelInsertionSort(arr3);
System.out.println("哨兵插入排序: " + java.util.Arrays.toString(arr3));
}
}
复杂度分析
| 版本 | 最好时间 | 平均时间 | 最坏时间 | 空间 | 比较次数 | 移动次数 |
|---|---|---|---|---|---|---|
| 基础插入 | O(n) | O(n²) | O(n²) | O(1) | O(n²) | O(n²) |
| 折半插入 | O(n) | O(n²) | O(n²) | O(1) | O(n log n) | O(n²) |
| 哨兵插入 | O(n) | O(n²) | O(n²) | O(1) | O(n²) | O(n²) |
折半插入排序虽然比较次数减少，但元素移动次数不变，因此在元素较大的场景下优势有限；当比较操作代价高于移动操作时（如字符串排序），折半优化效果显著。
应用场景
- 数据量较小（n < 50）时的首选排序算法
- 数据基本有序时的最优选择
- 作为快速排序/归并排序的递归终止条件（小规模切到插入排序）
- 在线排序场景（数据流逐个到达）
