C++归并排序统计数组交换次数与预期逆序数不符的问题排查
归并排序计数结果不符预期的排查与修复
核心错配
首先明确两个概念的本质差异:
- 你当前代码的
count统计的是归并过程中临时数组向原数组写入元素的次数 - 测试用例给出的预期值是数组的逆序数(即所有满足下标i<j、且arr[i]>arr[j]的元素对总数量)
两者统计规则完全独立,这是结果不符合预期的根本原因。
现存代码的问题
- 计数逻辑完全错位:你在双指针归并的每次赋值操作后都执行
count++,完全没有对应逆序对的计数规则 - 漏计了批量逆序对的数量:归并合并两个有序子数组时,一旦出现
R[j] < L[i]的情况,L数组中从i位置到末尾的所有元素都比当前R[j]大,这些元素会全部和R[j]构成逆序对,这部分数量必须统一累加,而不是按单次赋值计数 - 未考虑计数重置:全局变量
count没有在每次排序前重置为0,多次测试不同数组时会出现计数叠加的问题
正确的计数实现
归并过程的计数仅需要修改双指针循环的逻辑,不需要改动排序本身的流程:
- 当
L[i] <= R[j]时,直接将L[i]写入原数组,不存在新的逆序对,不执行计数操作 - 当
L[i] > R[j]时,将R[j]写入原数组,此时需要将n1 - i(即L数组中剩余未合并的元素总数)累加到count中 - 两个子数组剩余元素的顺序拷贝环节,不存在新的跨子数组逆序对,完全不需要涉及计数
修复后的核心代码段
// indexes initialization int i = 0; int j = 0; int k = l; // merges the subarrays while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; // 累加当前R[j]对应的所有逆序对数量 count += n1 - i; j++; } k++; }
另外需要在main函数调用mergeSort之前,增加一行count = 0;重置全局计数器,避免多次测试时计数叠加。
验证效果
按照上述逻辑修改后,你给出的两个测试用例的输出结果会和预期值65、33完全匹配。
内容的提问来源于stack exchange,提问作者CaptainBo
相关产品推荐
相关产品推荐

