本文目录导读：
我来给你介绍插入排序的Python实现,包括基础版本和优化版本。
基础插入排序实现
def insertion_sort(arr):
"""
插入排序基础实现
时间复杂度: O(n²)
空间复杂度: O(1)
"""
# 遍历数组，从第二个元素开始
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
arr[j + 1] = key # 插入key到正确位置
return arr
# 测试
if __name__ == "__main__":
numbers = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", numbers)
sorted_numbers = insertion_sort(numbers.copy())
print("排序后数组:", sorted_numbers)
带详细注释的版本
def insertion_sort_detailed(arr):
"""
插入排序（带详细注释）
就像整理扑克牌一样，每次将一张牌插入到已排序的手牌中
"""
# 从第2个元素开始（索引1），因为第1个元素（索引0）默认已排序
for i in range(1, len(arr)):
current = arr[i] # 当前要插入的元素
position = i # 记录插入位置
print(f"第{i}轮: 要插入的元素 = {current}")
print(f"已排序部分: {arr[:i]}")
# 在已排序部分从右向左查找插入位置
while position > 0 and arr[position - 1] > current:
arr[position] = arr[position - 1] # 较大元素后移
position -= 1
# 插入当前元素到正确位置
arr[position] = current
print(f"插入后: {arr}\n")
return arr
# 测试带详细注释的版本
numbers = [5, 2, 4, 6, 1, 3]
print("排序过程演示:")
print(f"初始数组: {numbers}\n")
result = insertion_sort_detailed(numbers.copy())
print(f"最终结果: {result}")
优化版本（二分查找插入）
import bisect
def insertion_sort_optimized(arr):
"""
优化版本：使用二分查找快速定位插入位置
但元素移动的时间复杂度仍然是O(n)
"""
for i in range(1, len(arr)):
key = arr[i]
# 使用二分查找找到插入位置
# 在已排序部分[0:i]中查找key应该插入的位置
left, right = 0, i
while left < right:
mid = (left + right) // 2
if arr[mid] <= key:
left = mid + 1
else:
right = mid
# 将元素右移，为新元素腾出位置
for j in range(i, left, -1):
arr[j] = arr[j - 1]
arr[left] = key
return arr
# 测试
test_arr = [3, 8, 2, 5, 1, 4, 7, 6]
print(f"原始数组: {test_arr}")
result = insertion_sort_optimized(test_arr.copy())
print(f"排序后数组: {result}")
综合示例：不同数据类型的排序
def generic_insertion_sort(arr, key=lambda x: x, reverse=False):
"""
通用插入排序：支持自定义排序规则
"""
arr = arr.copy() # 避免修改原数组
for i in range(1, len(arr)):
current = arr[i]
j = i - 1
# 根据reverse参数决定比较方式
while j >= 0:
if reverse:
if key(arr[j]) < key(current):
arr[j + 1] = arr[j]
j -= 1
else:
break
else:
if key(arr[j]) > key(current):
arr[j + 1] = arr[j]
j -= 1
else:
break
arr[j + 1] = current
return arr
# 测试不同类型的排序
if __name__ == "__main__":
# 1. 整数排序
numbers = [64, 34, 25, 12, 22, 11, 90]
print("整数排序:")
print(f"升序: {generic_insertion_sort(numbers)}")
print(f"降序: {generic_insertion_sort(numbers, reverse=True)}")
# 2. 字符串排序
words = ["banana", "apple", "cherry", "date"]
print(f"\n字符串排序:")
print(f"升序: {generic_insertion_sort(words)}")
print(f"按长度排序: {generic_insertion_sort(words, key=len)}")
# 3. 字典排序
students = [
{"name": "Alice", "score": 85},
{"name": "Bob", "score": 92},
{"name": "Charlie", "score": 78}
]
sorted_by_score = generic_insertion_sort(
students,
key=lambda s: s["score"]
)
print(f"\n按成绩排序:")
for student in sorted_by_score:
print(f" {student['name']}: {student['score']}")
性能测试
import time
import random
def performance_test():
"""比较不同排序算法的性能"""
# 生成测试数据
sizes = [100, 500, 1000, 2000, 5000]
for size in sizes:
# 生成随机数组
arr = [random.randint(1, 10000) for _ in range(size)]
# 测试插入排序
arr_copy = arr.copy()
start = time.time()
insertion_sort(arr_copy)
time_insertion = time.time() - start
# 测试Python内置排序
arr_copy2 = arr.copy()
start = time.time()
arr_copy2.sort()
time_builtin = time.time() - start
print(f"n={size:5}: 插入排序={time_insertion:.6f}s, "
f"内置排序={time_builtin:.6f}s, "
f"比例={time_insertion/time_builtin:.2f}")
# 运行性能测试（注意：当数据量较大时可能会比较慢）
# performance_test()
使用示例
# 简单使用示例
arr = [12, 11, 13, 5, 6, 7]
print(f"排序前: {arr}")
insertion_sort(arr)
print(f"排序后: {arr}")
# 结果:
# 排序前: [12, 11, 13, 5, 6, 7]
# 排序后: [5, 6, 7, 11, 12, 13]
算法特点
时间复杂度：
- 最好情况：O(n) - 数组已经有序
- 最坏情况：O(n²) - 数组逆序
- 平均情况：O(n²)
空间复杂度： O(1) - 原地排序
稳定性： 稳定排序
适用场景：
- 小规模数据（n < 50）
- 数据基本有序的情况
- 在线算法（可以边接收数据边排序）
插入排序在数据量较小时效率很高，实际应用中常用于其他高级排序算法（如快速排序）的优化,在小规模子数组上使用插入排序。
