修改合并排序以计算反转次数

Question

请先阅读此内容，然后再急于将其标记为重复！ - 这与实际修改无关，这是关于检查是否计算了特定的反转。

所以流行的CLRS算法导论书里有这个问题，要求你修改归并排序来计算数组的倒置次数。作者还慷慨地提供了这个问题2-4的解决方案here，我附上了下面的截图：

我的问题：在第二张截图中，作者使用了一个布尔值 counted = FALSE 来检查反转是否对应于特定 R[j] 的某个值 [=15] =] 是否已经计算过。因此我很困惑，因为我认为它是多余的。

我们在这里算倒数：

    if counted == FALSE and R[j] < L[i]   
        inversions = inversions + n1 - i + 1
        counted = TRUE

仅当 R[j] < L[i] 时，如此计算才变为 TRUE，这也是下面的 else 部分：

    ...
    else
        A[k] = R[j]
        j = j + 1
        counted = FALSE

所以每当我们有 R[j] < L[i] 时，我们将 R[j] 复制到 A[k] 并将 j 的值增加 1，这确保我们永远不会遇到之前的 R[j] 再次循环。在我看来，这使得 counted 布尔值变得多余。

或者还有更多内容？如果我们删除 counted 布尔值，是否有任何特定示例会中断：

    // my suggestion
    ...
    for k = p to r
        if R[j] < L[i]
            inversions = inversions + n1 - i + 1
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else A[k] = R[j]
            j = j + 1

Answer 1

我认为你是对的。解答作者是一位经验丰富的算法专家，但要解决一整本书的练习，一些答案是不可避免的。

你为什么不给作者写信？

修改合并排序以计算反转次数

Modifying merge sort to count the number of inversions

algorithm

mergesort

inversion

clrs