python - 插入排序中的比较次数

Question

在这个程序中，我想计算插入排序中的数据比较次数，但是我的代码没有按预期工作。

def insertionSort(list):
    numOfComp = 0
    for i in range(1,len(list)):
        value = list[i]
        j = i - 1
        while j>=0:
            if value < list[j]:
                list[j+1] = list[j]
                list[j] = value
                j = j - 1
                numOfComp += 1
            if value >= list[j]:
                numOfComp += 1
                j = j - 1
            else:
                break
    print("Number of data comparisons:",numOfComp)
    print("Sorted list:",list)

Answer 1

问题是

if value >= list[j]:
     numOfComp += 1
     j = j - 1

如果value >= list[j]你可以而且应该简单地退出你的while循环并停止进一步的comarisons

此外，您重复比较两次请参阅以下精炼代码

def insertionSort(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("Number of data comparisons:",numOfComp)
    print("Sorted list:",list)

Answer 2

不要忘记循环头比循环体多执行+1，我们称之为退出条件，举个例子：

S = 0;
for(int i = 0; i < 5; i++) {
    S++;
}

S++ 运行了5 次，而i < 5运行了 6 次，最后一个是检查 i < 5 是否为假，然后退出循环。