algorithm - 修改归并排序以计算反转次数

Question

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

所以在流行的 CLRS 的“算法简介”一书中有一个问题，要求您修改归并排序以计算数组中的反转数。作者还在这里慷慨地提供了这个问题 2-4 的解决方案，我在下面附上了其截图：

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

我们在这里计算反转：

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

因此计数仅在 时才变为TRUER[j] < L[i]，这也是else以下部分：

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

因此，每当我们R[j] < L[i]复制R[j]并A[k]增加j1 的值时，这确保我们不会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

标签： algorithmmergesortclrsinversion

Answer 1

我想你是正确的。解决方案作者是一位经验丰富的算法专家，但要解决一整本书的练习，某些答案不可避免地会不完美。

为什么不给作者写信？