使用C ++中的合并排序算法实现计数反转

莫斯塔法·穆罕默德(Mostafa Mohamed)

我需要为家庭作业实现计数反转算法,但是我无法弄清楚我的代码中有什么问题。我们的教授要求我们在c ++中实现计数反转(我没有太多使用它)仅C ++库,我可以包含<iostream>stdcout<<并将其仅用于输出(),此而已,他在这里给了我们以下内容:

 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。我希望有人可以指出我的错误在哪里。

al骨

您的基本想法是正确的,但是您的代码中有2个问题。一个是概念性的,另一个是代码中的。

  1. 在合并步骤的else块中,您将反转增加了一个。而是应将其增加左部分的值。因此,在else块中,您应该使用inversion += mid-i;而不是inversion++;因为,您需要实际计算所需的交换次数。此时,对于的值array[j],您mid - i(剩余的左数组)有个实际需要交换的元素数量对应于array[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

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章