在c++中用合并排序算法实现计数反演

Question

我需要为家庭作业实现计数反转算法，但我不知道我的code.Our教授要求我们在不使用任何C++库的情况下在c++中实现计数反转(我不经常使用它)，我只能包含<iostream>，并且只为输出(cout<<)使用std --仅此而已，他还在这里给了我们这篇文章：

 void count_inversion(int a[],int n){
    count_inversion(a, n / 2);
    count_inversion(a + (n / 2), n / 2);
    count_inversion_merge(a, n / 2, n);
  }

并表示我们应该实现count_inversion_merge函数，并将此部分用作提示。所以我试着把代码稍微修改一下，但还是没有运气。

这是我的代码：

 int count_inversion_merge(int array[], int mid, int n) {
        for (k = 0; k < n; k++) {
            if (j == n || (i < mid && array[i] < array[j])) {
                b[k] = array[i];
                i++;
            } else {
                b[k] = array[j];
                j++;
                inversion++;
            }
        }

    }

我的第一个输入int a[] ={ 2, 4, 1, 3, 5 };应该返回3，但是它返回5，我的第二个输出应该是5，我得到5，我希望有人能指出我的错误在哪里。

Answer 1

您的基本想法是正确的，但是代码中有两个问题。一个是概念性的，另一个是代码方面的。

1. 在合并步骤的其他块中，您将反转量增加1。相反，您应该通过左边部分的值来增加它。因此，在其他块中，您应该使用inversion += mid-i;而不是inversion++;，因为您需要实际计算所需的掉期数量。此时，对于array[j]的值，您有mid - i (左数组的其余部分)元素的数量，这些元素实际上需要交换对应于array[j]的元素。这意味着，如果要使用冒泡排序，则需要将左数组(mid-i)中的所有其余元素交换为单个值(array[j])。因此，对于这个array[j]，您应该增加左侧子数组中rest元素的数量。
2. 在count_inversion的递归调用中，每次调用中都缺少一些值。让我们说n=5。然后在左边使用5/2 = 2，在右边使用5/2 = 2。但是你错过了右边的最后一个元素。您可以在第二个递归调用中使用如下方法来解决这个问题。在这里，您应该使用第一次调用时所用长度的其余部分。 count_inversion(a + (n / 2), n - n / 2);

用补丁从您的代码中修改一下：https://ideone.com/raKD7T