python - 计算反转次数

Question

我想建立分而治之的算法，它计算了一些倒置。这是我的代码，它基于合并排序：

def merge_sort(array):
    if len(array)<=1:
        return array

    mid = len(array)//2

    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])
    res = merge(left_array,right_array)

    return res


def merge(left_array, right_array): 
    global inversions
    inversions = 0
    result = []
    i = j = 0


    while i < len(left_array) and j < len(right_array):
        if left_array[i] <= right_array[j]:
            result.append(left_array[i])
            i+=1


        else:
            result.append(right_array[j])
            inversions += len(left_array[i:])
            print(right_array[j],left_array[i])
            j +=1


    result.extend(left_array[i:])
    result.extend(right_array[j:])
    return result


test = [5 ,2 ,10 ,8 ,1 ,9 ,4 ,3 ,6 ,7]

#test = [1,3,5,2,4,6]

merge_sort(test)
inversions

就我而言，我得到了 11，但应该是 22。

例如，我们有一个数组 [1,3,5,2,4,6]。通过分而治之的方法（合并排序），我们将此数组分为两部分。在第一步中，我们选择元素 1 作为最小的元素，将其插入新数组并从左侧数组中删除。在第二步中，最小元素是 2（右数组）。在这里我们看到，在左边的数组中有 2 个元素。这意味着，我们有 2 个反转，其中涉及元素 2。主要思想是，如果我们从右侧选择一个元素，则反转数 = 左侧数组中左侧的元素数。

我试图在代码中实现这个逻辑，但它不能正常工作。你能帮我找出我的错误吗？

标签： pythonalgorithm