合并倒数计数

Question

我实现了一个mergesort函数，它可以正常工作，但是，在排序之前，我很难修改它来计算原始数组中的倒数。在

反转是一对，其中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|。所以你可以从i中减去数组L的长度，得到反转的总数。在