数组中的逆序对
数组中的逆序对
http://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
采用归并方法进行解决
思路分析：归并，将大问题不断分解成小问题，直到不能再分，解决了最小问题后，再合并较大问题，并解决，再一直合并成最终问题再解决（注意是并起来的时候解决）。
public class Solution {
int count; //统计逆序对的个数
public int InversePairs(int [] array) {
if(array == null || array.length == 0){
return 0;
}
divide(array, 0, array.length-1);
return count;
}
//归并排序的分治---分
private void divide(int [] array, int start, int end){
//递归的终止条件
if(start >= end){
return;
}
int mid = start + (end - start)/2;
//递归分
divide(array, start, mid);
divide(array, mid+1, end);
//治
merge(array, start, mid, end);
}
private void merge(int [] array, int start, int mid, int end){
//创建一个等长的数组
int[] tmp = new int[end-start+1];
int i = start;
int j = mid + 1;
int k = 0;
while(i <= mid && j <= end){ //
if(array[i] <= array[j]){
tmp[k++] = array[i++]; //拆分出来的左数组向右进行移位
}else{
tmp[k++] = array[j++]; //拆分出来的右数组进行移位
count = (count + mid - i + 1)%1000000007;
}
}
//各自还有未完成的将其比完
while(i <= mid){
tmp[k++] = array[i++];
}
while(j <= end){
tmp[k++] = array[j++];
}
//覆盖愿数组
for(k = 0; k < tmp.length; k++){
array[start + k] = tmp[k];
}
}
}