c++ - 在c++中使用归并排序算法实现计数倒置

Question

我需要为家庭作业实现计数倒置算法，但我无法弄清楚我的代码中的问题是什么。我们的教授要求我们在 C++ 中实现计数倒置算法(我没有用它太多)在不使用任何 C++ 库的情况下，我可以包含 <iostream>并仅将 std 用于输出(cout<<)，仅此而已，他也在这里给了我们这篇文章:

 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. 在合并步骤的 else block 中，您将反转增加 1。相反，您应该根据左侧部分的值来增加它。因此，在 else block 中，您应该使用 inversion += mid-i; 而不是 inversion++; 因为，您需要实际计算所需的交换次数。此时，对于 array[j] 的值，您有 mid - i(左侧数组的其余部分)实际需要交换的元素数对应于 数组[j]。这意味着，如果您要使用冒泡排序，则需要将左数组 (mid-i) 中的所有其余元素与该单个值 (array[j]) 交换).因此，对于此 array[j]，您应该增加左侧子数组中剩余的元素数量。

2. 在 count_inversion 的递归调用中，您在每次调用中都遗漏了一些值。例如让我们说 n=5。然后，您在左侧使用 5/2 = 2，在右侧使用 5/2 = 2。但是您缺少右侧的最后一个元素。您可以通过在第二次递归调用中使用以下方法来解决它。在这里，您应该使用第一次调用时使用的剩余长度。

   count_inversion(a + (n/2), n - n/2);

对您的代码进行了一些修改，并进行了修复:https://ideone.com/raKD7T