自定义InsertionSort算法异常求助：代码输出结果不符合预期

你的代码执行后得到[1,5,8,8,8,8]这种异常结果，核心原因是没有保存待插入元素的原始值，导致移动元素时覆盖了它，最后赋值用的是被修改后的值。

问题细节 #

以处理i=3（对应元素2）为例：

• j=2（元素8），因为8>2，执行x[3] = x[2]，此时原列表里的x[3]（也就是2）已经被替换成8。
• 接着j=1（元素5），判断x[j] > x[i]时，x[i]已经是8，5不大于8，于是跳出循环，执行x[index] = x[i]，也就是把8赋值到对应位置，原始的2彻底丢失。
• 后面处理7和4时，同样的逻辑会让x[i]被前面的8覆盖，最终所有后续位置都变成8。

修正后的代码 #

def insertionsort(x):
    i = 1
    while 1 <= i < len(x):
        # 提前保存待插入元素的原始值，避免被覆盖
        temp = x[i]
        j = i - 1
        # 向前遍历，找到temp应该插入的位置
        while j >= 0 and x[j] > temp:
            # 把比temp大的元素向后移一位
            x[j+1] = x[j]
            j -= 1
        # 将temp插入到正确位置
        x[j+1] = temp
        i += 1
    return x

# 测试
print(insertionsort([1,5,8,2,7,4]))  # 输出 [1,2,4,5,7,8]

关键修改点 #

• 新增temp = x[i]，锁定待插入元素的原始值，确保移动元素过程中不会丢失。
• 内层循环条件改为j >= 0 and x[j] > temp，直接用保存的temp比较，不再依赖可能被修改的x[i]。
• 去掉冗余的index变量，直接用j+1作为插入位置，逻辑更简洁清晰。

内容的提问来源于stack exchange，提问作者maths and chess