在c++中用合并排序算法实现计数反演
在c++中用合并排序算法实现计数反演
提问于 2017-11-15 02:40:23
我需要为家庭作业实现计数反转算法，但我不知道我的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，我希望有人能指出我的错误在哪里。
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-11-15 04:41:37
您的基本想法是正确的，但是代码中有两个问题。一个是概念性的，另一个是代码方面的。
- 在合并步骤的其他块中，您将反转量增加1。相反，您应该通过左边部分的值来增加它。因此，在其他块中，您应该使用
inversion += mid-i;而不是inversion++;，因为您需要实际计算所需的掉期数量。此时，对于array[j]的值，您有mid - i(左数组的其余部分)元素的数量，这些元素实际上需要交换对应于array[j]的元素。这意味着，如果要使用冒泡排序，则需要将左数组(mid-i)中的所有其余元素交换为单个值(array[j])。因此，对于这个array[j]，您应该增加左侧子数组中rest元素的数量。 - 在
count_inversion的递归调用中，每次调用中都缺少一些值。让我们说n=5。然后在左边使用5/2 = 2，在右边使用5/2 = 2。但是你错过了右边的最后一个元素。您可以在第二个递归调用中使用如下方法来解决这个问题。在这里，您应该使用第一次调用时所用长度的其余部分。count_inversion(a + (n / 2), n - n / 2);
用补丁从您的代码中修改一下：https://ideone.com/raKD7T
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/47305234
复制相关文章
相似问题
社区富文本编辑器全新改版！诚邀体验～
全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验
腾讯云开发者
