题解 | #数组中的逆序对#
数组中的逆序对
http://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
分治加归并排序，看代码吧，每一步都有解释
public class Solution {
long count = 0;
public int InversePairs(int [] array) {
if(array == null || array.length <= 1)return 0;
//分治,归并排序，因为分治下的两部分序列是有序的，只要右边的小于左边的最左的，就小于左边剩下的全部的
sort(array, 0, array.length-1);
return (int)(count%1000000007);
}
//归并排序
void sort(int[] array, int left, int right){
if(left >= right)return;
int mid = (right+left)/2;
//左区域
sort(array, left, mid);
//右区域
sort(array, mid+1, right);
//合并
merge(array, left, right);
}
void merge(int[] array, int left, int right){
//辅助数组，用来存放有序的子序列，然后再复制到array中
int[] temp = new int[right-left+1];
int mid = (right+left)/2;
int i = left, j = mid+1, k = 0;
//当i小于等于mid，并且j小于等于right时，进行比较
while(i <= mid && j <= right){
//如果前面的大于后面的
if(array[i] > array[j]){
//由于左右两边都是有序的，所以array[i]大于右边的array[j]，说明从array[i]到array[mid]都大于array[j]
count += mid-i+1;
//把array[j]这个最小的存在temp中，j++
temp[k++] = array[j++];
}else{
//这种情况就是array[i]小于等于array[j]，array[i]和array[j]到array[right]都不回存在逆序对，直接放进temp中
temp[k++] = array[i++];
}
}
//由于可能temp[j]到temp[right]都比较小，导致提前结束，做一个temp的赋值
while(i <= mid){
temp[k++] = array[i++];
}
//由于可能temp[j]到temp[right]都比较大，导致提前结束，做一个temp的赋值
while(j <= right){
temp[k++] = array[j++];
}
//把temp的有序数组赋值到array中
for(k = 0; k < temp.length; k++){
array[left+k] = temp[k];
}
}
} 
