Python插入排序实现：比较与交换次数统计异常排查

首先明确：你给出的代码里，交换次数的统计逻辑本身是正确的——每次执行相邻元素交换后，swaps +=1的位置没问题，会准确统计每一次交换操作。你遇到交换次数始终为0的情况，大概率是以下两种原因：

1. 测试列表本身是升序排列 #

插入排序在处理完全有序的列表时，不会触发任何交换操作，交换次数自然为0。比如测试insertion_sort([1,2,3,4])，返回的交换次数就是0，这是算法的正常表现，不是代码bug。

2. 接收返回值时顺序错误 #

函数返回的元组顺序是(排序后的列表, 比较次数, 交换次数)，如果你在接收时搞反了位置，比如写成：

sorted_lyst, swaps, comps = insertion_sort([3,1,2])

就会把比较次数当成交换次数；而如果测试的是有序列表，交换次数本身就是0，会让你误以为所有场景下交换次数都为0。正确的接收方式应该是：

sorted_lyst, comps, swaps = insertion_sort([3,1,2])

另外，你认为正确的比较次数统计其实是错误的：当前代码只在每个for循环末尾加1，但实际上while循环的条件判断每执行一次就是一次比较。比如处理[3,2,1]时，while循环会执行3次比较，但你的代码会统计comparisons=2，明显不符合实际。

修正后的完整代码 #

下面是同时修复比较次数统计，并保留正确交换次数统计的代码：

def insertion_sort(lyst):
    """
    该函数实现插入排序算法对列表元素进行排序。
    返回一个元组，包含排序后的列表、比较次数、交换次数。
    输入必须是包含可比较元素的Python列表，否则抛出TypeError异常。

    :param lyst: 待排序的整数列表
    :return: 元组(排序后的列表, 比较次数, 交换次数)
    """

    if not isinstance(lyst, list) or not all(isinstance(x, int) for x in lyst):
        raise TypeError("lyst必须是包含可比较元素的列表。")

    comparisons = 0
    swaps = 0

    for i in range(1, len(lyst)):
        j = i
        while j > 0:
            comparisons += 1  # 每次条件判断都算一次比较
            if lyst[j] < lyst[j - 1]:
                lyst[j], lyst[j - 1] = lyst[j - 1], lyst[j]
                swaps += 1
                j -= 1
            else:
                break

    return lyst, comparisons, swaps

测试验证 #

• 测试无序列表：insertion_sort([3,2,1])会返回([1,2,3], 3, 3)，比较次数3次，交换次数3次，符合预期。
• 测试有序列表：insertion_sort([1,2,3])返回([1,2,3], 2, 0)，交换次数为0，属于正常情况。

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