拆分反转的合并排序实现中的错误在哪里

Question

我正在尝试使用 merge sort 对数组中的 number of inversions 进行计数。

想法是合并步骤自然地适用于反转是什么：ith 元素大于 jth 元素。

def merge_and_count(x, y, result, count):
    i, j = 0, 0

    while i < len(x) and j < len(y):
        if x[i] > y[j]:
            result.append(y[j])
            j += 1
            count += 1
        else:
            result.append(x[i])
            i += 1

    result += x[i:]
    result += y[j:]

    return result, count

def sort_and_count(array):
    if len(array) == 1:
        return array, 0

    count = 0
    result = []

    mid = len(array)//2

    x = array[:mid]
    y = array[mid:]

    x, c1 = sort_and_count(x)
    y, c2 = sort_and_count(y)

    result, c3 = merge_and_count(x, y, result, count)

    return result, (c1+c2+c3)

def main():
    array = [1,3,5,2,4,6]
    result, count = sort_and_count(array)
    print("there are", count, "split inversion")
    print(result)

然而这是打印 2 当我的答案应该是 3

Answer 1

您的 merge_and_count 函数中存在错误。应该是：

if x[i] > y[j]:
     result.append(y[j])
     j += 1
     count += len(x) - i # It's not +1 here

当您将 y 中的下一个元素附加到结果时，它会与 x 中尚未添加的所有元素形成反转。正好有 len(x) - i 个这样的元素。

拆分反转的合并排序实现中的错误在哪里

Where is the bug in this merge sort implementation of split inversions

algorithm

mergesort