算法2

(归并) $O(nlogn)$

n^2只能就优化为nlogn归并，分区间，然后区间内的逆序对可以用归并算出来，然后将跨越区间的数算出来

时间复杂度

参考文献

java 代码

class Solution {
    int count = 0;
    public int inversePairs(int[] nums) {
         meger(nums,0,nums.length-1);
         return count;
    }
    public void meger(int[] q,int l,int r){
        //基线条件
        if(r-l<1) return;
        int m = l+r>>1;
        meger(q,l,m);
        meger(q,m+1,r);
        //归并
        int i = l;
        int j = m+1;
        int t = 0;
        int temp[] = new int[r-l+1];
        while(i<=m&&j<=r){
            if(q[i]>q[j])
            {
                count+=m-i+1;
                temp[t++]=q[j++];
            }
            else
            {
                temp[t++]=q[i++];
            }
        }
        while(i<=m) temp[t++]=q[i++];
        while(j<=r) temp[t++]=q[j++];
        //将temp复制到q中
        for(int g=0,h=l;g<r-l+1;g++,h++) q[h]=temp[g];
    }
}