数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

分析：

对于数组[7，5，6，4],若要计算其中的逆序对个数，及 [7,5],[7,6],[7,4],[5,4],[6,4],可以发现，若将所有逆序对依次交换其在数组中的位置，我们将会得到一个有序的数组，因此，我们可以用排序的思想来解决该题。

归并排序：

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略(分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

归并排序是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的

1.时间复杂度 归并排序算法每次将序列折半分组，共需要logn轮，因此归并排序算法的时间复杂度是O(nlogn)

2.空间复杂度 归并排序算法排序过程中需要额外的一个序列去存储排序后的结果，所占空间是n，因此空间复杂度为O(n)

3.稳定性 归并排序算法在排序过程中，相同元素的前后顺序并没有改变，所以归并排序是一种稳定排序算法

因此要求数组中的逆序对数，只需要计算通过归并排序，将数组中逆序对交换的次数即可。代码如下：

#include<iostream>
using namespace std;
int res = 0;
void MergeSort(int a[], int l,int m,int r)//合并分组进行排序
{
    int t[10100];//辅助数组
    for (int i = l;i <= r;i++)
    {
        t[i - l] = a[i];
    }
    int i = l,j = m + 1;
    for (int k = l;k <= r;k++)
    {
        if (i>m&&j<=r)//i越界而j没有越界
        {
            a[k] = t[j-l];
            res+=(j-m);
            j++;
        }
        else if (i<=m&&j>r)//j越界而i没有越界
        {
            a[k] = t[i-l];
            i++;
        }
        else if (t[i-l]>t[j-l])//i和j进行比较
        {
            a[k] = t[j - l];
            res += (j-m);//计算逆序对
            j++;
        }
        else if (t[i-l]<=t[j-l])//i和j进行比较
        {
            a[k] = t[i - l];
            i++;
        }
    }
}
void Merge(int a[],int l,int r)//递归进行归并排序
{
    if (l >= r)
        return;
    int m = (l + r) / 2;
    Merge(a, l, m);
    Merge(a, m+1, r);
    MergeSort(a, l, m, r);
}
int main()
{
    int n,a[10100];
    cin >> n;
    for (int i = 0;i < n;i++)
    {
        cin>>a[i];
    }
    Merge(a, 0, n-1);
    for (int i = 0;i < n;i++)
    {
        cout << a[i] << " ";
    }
    cout <<endl;
    cout <<"逆序对个数:"<<res<<endl;
    system("pause");
    return 0;
}

力扣 剑指 Offer 51. 数组中的逆序对 题解：

class Solution {
public:
    int mergeSort(vector<int>& nums, vector<int>& tmp, int l, int r) {
        if (l >= r) {
            return 0;
        }
​
        int mid = (l + r) / 2;
        int inv_count = mergeSort(nums, tmp, l, mid) + mergeSort(nums, tmp, mid + 1, r);
        int i = l, j = mid + 1, pos = l;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[pos] = nums[i];
                ++i;
                inv_count += (j - (mid + 1));
            }
            else {
                tmp[pos] = nums[j];
                ++j;
            }
            ++pos;
        }
        for (int k = i; k <= mid; ++k) {
            tmp[pos++] = nums[k];
            inv_count += (j - (mid + 1));
        }
        for (int k = j; k <= r; ++k) {
            tmp[pos++] = nums[k];
        }
        copy(tmp.begin() + l, tmp.begin() + r + 1, nums.begin() + l);
        return inv_count;
    }
​
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> tmp(n);
        return mergeSort(nums, tmp, 0, n - 1);
    }
};