排序 求解数组的逆序对

数组中，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

给定一个数组,求出这个数组中的逆序对的总数。

传统思路：

• 每遇到一个数字，遍历其后数字比该数字小的组成一组逆序对，复杂度O(N2)

进阶思路：

• 归并排序中，如果遇到前部分序列的一个值A，比后部分序列一个值B小的
• 说明前部分序列从A开始的每一个数字（因为每部分序列内部是已经升序的），都可以与B组成逆序对
• 
• 前部分序列 3  5  7   后部分序列  4  6  8
• 当归并时访问到前部分序列5和后部分序列4时候
• 由于5比4大 构成(5,4)逆序对  同时5之后元素也必定可以与4构成逆序对

——实现

class Solution {
public:
    int res=0;
    int InversePairs(vector<int> data) {
        if(data.size()==0)
            return 0;
        MergeSort(data,0,data.size()-1);
        return res%1000000007;
        
        
    }
    
    void MergeSort(vector<int>& data,int first,int last)
    {
        if(first<last)
        {
            int mid=(first+last)/2;
            MergeSort(data,first,mid);
            MergeSort(data,mid+1,last);
            MergeArray(data,first,last);
            
        }
    }
    //合并左右 2个有序序列
    void MergeArray(vector<int>& data,int first,int last)
    {
        if(first<last)
        {
            vector<int> temp;//存放排序后序列
            int mid=(first+last)/2;
            int i=first,m=mid;//前部分有序序列  后部分有序序列
            int j=mid+1,n=last;//变量范围
            while(i<=m && j<=n)
            {
                if(data[i]>data[j]) //前部分的数据 大于后部分的一个数据 那么形成逆序
                {
                    temp.push_back(data[j++]);
                    res+=m-i+1;//那么前面部分有 m-i+1个数比data[j]大
                }
                else
                {
                    temp.push_back(data[i++]);
                }
            }
            while(i<=m) //可能剩下元素
            {
                temp.push_back(data[i++]);
            }
            while(j<=n)
            {
                temp.push_back(data[j++]);
            }
            //将结果覆盖到源数组
            for(i=first;i<=last;i++)
            {
                data[i]=temp[i-first];
            }
            
            
            
        }
        
    }
    
    
};