插入排序比较次数统计错误：输入3 2 1 5 9 8得9次而非7次

你的代码问题出在比较次数的统计逻辑错误，导致多算了2次比较。以下是具体分析和修正方案：

问题根源 #

原代码中，你在while循环内统计条件为真的比较，循环结束后又无条件加1次比较，但忽略了两种关键情况：

1. 当循环因j=0退出时，并没有执行numbers[j] < numbers[j-1]的比较（逻辑与的短路特性：j>0不成立时，不会判断后半句），此时循环外的comparisons +=1属于无效统计。
2. 当循环因numbers[j] >= numbers[j-1]退出时，确实进行了一次比较，但原代码的统计方式在部分场景下重复计数。

以输入3 2 1 5 9 8为例：

• 处理i=1（元素2）时，循环结束后额外加1次，多算1次；
• 处理i=2（元素1）时，循环结束后额外加1次，又多算1次；
• 最终总次数比正确值多2次（9 vs 7）。

修正方案 #

将比较次数的统计调整为每次实际执行numbers[j]与numbers[j-1]的比较时就计数，不管比较结果是真还是假。修改insertion_sort函数的循环逻辑：

def insertion_sort(numbers):
    """Sort the list numbers using insertion sort"""
    global comparisons
    global swaps

    for i in range(1, len(numbers)):
        j = i
        # Insert numbers[i] into the sorted part
        # stopping once numbers[i] is in the correct position
        while j > 0:
            comparisons += 1  # 每一次比较都计数
            if numbers[j] < numbers[j - 1]:
                swap(numbers, j, j - 1)
                swaps += 1
                j -= 1
            else:
                break  # 找到正确位置，停止比较

        # Output the list during each iteration of the outside loop
        print_nums(numbers)
        print()  # Add a newline after each iteration

验证结果 #

修改后，输入3 2 1 5 9 8时：

• 比较次数会准确统计为7次，交换次数为4次，完全符合预期。

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