【题目】在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
* 【思路】运用归并排序的思想。
* 首先将数组分成两个子数组，统计子数组的逆序对；
* 再合并，统计整个的逆序对。
package com.exe11.offer; /**
* 【题目】在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
* 【思路】运用归并排序的思想。
* 首先将数组分成两个子数组，统计子数组的逆序对；
* 再合并，统计整个的逆序对。
* @author WGS
*
*/
public class InversePairsCount {
public int InversePairs(int[] data){
if(data==null ||data.length<=0)
return 0;
int[] copy=new int[data.length];
for(int i=0;i<data.length;i++){
copy[i]=data[i];
}
int count=InversePairsCountCore(data,copy,0,data.length-1);
return count;
} private int InversePairsCountCore(int[] data, int[] copy, int start, int end) {
if(start==end){
copy[start]=data[start];
return 0;
}
//分成两个子数组
int len=(end-start)/2;
int leftCount=InversePairsCountCore(copy,data,start,start+len);//然后使用递归对左数组不断进行分解，直至start==end，即只有一个数的情况
int rightCount=InversePairsCountCore(copy,data,start+len+1,end); int i=start+len;//左数组最后一个数下标
int j=end;
int indexOfCopy=end;//在数组copy中，从最后一位进行复制
int count=0;
while(i>=start && j>=start+len+1){
if(data[i]>data[j]){//如果左数组最后一个数大于右数组最后一个数，逆序对数为右数组剩下数字的个数，并将左数组此数组添加至copy数组中
copy[indexOfCopy--]=data[i--];
count+=j-start-len;
}else{
copy[indexOfCopy--]=data[j--];
}
}
for(;i>=start;i--)
copy[indexOfCopy--]=data[i];
for(;j>=start+len+1;j--)
copy[indexOfCopy--]=data[j]; return leftCount+rightCount+count;
} public static void main(String[] args) {
InversePairsCount i=new InversePairsCount();
int[] nums=new int[]{7,5,6,4};
int n=i.InversePairs(nums);
System.out.println(n); }
}