归并排序求逆序对数c++

归并排序是一种经典的排序算法，可以求解逆序对数。以下是使用C++实现归并排序并计算逆序对数的示例代码：

#include <iostream>
#include <vector>

using namespace std;

// 归并排序
long long mergeSort(vector<int>& nums, int left, int right, vector<int>& temp) {
    if (left >= right) {
        return 0;
    }

    int mid = left + (right - left) / 2;
    long long count = mergeSort(nums, left, mid, temp) + mergeSort(nums, mid + 1, right, temp);

    int i = left, j = mid + 1, pos = left;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[pos++] = nums[i++];
        } else {
            temp[pos++] = nums[j++];
            count += mid - i + 1;  // 统计逆序对数
        }
    }

    while (i <= mid) {
        temp[pos++] = nums[i++];
    }
    while (j <= right) {
        temp[pos++] = nums[j++];
    }

    for (int k = left; k <= right; k++) {
        nums[k] = temp[k];
    }

    return count;
}

long long countReversePairs(vector<int>& nums) {
    int n = nums.size();
    vector<int> temp(n);
    return mergeSort(nums, 0, n - 1, temp);
}

int main() {
    vector<int> nums = {7, 5, 6, 4};
    long long count = countReversePairs(nums);
    cout << "逆序对数：" << count << endl;
    return 0;
}

以上代码中，`mergeSort`函数用于进行归并排序，并返回逆序对数。在归并的过程中，通过统计左右两个子数组中的逆序对数，即可得到整个数组的逆序对数。`countReversePairs`函数调用`mergeSort`函数，并返回最终的逆序对数。

运行以上代码，将输出逆序对数为3。