本文详解插入排序中因未暂存待插入元素而导致数组值被意外覆盖的常见错误，并提供修复后的完整代码及优化建议。

本文详解插入排序中因未暂存待插入元素而导致数组值被意外覆盖的常见错误，并提供修复后的完整代码及优化建议。

插入排序的核心思想是：将数组分为已排序和未排序两部分，每次从未排序区取一个元素，将其插入到已排序区的合适位置。在实现过程中，关键在于**为待插入元素保留一份独立副本**——否则，在向后移动较大元素的过程中，原始 `x[i]` 的值可能被覆盖，导致后续赋值出错。

你提供的代码中，问题正源于此：当执行 x[j+1] = x[j] 时，若 j+1 == i（即首次移动就覆盖了当前位置），x[i] 的原始值便永久丢失。后续 x[index] = x[i] 实际写入的是已被污染的值，从而引发如 [1,5,8,8,8,8] 这类明显错误结果。

以下是修复后的正确实现（仅修改关键三处，逻辑保持原结构）：

def insertionsort(x):
    i = 1
    while i < len(x):  # 简化条件：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  # ✅ 使用保存的值，而非 x[i]
        i += 1
    return x

注意事项与优化建议：

• 暂存变量不可省略：val = x[i] 是插入排序稳定性和正确性的基石；
• 边界条件精简：while i 比 <code>i>=1 and i<len> 更直观；<code>while j >= 0 and x[j] > val 同时检查索引与比较逻辑，避免冗余判断；
• Pythonic 改写推荐（更符合 Python 风格）：

  def insertion_sort(arr):
      for i in range(1, len(arr)):
          key = arr[i]
          j = i - 1
          while j >= 0 and arr[j] > key:
              arr[j + 1] = arr[j]
              j -= 1
          arr[j + 1] = key
      return arr

• 测试验证：
  print(insertion_sort([1, 5, 8, 2, 7, 4])) → 输出 [1, 2, 4, 5, 7, 8]，结果正确。

掌握这一“暂存—移动—回填”三步模式，不仅能修复插入排序，也为理解其他原地排序算法（如希尔排序）奠定坚实基础。