在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序数对。一个排列中的逆序的总数就称为这个排列的逆序数。现在给定一个数组，求统计出该数组的逆序数对个数。用C++实现

可以使用归并排序的思想来解决这个问题，在归并排序的过程中统计逆序数对的个数。

具体思路如下：

1.将数组分成左右两部分，分别进行递归调用。

2.在递归到最小子问题时（即只有一个元素），直接返回。

3.在归并的过程中，比较左右两部分的元素大小，并将较小的元素存入临时数组中。若当前左部分元素较大，则逆序数对个数为右部分当前位置到结尾的元素个数。

4.将临时数组中的元素复制回原数组中。

5.返回逆序数对个数。

代码如下：

#include<iostream>
using namespace std;

int merge(int* nums, int left, int mid, int right)
{
    int i = left, j = mid + 1, k = 0;
    int* tmp = new int[right - left + 1];
    int cnt = 0;
    while (i <= mid && j <= right)
    {
        if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
        else
        {
            tmp[k++] = nums[j++];
            cnt += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= right) tmp[k++] = nums[j++];
    for (int p = 0; p < k; p++) nums[left + p] = tmp[p];
    delete[] tmp;
    return cnt;
}

int merge_sort(int* nums, int left, int right)
{
    if (left >= right) return 0;
    int mid = (left + right) / 2;
    int cnt = 0;
    cnt += merge_sort(nums, left, mid);
    cnt += merge_sort(nums, mid + 1, right);
    cnt += merge(nums, left, mid, right);
    return cnt;
}

int main()
{
    int nums[] = { 2, 4, 3, 1, 5, 6 };
    int cnt = merge_sort(nums, 0, 5);
    cout << cnt << endl; // 输出3
    return 0;
}