插入排序比较次数统计异常：data1实际15次vs预期19次求排查

我正在统计插入排序的比较次数，针对测试数据data1=[10, 30, 80, 70, 20, 60, 40]，当前代码输出15次，但预期应为19次，请问我的代码存在什么问题？

问题代码 #

def insertionSorts(list):
    numOfComp = 0
    for i in range(1,len(list)):
        value = list[i]
        j = i - 1
        while j>=0:
            if value<list[j]:
                flag=True
            else :
                flag=False
            numOfComp += 1
            if flag:
                list[j+1] = list[j]
                list[j] = value
                j = j - 1
            else:
                break
    print (numOfComp)


data1 = [10, 30, 80, 70, 20, 60, 40]
insertionSorts(data1)
print(data1)
print('No.of Comparisons: ', totalcompi)
print()

问题分析与解答 #

首先，你的代码实现的是交换式插入排序，手动统计其比较次数确实为15次，和代码输出一致。如果参考资料预期是19次，大概率是两者的比较次数定义不同，或者你误解了参考资料的测试场景：

1. 计数规则差异
   部分资料会错误地将“元素移动操作”计入比较次数，或者对插入排序的比较逻辑定义不同（比如强制要求对前面所有元素完成比较，即使已经找到插入位置）。但从标准插入排序的定义来看，你的计数逻辑是正确的：每一次元素间的大小比较都计数一次，找到插入位置后立即终止当前元素的比较。

2. 代码本身的小问题
   代码最后一行打印totalcompi是未定义变量，会抛出NameError，需要修正为将函数内的numOfComp作为返回值，再在外部打印：

   def insertionSorts(list):
       numOfComp = 0
       for i in range(1,len(list)):
           value = list[i]
           j = i - 1
           while j>=0:
               if value<list[j]:
                   flag=True
               else :
                   flag=False
               numOfComp += 1
               if flag:
                   list[j+1] = list[j]
                   list[j] = value
                   j = j - 1
               else:
                   break
       return numOfComp
   
   
   data1 = [10, 30, 80, 70, 20, 60, 40]
   totalcompi = insertionSorts(data1)
   print(data1)
   print('No.of Comparisons: ', totalcompi)
   

3. 验证标准计数
   手动统计标准插入排序的比较次数：

   • 30与10比较：1次
   • 80与30比较：1次
   • 70与80、30比较：2次
   • 20与70、80、30、10比较：4次
   • 60与80、70、30比较：3次
   • 40与80、70、60、30比较：4次
     总和：1+1+2+4+3+4=15次，和你的代码输出完全一致。

如果参考资料确实针对该数组给出19次的预期，建议核对其插入排序的具体实现逻辑和计数规则，大概率是规则定义差异导致的。

内容的提问来源于stack exchange，提问作者yasara