为何我的插入排序算法比较次数统计结果偏多？

你遇到的问题很明确——每次处理完一个元素后，额外加的那行comparison_count += 1重复统计了一次比较操作。

咱们拆解下你的代码逻辑：
在insertion_sort里，while循环的条件position > 0 and compare(data, position - 1, position)本身就是一次比较（调用compare函数的过程就是一次元素大小比较）。

• 当条件成立时，你进入循环体并加了一次比较计数，这部分是对的；
• 当条件不成立时（比如position已经到0，或者前一个元素小于等于当前元素），这次条件判断的比较已经发生了，但你在循环外又额外加了一次计数，这就导致多算了一次。

比如你测试的那个列表，每个元素的处理流程结束后都会多算这一次，最终整体统计就多了1次（刚好对应最后一个元素处理完时的多余计数）。

我给你两种修正方式，都是为了确保每一次实际发生的比较都只被统计一次：

方案1：把比较计数移到while循环内的判断前 #

这种方式更直观，每次调用compare前先计数，确保每一次比较都被记录：

def compare(data, a, b):
    """若索引a的元素大于索引b的元素则返回True"""
    return data[a] > data[b]

def swap(data, a, b):
    """交换索引a和索引b处的元素"""
    data[a], data[b] = data[b], data[a]

def insertion_sort(data):
    """将列表按升序排序"""
    comparison_count = 0
    swap_count = 0
    for index in range(1, len(data)):
        position = index
        while position > 0:
            # 每次调用compare前先统计一次比较
            comparison_count += 1
            if compare(data, position - 1, position):
                swap(data, position - 1, position)
                swap_count += 1
                position -= 1
            else:
                # 不需要交换，直接跳出循环
                break
    print('Length:', len(data), 'Comparisons:', comparison_count, 'Swaps:', swap_count)

# 测试你的示例列表
test_list = [50, 63, 11, 79, 22, 70, 65, 39, 97, 48]
insertion_sort(test_list)

方案2：调整原while结构，去掉循环外的多余计数 #

如果你想保留原来的while条件写法，只需要删掉循环外的comparison_count += 1，同时把循环内的计数移到条件判断后：

def insertion_sort(data):
    """将列表按升序排序"""
    comparison_count = 0
    swap_count = 0
    for index in range(1, len(data)):
        position = index
        while position > 0:
            comparison_count += 1
            # 先统计，再判断是否需要交换
            if not compare(data, position - 1, position):
                break
            swap(data, position - 1, position)
            swap_count += 1
            position -= 1
    print('Length:', len(data), 'Comparisons:', comparison_count, 'Swaps:', swap_count)

比如处理你列表里的11元素：

• 初始position=2，进入while循环：统计一次比较，判断63>11成立，交换后position=1；
• 再次进入while循环：统计一次比较，判断50>11成立，交换后position=0；
• 此时position>0不成立，循环结束，没有额外的计数，这就正确统计了2次比较，没有多余的加1。

这样修改后，你的比较次数统计就会和实际一致了。

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