思路：归并排序
每次把数组从中间拆分成两部分，先统计拆分数组内部的逆序对，再把这个数组排序，防止统计重复，最后再把拆分的数组合并，并统计合并过程中的逆序对。
Paste_Image.png
Paste_Image.png
public int InversePairs(int [] array) {
if(array==null||array.length==0)
return 0;
int[] copy = new int[array.length];
for (int i = 0; i < copy.length; i++) {
copy[i] = array[i];
}
int count = InversePairsHelper(array, copy, 0, array.length - 1);
return count;
}
public int InversePairsHelper(int [] array,int [] copy,int start,int end) {
if(start==end){
copy[end]=array[end];
return 0;
}
int len=(end-start)/2;//
int left=InversePairsHelper(array,copy,start,start+len);
int right=InversePairsHelper(array,copy,start+len+1,end);
int i=start+len;
int j=end;
int indexofCopy=end;
while(i>=start&&j>start+len+1){
if(array[i]>array[j]){
copy[indexofCopy--]=array[i--];
count+=j-start-len;
}else{
copy[indexofCopy--]=array[j--];
}
}
for(;i>=start;i--){
copy[indexofCopy--]=array[i--];
}
for(;j>=start+len+1;j--){
copy[indexofCopy--]=array[i--];
}
return left+right+count;
}
