//题目：输入一个数组，返回数组中的逆序数对个数
//采用类似二路归并排序的方式来计算，每次出现第二组的数小于第一组数时就将result加上第一组元素的长度
public class Main {
public static void main(String[] args) throws Exception {
System.out.println(findReverseCount(new int[]{7,5,6,4}));
}
public static int findReverseCount(int[] input){
int low = 0;
int high = input.length-1;
int result = sort(input,low,high);
return result;
}
public static int sort(int[] input, int low, int high){
if(low == high){ //当low与high相等时就返回0
return 0;
}
int mid = (low+high)/2;
int left = sort(input,low,mid); //要返回每一组归并的逆序数
int right = sort(input,mid+1,high);
int count = merge(input,low,high,mid);
return left+right+count;
}
public static int merge(int[] input, int low, int high, int mid){
int result = 0;
int[] temp = new int[input.length];
for(int i = low;i<=high;i++){
temp[i] = input[i];
}
int leftStart = low;
int leftEnd = mid;
int rightStart = mid+1;
int rightEnd = high;
int index = low;
while(leftStart<=leftEnd && rightStart<=rightEnd){
if(temp[leftStart]>temp[rightStart]){ //第二组的第一个数小于第一组第一个数
input[index] = temp[rightStart];
result = result+(leftEnd-leftStart+1); //逆序数加上第一组还剩元素的个数
rightStart++;
}else{
input[index] = temp[leftStart];
leftStart++;
}
index++;
}
while(leftStart<=leftEnd){
input[index] = temp[leftStart];
leftStart++;
index++;
}
while(rightStart<=rightEnd){
input[index] = temp[rightStart];
rightStart++;
index++;
}
return result;
}
}
