本文详解插入排序自定义实现中因未保存待插入元素而引发的数组覆盖问题，并提供修正后的代码及优化建议。
本文详解插入排序自定义实现中因未保存待插入元素而引发的数组覆盖问题，并提供修正后的代码及优化建议。
插入排序的核心思想是：将数组分为已排序和未排序两部分，每次从未排序区取一个元素（即 x[i]），在已排序区（x[0:i]）中找到其正确位置并插入。初学者常犯的一个典型错误，是在“前移较大元素”的过程中直接覆盖了待插入的原始值——这会导致后续赋值时使用的是已被篡改的数据，最终产生如 [1,5,8,8,8,8] 这类重复、失真的结果。
问题根源在于原代码中未对 x[i] 做临时保存。当执行 x[j+1] = x[j] 时，若 j+1 == i（即首次前移就覆盖 i 位置），x[i] 的原始值即永久丢失。后续 x[index] = x[i] 实际写入的是被覆盖后的错误值，而非最初待插入的数。
修正方案：在内层循环开始前，用临时变量 val = x[i] 保存该值；所有比较（x[j] > val）和最终赋值（x[index] = val）均基于此不变量。以下是修复后的完整实现：
def insertionsort(x):
i = 1
while i = 1 恒成立，可省略
j = i - 1
val = x[i] # ✅ 关键：提前保存待插入元素
while j >= 0 and x[j] > val: # ✅ 合并边界与比较逻辑，更清晰
x[j + 1] = x[j]
j -= 1
x[j + 1] = val # ✅ 插入到正确位置（j+1 是首个 ≤ val 的位置后）
i += 1
return x
# 测试
print(insertionsort([1, 5, 8, 2, 7, 4])) # 输出: [1, 2, 4, 5, 7, 8]
注意事项：
- 原代码中
while(0 可简化为j >= 0，因为j由i-1递减，不可能超过i； -
index变量非必需——j+1即为最终插入位置，直接使用更简洁； - Python 中推荐使用
for循环替代while（更符合 Python 风格），例如：for i in range(1, len(x)):； - 该算法为原地排序，时间复杂度最坏为 O(n²)，适用于小规模或基本有序数据。
掌握“先保存、再移动、后插入”这一模式，是正确实现插入排序的关键，也适用于其他需原地调整的类似算法。
