快速排序中插入排序的比较次数计数错误问题求助

先给你指出代码里的几个核心问题：

• 比较计数逻辑完全错误：你在while循环里比较array[j-1] > array[j]，这根本不是插入排序的核心比较操作，插入排序每次是拿array[j]和key比，而且当j=p时，j-1会触发数组越界。
• 数组操作逻辑错误：循环结束后的交换和赋值步骤混乱，array[j-1], array[j]的交换完全多余，还会导致数组越界（比如j=p-1时）。
• 额外的错误计数：循环末尾的count +=1没有依据，属于无意义的累加。

下面是修正后的代码，同时正确统计比较次数：

def insertion_sort(array, p, r, count):
    for i in range(p+1, r+1):
        key = array[i]
        j = i - 1
        # 每次对array[j]和key的判断都是一次比较，在这里计数
        while j >= p:
            count += 1
            if array[j] > key:
                array[j+1] = array[j]
                j -= 1
            else:
                break
        array[j+1] = key
    return array, count

关键说明： #

1. 插入排序的比较操作就是每次将当前元素key和前面的有序元素逐一比较，所以每次执行array[j] > key的判断时，都要计数一次，不管结果是True还是False。
2. 原代码里的交换步骤是错的，正确的做法是当array[j] > key时，把array[j]后移一位，直到找到key应该插入的位置j+1，最后完成赋值。
3. 不需要额外的末尾计数，所有比较都在while循环的判断逻辑里完成。

你可以用小数组（比如[3,1,2]，p=0，r=2）手动计算比较次数，再和代码返回的count对比，就能验证正确性了。

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