用C++归并算法实现对序列逆序对个数的计算

归并算法求逆序对的思路如下：

1. 将原序列递归地二分成左右两个子序列，对左右两个子序列分别计算逆序对个数；

2. 对左右两个子序列进行归并排序，同时统计左右两个子序列之间的逆序对个数；

3. 将排序后的左右两个子序列合并成一个有序序列，最终得到整个序列的逆序对个数。

具体实现如下：

#include <iostream>
#include <vector>

using namespace std;

long long merge(vector<int>& nums, int left, int mid, int right) {
    int i = left, j = mid + 1;
    long long count = 0;
    vector<int> temp;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp.push_back(nums[i++]);
        } else {
            count += mid - i + 1; // 统计逆序对个数
            temp.push_back(nums[j++]);
        }
    }
    while (i <= mid) temp.push_back(nums[i++]);
    while (j <= right) temp.push_back(nums[j++]);
    for (int k = 0; k < temp.size(); k++) {
        nums[left + k] = temp[k];
    }
    return count;
}

long long mergeSort(vector<int>& nums, int left, int right) {
    long long count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        count += mergeSort(nums, left, mid);
        count += mergeSort(nums, mid + 1, right);
        count += merge(nums, left, mid, right);
    }
    return count;
}

int main() {
    vector<int> nums = {7, 5, 6, 4};
    cout << mergeSort(nums, 0, nums.size() - 1) << endl; // 5
    return 0;
}

以上代码中，merge() 函数实现了对左右子序列的归并排序，并统计左右两个子序列之间的逆序对个数。mergeSort() 函数实现了归并排序的递归调用，并返回整个序列的逆序对个数。main() 函数中给出了一个样例，输出结果为 5。