python - 如何计算插入排序中交换的数量？

Question

我正在尝试计算插入排序进行交换或对数组中的值进行排序的次数。我应该在哪里增加交换计数？

这是在 Python 3 上进行的，我测试了几种缩进，但似乎都不起作用。此外，我在各种网站上寻找答案，包括堆栈溢出，但无济于事。

def insertionsort(array):
    swapsmade = 0
    checksmade = 0
    for f in range(len(array)):
        value = array[f]
        valueindex = f
        checksmade += 1
        # moving the value
        while valueindex > 0 and value < array[valueindex-1]:
            array[valueindex] = array[valueindex-1]
            valueindex -= 1
            checksmade += 1
        swapsmade += 1 #  FIX THIS
        array[valueindex] = value
    print(array)
    swapsnchecks = "{} swaps were made. {} checks were made.".format(swapsmade, checksmade)
    return swapsnchecks

当我使用带有十个整数的排序列表(即 [1, 2, 3, 4, 5, 6, 7, 8, 9 ，10])。我预计输出为 0 swaps were made。进行了 55 次检查。，但输出最终为 10 swaps were made。进行了 55 次检查。

Answer 1

您只需在 while 循环内缩进计数器，如下所示:

def insertionsort(array):
    swapsmade = 0
    checksmade = 0
    for f in range(len(array)):
        value = array[f]
        valueindex = f
        checksmade += 1
        # moving the value
        while valueindex > 0 and value < array[valueindex-1]:
            array[valueindex] = array[valueindex-1]
            valueindex -= 1
            checksmade += 1
            swapsmade += 1 #  Move inside the while loop
        array[valueindex] = value
    print(array)
    swapsnchecks = "{} swaps were made. {} checks were made.".format(swapsmade, checksmade)
    return swapsnchecks

例如:

print(insertionsort([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]))
print(insertionsort([2, 1, 3, 4, 5, 6, 7, 8, 9, 10]))
print(insertionsort([10, 9, 8, 7, 6, 5, 4, 3, 2, 1]))

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
0 swaps were made. 10 checks were made.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
1 swaps were made. 11 checks were made
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
45 swaps were made. 55 checks were made.