python - 计算归并排序的反转

Question

我已经实现了一个可以正常工作的归并排序函数，但是，我很难修改它以在排序之前计算原始数组中的反转次数。

反转是一对，其中i < j but a[i] > a[j]一个例子，a = [5,2,1]有 3 个反转:(5,2),(5,1),(2,1)

def mergeSort(a):

    mid = len(a)//2

    if len(a) < 2:
        return

    l = a[:mid]
    r = a[mid:]
    mergeSort(l)
    mergeSort(r)

    return merge(l,r,a)

def merge(l,r,a):
    i = 0
    j = 0
    k = 0

    inv = 0

    while(i < len(l) and j < len(r)):
        if(l[i] < r[j]):
           a[k] = l[i]
           i = i + 1
        else:
            a[k] = r[j]
            inv = inv + 1
            j = j + 1
        k = k + 1

    while i < len(l):
        a[k] = l[i]
        i = i + 1
        k = k + 1
    while j < len(r):
       a[k] = r[j]
       j = j + 1
       k = k + 1
       inv = inv + 1
    return [a,inv]

a = [6,5,4,3,2,1]
print(mergeSort(a))

上面的例子应该返回 15 作为倒置计数，因为 n(n-1)/2 是降序数组的倒置次数。

有人可以解释一下如何计算吗？

Answer 1

L[i] > R[j]是一次反转，但请注意，由于数组已排序，如果 L[k] > R[j]对于一些 k , 这意味着 L[k] > R[j] for all i <= k < |L| .所以你可以减去数组的长度L来自 i为您提供反转的总数。