“插入排序”的英文名是 Insertion Sort,它是一种简单直观的排序算法。
（图片来源网络，侵删）
算法核心思想
插入排序的核心思想就像我们整理一副扑克牌：
- 假设有序：我们首先认为手中的第一张牌已经是有序的。
- 逐个插入：我们从第二张牌开始,依次取出每一张牌。
- 比较和移动：将取出的这张牌，与它前面已经排好序的牌进行比较，从后向前找到它应该在的位置，并将这个位置以及之后的所有牌都向后移动一位,为这张新牌腾出空间。
- 插入：将这张牌插入到正确的位置。
这个过程重复进行，直到所有的牌都被插入到正确的位置,整个序列就变得有序了。
算法步骤分解
假设我们要对一个数组 [5, 2, 4, 6, 1, 3] 进行从小到大排序。
-
初始状态：
[5, 2, 4, 6, 1, 3]
（图片来源网络，侵删）- 我们把第一个元素
5看作是一个已排序的子数组[5]。 - 剩下的
[2, 4, 6, 1, 3]是未排序的部分。
- 我们把第一个元素
-
第一轮：插入
2- 从未排序部分取出第一个元素
2。 - 将
2与已排序子数组的最后一个元素5比较，因为2 < 5，5需要向后移动一位。 - 已排序子数组变为
[ , 5]，2被放在空位上。 - 结果:
[2, 5, 4, 6, 1, 3]
- 从未排序部分取出第一个元素
-
第二轮：插入
4- 从未排序部分取出
4。 - 将
4与已排序子数组的最后一个元素5比较，因为4 < 5，5向后移动。 - 已排序子数组变为
[2, , 5]。 - 再将
4与新的最后一个元素2比较，因为4 > 2,所以找到了正确的位置。 - 结果:
[2, 4, 5, 6, 1, 3]
- 从未排序部分取出
-
第三轮：插入
6- 从未排序部分取出
6。 - 将
6与已排序子数组的最后一个元素5比较，因为6 > 5，6不需要移动，直接放在5的后面。 - 结果:
[2, 4, 5, 6, 1, 3]
- 从未排序部分取出
-
第四轮：插入
1- 从未排序部分取出
1。 1需要与6,5,4,2依次比较，并把这些元素都向后移动,直到找到最前面。- 结果:
[1, 2, 4, 5, 6, 3]
- 从未排序部分取出
-
第五轮：插入
3- 从未排序部分取出
3。 3需要与6,5,4依次比较并移动，直到找到2和4之间。- 结果:
[1, 2, 3, 4, 5, 6]
- 从未排序部分取出
-
结束：未排序部分为空,排序完成。
Python 代码实现
下面是插入排序的 Python 代码实现,包含了详细的注释来解释每一步。
标准实现（推荐）
def insertion_sort(arr):
"""
对给定的数组进行插入排序
:param arr: 需要排序的列表
:return: 无返回值，直接在原列表上进行排序
"""
# 遍历数组从第二个元素开始 (索引 1)
# 因为第一个元素可以看作是一个只有一个元素的已排序子数组
for i in range(1, len(arr)):
# key 是当前待插入的元素
key = arr[i]
# j 是已排序子数组的最后一个元素的索引
j = i - 1
# 将 key 与已排序子数组中的元素从后向前进行比较
# key 比前一个元素小，就将前一个元素向后移动
# 循环继续，直到找到 key 的正确位置或到达数组开头
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j] # 将元素向后移动一位
j -= 1 # 指向前一个元素继续比较
# 循环结束后，j + 1 key 的正确位置
arr[j + 1] = key
# --- 使用示例 ---
my_list = [12, 11, 13, 5, 6]
print("原始数组:", my_list)
insertion_sort(my_list)
print("排序后数组:", my_list)
输出:
原始数组: [12, 11, 13, 5, 6]
排序后数组: [5, 6, 11, 12, 13]更直观的写法（使用 pop 和 insert）
这种写法更容易理解，但性能稍差，因为 pop 和 insert 操作本身就有时间开销。
def insertion_sort_visual(arr):
"""
使用 pop 和 insert 实现的插入排序，更直观但性能略低
"""
# 遍历数组从第二个元素开始
for i in range(1, len(arr)):
# 取出当前待插入的元素
current_value = arr.pop(i)
# 从已排序部分的末尾开始向前查找插入位置
j = i - 1
while j >= 0 and current_value < arr[j]:
j -= 1
# 在找到的位置插入元素
arr.insert(j + 1, current_value)
# --- 使用示例 ---
my_list_2 = [12, 11, 13, 5, 6]
print("原始数组:", my_list_2)
insertion_sort_visual(my_list_2)
print("排序后数组:", my_list_2)
算法分析
时间复杂度
- 最佳情况：O(n)，当输入数组已经是排序好的状态时，对于每个元素
arr[i]，while循环只会比较一次（arr[i-1] <= arr[i]），然后就结束了，总共需要 n-1 次比较。 - 最坏情况：O(n²)，当输入数组是逆序排序时，对于每个元素
arr[i]，while循环需要比较 i 次，总比较次数为 1 + 2 + 3 + ... + (n-1) = n(n-1)/2。 - 平均情况：O(n²)，对于随机顺序的数组，平均时间复杂度也是 O(n²)。
空间复杂度
- O(1)，插入排序是原地排序算法，它不需要额外的存储空间来存储另一份数组，只使用了常数个额外变量（如
key,j等）。
稳定性
- 稳定，插入排序是稳定的排序算法，当两个相等元素的值相等时，由于我们用的是
key < arr[j]（而不是<=），所以不会发生交换,它们原有的相对顺序会保持不变。
优缺点总结
优点
- 实现简单：代码逻辑非常直观,容易理解和实现。
- 空间效率高：是原地排序，空间复杂度为 O(1)。
- 对小规模数据高效：当数据量
n很小时，插入排序的性能可能比一些更复杂的算法（如快速排序）要好。 - 稳定排序：可以保持相等元素的原始顺序。
- 自适应：对于部分有序的数据,效率很高。
缺点
- 性能较差：对于大规模数据，时间复杂度为 O(n²)，效率非常低，远不如 O(n log n) 的算法（如归并排序、堆排序、快速排序）。
- 数据移动多：在插入元素时，需要移动大量的元素，这在链表结构中可以通过指针操作优化,但在数组中成本较高。
| 特性 | 描述 |
|---|---|
| 中文名 | 插入排序 |
| 英文名 | Insertion Sort |
| 核心思想 | 将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置。 |
| 时间复杂度 | 最佳: O(n), 平均: O(n²), 最差: O(n²) |
| 空间复杂度 | O(1) |
| 稳定性 | 稳定 |
| 适用场景 | 数据量小、数据基本有序、或作为更复杂排序算法的子过程（如 Timsort）。 |
在 Python 的实际开发中，你几乎不会自己手动实现插入排序，因为内置的 list.sort() 方法和 sorted() 函数使用了非常高效的 Timsort 算法，它结合了归并排序和插入排序的优点，在各种情况下都能表现出色,学习插入排序是理解排序算法基础和思想的重要一步。
![Python reversed()怎么用？[::-1]和它有啥区别？](https://www.jerry.net.cn/zb_users/cache/thumbs/ed28fc61e3e820b31c4e5ed7c6a8b7fc-252-157-1.jpeg)
