python - 计算插入排序算法中要排序的元素个数

Question

我认为标题是不言自明的。我正在尝试编写一个程序来计算使用插入排序对列表进行排序所需的交换次数。这就是我所做的:

counts = []
for _ in range(int(input())):
    size = int(input())
    ar = list(map(int, input().split()))
    count = 0
    for i in range(1, len(ar)):
        for j in range(i, 0, -1):
            if ar[j] > ar[i]: count +=1
    counts.append(count)
print(*counts)

但问题是它不起作用。

对于列表 {1 1 1 2 2} 我得到 0 这是正确的但是，

对于列表 {2 1 3 1 2} 我得到 2 这是不正确的答案是 4。

我能知道为什么它不起作用吗？谢谢。

Answer 1

这都是因为 for j in range(i, 0, -1):。 range 不包括右边界，因此您应该:

for j in range(i-1, -1, -1):