You need to enable JavaScript to run this app. C++归并排序统计数组交换次数与预期逆序数不符的问题排查
优惠活动
大模型
产品
解决方案
定价
更多

C++归并排序统计数组交换次数与预期逆序数不符的问题排查

归并排序计数结果不符预期的排查与修复

核心错配

首先明确两个概念的本质差异:

  • 你当前代码的count统计的是归并过程中临时数组向原数组写入元素的次数
  • 测试用例给出的预期值是数组的逆序数(即所有满足下标i<j、且arr[i]>arr[j]的元素对总数量)
    两者统计规则完全独立,这是结果不符合预期的根本原因。

现存代码的问题

  • 计数逻辑完全错位:你在双指针归并的每次赋值操作后都执行count++,完全没有对应逆序对的计数规则
  • 漏计了批量逆序对的数量:归并合并两个有序子数组时,一旦出现R[j] < L[i]的情况,L数组中从i位置到末尾的所有元素都比当前R[j]大,这些元素会全部和R[j]构成逆序对,这部分数量必须统一累加,而不是按单次赋值计数
  • 未考虑计数重置:全局变量count没有在每次排序前重置为0,多次测试不同数组时会出现计数叠加的问题

正确的计数实现

归并过程的计数仅需要修改双指针循环的逻辑,不需要改动排序本身的流程:

  1. 当L[i] <= R[j]时,直接将L[i]写入原数组,不存在新的逆序对,不执行计数操作
  2. 当L[i] > R[j]时,将R[j]写入原数组,此时需要将n1 - i(即L数组中剩余未合并的元素总数)累加到count中
  3. 两个子数组剩余元素的顺序拷贝环节,不存在新的跨子数组逆序对,完全不需要涉及计数

修复后的核心代码段

// 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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.16 11:45:03