计算归并排序的反转

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))

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

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

Answer 1

L[i] > R[j] 是一个单一的反转，但请注意，由于数组是排序的，如果 L[k] > R[j] 对于某些 k，这意味着 L[k] > R[j] for all i <= k < |L|。所以你可以从 i 中减去数组的长度 L 得到反转的总数。

计算归并排序的反转

counting inversions of mergesort

python

algorithm

mergesort