插入排序（Insertion Sort）是一种简单直观的排序算法，其核心思想是将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的适当位置，直到整个数组有序。以下是详细的实现思路和示例说明：
基本原理
- 数组分区：将数组视为两部分：左侧为已排序部分，右侧为未排序部分。初始时，已排序部分仅包含第一个元素。
- 遍历未排序部分：从第二个元素开始，逐个取出未排序部分的元素。
- 插入操作：将取出的元素与已排序部分的元素从后向前比较，找到合适的位置插入，确保已排序部分始终有序。
- 重复步骤2-3：直到未排序部分的所有元素都插入到已排序部分。
实现步骤
- 初始化：将数组的第一个元素视为已排序部分（长度为1）。
- 遍历未排序元素：从第二个元素（索引
i=1）开始，遍历到最后一个元素（索引i=n-1）。 - 保存当前元素：将当前元素
arr[i]保存到临时变量key。 - 寻找插入位置：从已排序部分的末尾（索引
j=i-1）开始向前比较，将大于key的元素后移一位，直到找到第一个不大于key的位置。 - 插入元素：将
key插入到该位置。
示例演示
假设我们要对数组 [5, 3, 8, 4, 6] 进行升序排序：
- 初始状态：
[5 | 3, 8, 4, 6]（竖线左侧为已排序部分） - 处理
3：- 已排序部分：
[5] - 未排序部分：
[3, 8, 4, 6] - 取出
3，与5比较，5 > 3，将5后移，插入3。 - 结果：
[3, 5 | 8, 4, 6]
- 已排序部分：
- 处理
8：- 已排序部分：
[3, 5] - 未排序部分：
[8, 4, 6] - 取出
8，与5比较，5 < 8，直接插入。 - 结果：
[3, 5, 8 | 4, 6]
- 已排序部分：
- 处理
4：- 已排序部分：
[3, 5, 8] - 未排序部分：
[4, 6] - 取出
4，与8、5比较，后移8、5，插入4。 - 结果：
[3, 4, 5, 8 | 6]
- 已排序部分：
- 处理
6：- 已排序部分：
[3, 4, 5, 8] - 未排序部分：
[6] - 取出
6，与8、5比较，后移8，插入6。 - 最终结果：
[3, 4, 5, 6, 8]
- 已排序部分：
代码实现
以下是插入排序的Python实现：
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # 当前要插入的元素
j = i - 1 # 已排序部分的最后一个元素索引
# 将大于key的元素后移
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
# 插入key
arr[j + 1] = key
return arr
# 测试
arr = [5, 3, 8, 4, 6]
print("排序前:", arr)
print("排序后:", insertion_sort(arr))
复杂度分析
- 时间复杂度：
- 最好情况：数组已经有序，只需遍历一次，时间复杂度为 $O(n)$。
- 最坏情况：数组完全逆序，每次插入都需移动所有已排序元素，时间复杂度为 $O(n^2)$。
- 平均情况：时间复杂度为 $O(n^2)$。
- 空间复杂度：$O(1)$（原地排序，只需要常数级额外空间）。
- 稳定性：插入排序是稳定的，因为相等元素不会被交换位置。
适用场景
- 小规模数据：插入排序在数据量较小时效率较高。
- 接近有序的数据：如果数组接近有序，插入排序的时间复杂度接近 $O(n)$。
- 在线排序：可以在接收数据的同时进行排序（每次插入一个新元素）。
优化思路
- 二分插入排序：使用二分查找来减少比较次数，将时间复杂度优化到 $O(n \log n)$（比较操作），但移动操作仍需 $O(n^2)$。
- 希尔排序：通过分组插入的方式，进一步提高效率（时间复杂度可优化到 $O(n^{1.3})$）。
插入排序虽然在大数据集上效率不高，但因其简单易实现、空间效率高和稳定性，在特定场景下仍有应用价值。
