为何实现的Insertion_Sort未排序反而出现列表元素重复？

问题描述 #

参照讲义示例实现插入排序后，函数未将数组按升序排序，反而出现元素重复；调整range结束值为n后，数组中3重复、2消失；调换while循环中array[j]与array[j-1]的位置后，重复元素变为2、3消失，始终无法得到正确结果[1,2,3]。

错误代码 #

def function insertion_sort(array):
    
    n = len(array)
    
    for i in range(1, n-1): 
        j = i #j is inner index, i is inner index
        temporary = array[j]
       
        
        while (j > 0) and (array[j] < array[j-1]):
            array[j]= array[j - 1]#shift right
            j = j - 1 #move left 
            print(array)
            
        array[j] = temporary #save to final position

array = [3,2,1] #test case
insertion_sort(array)

尝试修改后的异常结果 #

• 将n-1改为n后的结果：

  [3, 3, 1] #3 is duplicated, 2 has disappeared
  

• 调换数组位置后的结果：

  [2, 2, 1] #2 is duplicated, 3 has disappeared
  

问题根源分析 #

1. 函数定义语法错误：
   Python函数定义格式为def 函数名(参数):，错误代码中多了function关键词，这会直接导致函数定义失败（若实际运行时未修正，代码无法正常执行）。

2. 外层循环范围错误：
   插入排序需要从第二个元素（索引1）开始，遍历到最后一个元素（索引n-1）。原代码中range(1, n-1)是左闭右开区间，对于长度为3的数组，仅会循环i=1，完全没处理索引2的元素（值为1），导致排序不完整。

3. while循环比较逻辑错误：
   进入循环前已将当前元素值存入temporary，但循环中第一步就执行array[j] = array[j-1]覆盖了array[j]的原值。原代码用array[j] < array[j-1]作为比较条件，实际是拿已经被覆盖后的元素值和前一个元素比较，而非原本要插入的temporary值，这会导致元素被错误覆盖，出现重复或丢失。

修正后的代码 #

def insertion_sort(array):
    n = len(array)
    # 修正循环范围：遍历从索引1到最后一个元素
    for i in range(1, n):  
        j = i
        temporary = array[j]
        # 用保存的临时值与前一个元素比较，避免覆盖后的错误值干扰
        while j > 0 and temporary < array[j-1]:
            array[j] = array[j-1]  # 元素右移，腾出插入位置
            j -= 1
        array[j] = temporary  # 将临时值插入正确位置

array = [3,2,1]
insertion_sort(array)
print(array)  # 输出：[1, 2, 3]

修正说明 #

• 移除函数定义中的多余function关键词，保证语法合法；
• 外层循环改为range(1, n)，确保所有需要插入的元素都被处理；
• while循环条件改为用temporary与array[j-1]比较，基于原本要插入的元素值判断是否需要右移，避免元素被错误覆盖。

内容的提问来源于stack exchange，提问作者tan qi xiang