C++归并排序Merge Sort怎么计算数组逆序对数量-C++-PHP中文网

归并排序中统计逆序对的关键是在merge时，当arr[i] > arr[j]，累加mid - i + 1个逆序对；需用临时数组合并、递归累加左右子区间结果，并注意下标边界与long long防溢出。

c++归并排序merge sort怎么计算数组逆序对数量

归并排序过程中怎么顺便数逆序对

归并排序天然适合统计逆序对，因为每次 merge 时，左半段和右半段各自已有序，一旦发现 left[i] > right[j]，说明 left[i] 及其后面所有元素（共 mid - i + 1 个）都大于 right[j]，这正是逆序对的批量来源。

关键不是“额外加一层循环去检查”，而是把计数逻辑嵌进 merge 的比较分支里。

常见错误是只在 left[i] > right[j] 时加 1，漏掉整个左段剩余部分；或者把计数放在错误位置（比如 merge 前递归调用后），导致重复或遗漏。

必须在 right[j] 被写入临时数组前，累加 mid - i + 1
递归调用要分别获取左右子区间的逆序对数量，再加本次 merge 新产生的
原数组不能直接修改后再计数——得用临时数组合并，否则破坏有序性影响后续判断

C++ 实现中要注意的参数和边界

标准归并排序的 mergeSort(arr, l, r) 签名没问题，但计数函数最好返回 long long，避免大量逆序对时溢出（比如 n = 1e5 时最多约 5e9 对）。

merge 函数需接收原数组、左右边界、以及一个临时缓冲区（推荐传入 vector<int>& temp</int> 避免反复构造）。

容易错的下标：假设当前处理 [l, r]，中点是 mid = l + (r - l) / 2，那么左段是 [l, mid]，右段是 [mid + 1, r]。计数时，当 arr[i] > arr[j]，左段剩余个数是 mid - i + 1，不是 r - i + 1。

示例片段：

long long merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) {
    int i = l, j = mid + 1, k = l;
    long long inv_count = 0;
<pre class="brush:php;toolbar:false;">while (i <= mid && j <= r) {
    if (arr[i] <= arr[j]) {
        temp[k++] = arr[i++];
    } else {
        temp[k++] = arr[j++];
        inv_count += (mid - i + 1); // 关键：左段从 i 到 mid 都构成逆序
    }
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];

for (i = l; i <= r; ++i) arr[i] = temp[i];
return inv_count;

}