插入排序
插入排序（Insertion Sort）是一种简单直观的排序算法，适用于小规模数据或基本有序的数据集。其核心思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上通常采用原地排序（即只需用到O(1)的额外空间），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
算法描述[编辑 | 编辑源代码]
插入排序的工作方式类似于整理扑克牌： 1. 从第一个元素开始，该元素可以认为已经被排序。 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。 4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。 5. 将新元素插入到该位置后。 6. 重复步骤2~5，直到所有元素均排序完毕。
时间复杂度分析[编辑 | 编辑源代码]
- 最坏时间复杂度：（当输入数组逆序时）
- 平均时间复杂度：
- 最好时间复杂度：（当输入数组已排序时）
代码实现[编辑 | 编辑源代码]
以下是插入排序的Python实现示例：
def insertion_sort(arr):
# 遍历从1到n-1的元素
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# 将arr[0..i-1]中比key大的元素向后移动
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # 插入key到正确位置
# 示例使用
if __name__ == "__main__":
data = [12, 11, 13, 5, 6]
print("排序前:", data)
insertion_sort(data)
print("排序后:", data)
输出:
排序前: [12, 11, 13, 5, 6] 排序后: [5, 6, 11, 12, 13]
可视化示例[编辑 | 编辑源代码]
以下是插入排序过程的mermaid图示：
实际应用场景[编辑 | 编辑源代码]
插入排序在以下场景中特别有用： 1. 小规模数据排序：当数据量较小时（通常n<100），插入排序的性能可能优于更复杂的算法如快速排序或归并排序。 2. 基本有序数据：当输入数组"几乎排序"时（即每个元素距离它的最终位置不远），插入排序的效率接近O(n)。 3. 在线算法：插入排序可以一边接收数据一边排序，适用于数据流式的输入场景。 4. 混合排序算法：常被用作快速排序或归并排序等算法的子过程，用于处理小的子数组。
变体与优化[编辑 | 编辑源代码]
二分插入排序[编辑 | 编辑源代码]
通过使用二分查找来找到插入位置，可以将比较次数从O(n^2)减少到O(n log n)，但移动元素的复杂度仍为O(n^2)。
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 key < arr[mid]:
right = mid - 1
else:
left = mid + 1
# 移动元素
for j in range(i - 1, left - 1, -1):
arr[j + 1] = arr[j]
arr[left] = key
希尔排序[编辑 | 编辑源代码]
希尔排序是插入排序的高效改进版本，通过将原始列表分成多个子列表来改进插入排序的性能。
算法比较[编辑 | 编辑源代码]
| 算法 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 插入排序 | O(1) | 稳定 | |
| 冒泡排序 | O(1) | 稳定 | |
| 选择排序 | O(1) | 不稳定 |
练习题目[编辑 | 编辑源代码]
1. 实现一个降序排列的插入排序版本。 2. 修改插入排序算法，使其同时记录每个元素的原始位置。 3. 分析当输入数组已经排序时，插入排序的性能表现。 4. 比较插入排序和选择排序在相同数据集上的性能差异。
总结[编辑 | 编辑源代码]
插入排序虽然在大规模数据上效率不高，但由于其实现简单、对小规模数据高效、对基本有序数据表现优异等特点，仍然在实际应用中有其一席之地。理解插入排序有助于掌握更复杂的排序算法，也是学习算法设计与分析的良好起点。