上一篇
Python插入排序算法实现教程 - 详细步骤与代码示例
NingPanHuo
- Python
- 2025-08-08
- 1333
Python插入排序算法实现教程
什么是插入排序？
插入排序是一种简单直观的排序算法，其工作原理类似于我们整理扑克牌的方式：
- 将数组分为已排序和未排序两部分
- 每次从未排序部分取出第一个元素
- 将其插入到已排序部分的正确位置
- 重复此过程直到所有元素排序完成
插入排序工作原理
逐步演示
以数组 [5, 2, 4, 6, 1, 3] 为例：
- 初始状态: [5, 2, 4, 6, 1, 3] (已排序部分:5)
- 第1步: [2, 5, 4, 6, 1, 3] (插入2)
- 第2步: [2, 4, 5, 6, 1, 3] (插入4)
- 第3步: [2, 4, 5, 6, 1, 3] (插入6)
- 第4步: [1, 2, 4, 5, 6, 3] (插入1)
- 第5步: [1, 2, 3, 4, 5, 6] (插入3)
算法特点
- 时间复杂度: O(n²) 最坏和平均情况, O(n) 最好情况
- 空间复杂度: O(1) 原地排序
- 稳定性: 稳定排序算法
- 适用场景: 小规模数据或基本有序的数据集
- 优点: 实现简单，对小数据集高效
- 缺点: 对大数据集效率较低
Python实现插入排序
下面是插入排序的Python实现代码：
def insertion_sort(arr):
# 遍历从1到数组长度
for i in range(1, len(arr)):
key = arr[i] # 当前需要插入的元素
j = i - 1 # 已排序部分的最后一个元素索引
# 将大于key的元素向后移动
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
# 插入key到正确位置
arr[j + 1] = key
# 测试插入排序
if __name__ == "__main__":
data = [5, 2, 4, 6, 1, 3]
print("原始数组:", data)
insertion_sort(data)
print("排序后数组:", data)代码解释
- 外层循环: 从数组的第二个元素开始遍历（索引1），逐个处理未排序元素
- 保存当前值: 将当前需要插入的元素保存在变量key中
- 内层循环: 将key与已排序部分的元素从后向前比较
- 元素后移: 当遇到比key大的元素时，将其向后移动一位
- 插入元素: 找到key的正确位置后，将其插入
插入排序可视化
插入排序的优化
虽然基本插入排序已经很高效了，但我们还可以进行一些优化：
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 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实际应用场景
插入排序在以下场景中特别有用：
- 小规模数据排序（n ≤ 100）
- 数据基本有序的情况
- 作为更高级排序算法（如TimSort）的一部分
- 在线算法（数据逐个到达时排序）
- 链表排序（插入操作高效）
总结
插入排序是一种简单但有效的排序算法，特别适合小规模数据集。通过本教程，您应该已经掌握了：
- 插入排序的基本原理和工作方式
- 使用Python实现插入排序
- 理解插入排序的时间复杂度和适用场景
- 优化插入排序的方法
虽然对于大型数据集有更高效的排序算法（如快速排序、归并排序），但插入排序仍然是算法学习中的重要基础，并在特定场景下保持其实用价值。
本文由NingPanHuo于2025-08-08发表在吾爱品聚，如有疑问，请联系我们。
本文链接：https://liuhe.jltcw.com/20257620.html
发表评论