对mergesort python中的倒数进行计数

Question

在使用mergesort对列表进行排序时，我想要计算列表中有多少个反转。到目前为止，这是我的代码，其中'x‘计算倒数的数量，而其余的对其进行排序：

import sys
x = 0

def merge_sort(A):
    merge_sort2(A, 0, len(A) - 1)


def merge_sort2(A, first, last):
    if first < last:
        middle = (first + last) // 2
        merge_sort2(A, first, middle)
        merge_sort2(A, middle + 1, last)
        merge(A, first, middle, last)


def merge(A, first, middle, last):
    global x
    L = A[first:middle + 1]
    R = A[middle + 1:last + 1]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = j = 0

    for k in range(first, last + 1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            x += 1
            x += len(L[first + 1:])

当我使用列表调用合并排序时，支持变量x来给出列表中的反转次数。因此，如果列表是'4,3,2,1，x就是6。如果列表是1,2,3 x就是0。当合并定义中的右边大于左边时，我改变了x的值，但是这个数字总是太大了。我做错了什么？

Answer 1

检查我的工作，但我认为，而不是：

x += 1
x += len(L[first + 1:])

您需要：

x += middle + 1 + j - k

基本上，你想要添加项目k实际来自哪里和如果所有东西都已经排序了，你希望它来自哪里之间的差异。

Answer 2

你的合并步骤对我来说有点难理解--我不确定你为什么要这样做(也许只是另一种合并的方式？)：

L.append(sys.maxsize)
R.append(sys.maxsize)

但添加到分区中的额外元素并不能解决所有问题。我认为，每次从R进行合并移动时，您都会将L中的额外元素计数为一个反转

我认为这是造成一些问题的原因。但是你还有另外两个问题：

你的最后一行逻辑不太正确：

 x += len(L[first + 1:])

反转的数量将是您在L中跳过的元素的数量。您每次都要计算L的几乎每一个元素。下面这样的代码效果更好：

x += len(L[i:]) 

然后在最后，你可能会留下一些元素，你还没有计算它们的反转。也许这不是额外元素的问题，但在更传统的合并中，这是一个问题。下面是我计算倒数的方法：

def merge(A, first, middle, last):
    global x
    L = A[first:middle+1]
    R = A[middle+1:last+1]
    i = j = 0
    k = first
    print(L, R)
    while i<len(L) and j<len(R):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            # count how many left in L 
            x += len(L[i:]) 
        k += 1
    # take care of any leftovers in L or R
    while i < len(L):
        A[k] = L[i]
        i += 1
        k+=1
    while j < len(R):
        A[k] = R[j]
        j += 1
        k+=1
        x += len(L[i:])