希尔排序(Shell Sort)实现比较次数计数位置及正确性确认问题

现有代码的计数逻辑问题 #

• 漏记第一处比较操作：if arr[i] > arr[j] 这一步的元素大小比较没有被计入总次数
• 内层回溯比较的计数位置语义不清晰：原代码把计数放在if判断外、内层循环末尾，虽然当前逻辑下计数结果和实际比较次数一致，但和比较操作没有绑定，后续修改代码很容易出现计数错位问题

正确修改方案 #

直接在每一次执行元素大小比较的操作前加计数即可，修正后的代码如下：

def shell_sort(arr):
    mid = len(arr) // 2
    number_of_comparings = 0
    while mid > 0:
        i = 0
        j = mid
        while j < len(arr):
            # 统计第一处元素比较的次数
            number_of_comparings += 1
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j += 1
            k = i
            while k - mid > -1:
                # 统计第二处回溯元素比较的次数，删除原循环末尾的计数语句
                number_of_comparings += 1
                if arr[k - mid] > arr[k]:
                    arr[k-mid], arr[k] = arr[k], arr[k-mid]
                k -= 1
        mid //= 2
    print(number_of_comparings)
    return arr

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