插入排序（Insertion Sort）是一种简单直观的排序算法，适用于少量数据排序。其核心思想是：将数组划分为已排序和未排序部分，每次从未排序部分取一个元素插入到已排序部分的合适位置。
1. 算法思路
- 从数组的第二个元素开始，将其作为当前待插入元素，向前检查它应该插入的位置。
- 依次与前面的元素进行比较，如果前面的元素较大，则向后移动，直到找到合适的位置插入当前元素。
- 继续处理下一个元素，重复以上步骤，直到数组全部排序完毕。
2. 代码实现
Python 版
def insertion_sort(arr):
n = len(arr)
for i in range(1, n): # 从索引 1 开始
key = arr[i] # 取当前待插入元素
j = i - 1
while j >= 0 and arr[j] > key: # 向前比较并移动元素
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # 插入元素到正确位置
return arr
# 测试
data = [12, 11, 13, 5, 6]
print("排序前:", data)
sorted_data = insertion_sort(data)
print("排序后:", sorted_data)
输出：
排序前: [12, 11, 13, 5, 6]
排序后: [5, 6, 11, 12, 13]
C 语言版
#include <stdio.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) { // 移动比 key 大的元素
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 插入 key
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int data[] = {12, 11, 13, 5, 6};
int n = sizeof(data) / sizeof(data[0]);
printf("排序前: ");
printArray(data, n);
insertionSort(data, n);
printf("排序后: ");
printArray(data, n);
return 0;
}
3. 时间复杂度分析
| 场景 | 时间复杂度 |
|---|---|
| 最佳情况（数组已排序） | O(n) |
| 最坏情况（数组逆序） | O(n²) |
| 平均情况 | O(n²) |
- 最坏情况：如果输入数组是逆序排列的，则每个元素都需要向前移动，时间复杂度为 O(n²)。
- 最佳情况：如果输入数组已经有序，每次插入时都无需移动，时间复杂度为 O(n)。
- 空间复杂度：O(1)，只使用了常数级别的额外空间（原地排序）。
4. 插入排序 vs 其他排序
| 排序算法 | 时间复杂度 (平均) | 最坏情况 | 额外空间 | 是否稳定 |
|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | ✅ 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | ❌ 不稳定 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | ✅ 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | ✅ 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ❌ 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ❌ 不稳定 |
5. 插入排序的优化
优化思路 1：二分插入排序
普通插入排序的插入过程需要线性查找，可以优化为二分查找：
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
left, right = 0, i - 1
while left <= right: # 使用二分查找找到插入位置
mid = (left + right) // 2
if arr[mid] > key:
right = mid - 1
else:
left = mid + 1
# 插入元素，并移动数组元素
j = i - 1
while j >= left:
arr[j + 1] = arr[j]
j -= 1
arr[left] = key
return arr
时间复杂度： O(n²)（查找是 O(log n)，但移动数据仍然是 O(n)）
6. 插入排序适用场景
- 数据量小（当 n 较小时，插入排序的常数系数较小，比快速排序更高效）。
- 数据大部分已排序（当输入数据接近有序时，插入排序时间复杂度趋近于 O(n)）。
- 需要稳定排序（插入排序不会改变相同元素的相对顺序）。
7. 练习题
- 实现插入排序（递归版）。
- 对链表进行插入排序（要求 O(n²)）。
- 使用插入排序对一个近乎有序的数组排序，分析性能。
- 对 100 万个数据进行排序，比较插入排序与快速排序的性能。
8. 相关链接
🔗 LeetCode – 插入排序列表
🔗 GeeksforGeeks – Insertion Sort
🔗 Algorithm Visualizer – 插入排序动画
9. 参考资料
- 《算法导论》—— Thomas H. Cormen
- 《数据结构与算法分析》—— Mark Allen Weiss
- GeeksforGeeks – Sorting Algorithms
插入排序虽简单，但在某些场景下仍然高效，尤其是用于小规模数据集或接近有序的数组。希望这篇详解能帮你彻底理解插入排序！🚀
发表回复