方法一：暴力（超时）

1.解题思路

题意： 前一个数字比后一个大称为一个逆序对，这里要对给定数列找出逆序对的数量。 分析： 其实也就是线性代数中的逆序数。我们可以先尝试用暴力遍历查找方式来解决。

2.解法

暴力，两层循环，先遍历数组中每一个元素，接着在该元素后查找比它小的数的个数。

3.具体代码

class Solution {
public:
    int InversePairs(vector<int> data) {
        int ans=0;
        for(int i=0;i<data.size();i++){//遍历到一个元素 
        	for(int j=i+1;j<data.size();j++){//接着遍历该元素后面的所有元素，查找比它小的元素个数 
        		if(data[i]>data[j]){
        			ans++;
        			ans%=1000000007; 
				}
			}
		}
		return ans; 
    }
};

4.时间复杂度和空间复杂度分析

时间复杂度：$O(n^2)O(n^2)$，n是给定序列的元素个数，两层循环遍历数组，所以这里是$O(n^2)O(n^2)$。 空间复杂度：$O(1)O(1)$，只用到了一个整形变量ans用于计数。

方法二：归并

1.解题思路

因为统计逆序对就是对于数值大的在前，数值小的在后的这样一对数的数目统计。可使用归并排序来比较两数大小，如归并段$A[i]A[i]$>归并段$B[j]B[j]$，按从小到大排列，$B[j]B[j]$先加入temp，$A[i]A[i]$加入temp数组后会在$B[j]B[j]$后，这样就是一个逆序对。因为归并段内是有序的，易知$A[i]A[i]$以后的所有元素也都比$B[j]B[j]$大，加入temp数组后也都在$B[j]B[j]$后，所以本次统计逆序对个数为$A[i]A[i]$及以后的所有数。

2.解法

归并排序步骤 划分：将待排序区间$[left,right][left,right]$，按照$mid=(left+right)\mathrm{/}2mid=(left+right)/2$，划分成两段$[left,mid][left,mid]$，$[mid+1,right][mid+1,right]$。 合并：对$[left,mid][left,mid]$，$[mid+1,right][mid+1,right]$使用递归排序，并合并成新的有序序列。

在基础归并排序的基础上，统计上述归并段A[i]>归并段B[j]时，A[i]及以后的所有数的个数即可。

3.图解

4.具体代码

class Solution {
public:
	int merge_sort(vector<int>&a,vector<int>&temp,int l,int r){
		if(l>=r)return 0;//递归边界 
		int mid=l+r>>1;//划分 
		int ans=merge_sort(a,temp,l,mid)+merge_sort(a,temp,mid+1,r);
		ans %= 1000000007;
		int cn=0,i=l,j=mid+1;//合并 
		while(i<=mid&&j<=r){//两路归并排序并用temp数组暂存 
			if(a[i]<=a[j])temp[cn++]=a[i++];
			else{
				temp[cn++]=a[j++];
				ans+=mid-i+1;//统计逆序对，此时a[i]>a[j],即a[i]~a[mid]都>a[j],i~mid排好的数和j都能构成逆序对,数量为mid-i+1 
			}
		}	
		while(i<=mid)temp[cn++]=a[i++];//所分两路分别有序，如有剩余，直接加到temp数组后面 
		while(j<=r)temp[cn++]=a[j++];
		ans %= 1000000007;
		for(int i=l,j=0;i<=r;i++,j++){//temp数组的写回 
			a[i]=temp[j];
		}
		return ans;
	} 
    int InversePairs(vector<int> data) {
    	vector<int>temp(data.size(),0);
        return merge_sort(data,temp,0,data.size()-1);
    }
};

5.时间复杂度和空间复杂度分析

时间复杂度：$O(n{}_{2}n)O(n\backslash log\_\{2\}\{n\}\; )$，n为序列元素个数,归并排序的时间复杂度，递归树高${}_{2}n\backslash log\_\{2\}\{n\}$（即归并趟数），每层共计n个数组元素，所以总的时间复杂度$O(n{}_{2}n)O(n\backslash log\_\{2\}\{n\}\; )$。 空间复杂度：$O(n)O(n)$，只用到了长度为n的辅助数组temp。