逆序对数(inverse number) 给一列数a1, a2, . . . , an，求它的逆序对数，即有多少 个有序对i, j使得i < j但a[i] > a[j]。最简单的方法是二重循环，时间复杂度为O(n2)。 如果利用归并排序，我们可以轻松做到这一点。划分和递归求解部分完全一致，只有 合并部分需要修改：需要加上跨越两边的逆序对。考虑右表中的任意元素k。当k从右 表中删除时，左表剩下的所有元素x都与k构成(x; k)逆序对，因此应该在总答案中加上 左表此时的元素个数。
下面的程序中，左表初始为[l;m]而右表为[m + 1; r]，两个表各有一个指针i和j， 因此在任意时刻左表为[i;m]而右表为[j; r]。如果右表为空或者两表都不空且a[i] · a[j]时，元素i从左表中移出；否则元素j从右表中移出，并累加左表元素个数m ¡ ¡j + 1。
这个好像是错的呀，while条件应该是||
void sort (int l , int r)
{
if(l >= r) return 0;
int m = ( l + r) > > 1;
sort (l , m);
sort (m+1 , r);
// merge [l,m] and [m+1,r]
int i = l , j = m+1 , c = l;
while (i <= m && j <= r)
if(j > r || ( i <= m && a[i] <= a[j ]) )
t[c ++] = a[i ++];
else
{ t[c ++] = a[j ++]; cnt += m– i + 1; }
// copy back
for(i = l; i <= r; i ++) a[i ] = t[i];
}
只要把cnt += m - i + 1;这一句去掉，就是标准的归并排序。时间复杂度也 是O(n log n)，比普通的O(n2)算法快很多。需要注意的是附加空间t数组是(n)的。
public class Solution {
private int[] array=null;
private int[] t = null;
private int cnt=0;
private void sort(int l,int r){
if(l>=r) return;
int m=(l+r)>>1;
sort(l, m);
sort(m + 1, r);
int i=l,j=m+1,c=l;
while (i<=m||j<=r){
if(j>r||i<=m&&array[i]<=array[j]){
t[c++]=array[i++];
}else{
t[c++]=array[j++];
cnt=(cnt+m-i+1)%1000000007;
}
}
for(i=l;i<=r;i++){
array[i]=t[i];
}
}
public int InversePairs(int [] array) {
this.array=array;
t=new int[array.length];
sort(0,array.length-1);
return cnt;
}
public static void main(String[] args) {
int[] a=new int[]{1,2,3,4,5,6,7,0};
int res = new Solution().InversePairs(a);
System.out.println(res);
}
}