计数反转算法中的错误

Question

我正在尝试编写一种算法来计算数组中的反转次数。反转是 A[i] > A[j] 和 i < j。def sort_and_count(L):    if len(L)<2:        return 0, L    else:        A = L[:len(L)//2]        B = L[len(L)//2:]        rA, A = sort_and_count(A)        rB, B = sort_and_count(B)        r, L = merge_and_count(A,B)    return r+rB+rA, Ldef merge_and_count(A,B):    i = j = 0    count = 0    L = []    while len(A) > i and len(B) > j:        if A[i] <= B[j]:            L.append(A[i])            i+=1        else:            L.append(B[j])            count = count + (len(A)-1)            j+=1    #copy the remaining elements    for index in range(i,len(A)):        L.append(A[index])    for index in range(j,len(B)):        L.append(B[index])    return count, Lsort_and_count(A)[0]算法不正确。对于这个输入 A = [7, 3, 20, 16, 5, 8] 它返回 6。正确答案是 7 (7, 3),(7, 5),(20, 16),(20, 5) ,(20, 8),(16, 5),(16, 8)。对于某些输入，答案是正确的。我不确定是什么原因造成的。

Answer 1

我希望我知道它给出正确结果的输入是什么。你有一个错字：len(A) - 1应该是len(A) - i。