用O(nlgn)的最坏运行时间,确定n个元素的数组中逆序对的数目(修改合并排序):
int merge_inversion(int a[],int p,int q,int r) { int n1=q-p+1; int n2=r-q; int *L=new int[n1]; int *R=new int[n2]; int i,j,k,v; for(i=0;i<n1;++i) L[i]=a[p+i]; for(j=0;j<n2;++j) R[j]=a[q+1+j]; i=0; j=0; v=0; for(k=p;k<=r;++k) { if(i>n1-1) a[k]=R[j++]; else if(j>n2-1) a[k]=L[i++]; else if(L[i]>R[j]) { a[k]=R[j++]; v+=n1-i;//注意逆序对的个数!!!不是n1-i-1 } else a[k]=L[i++]; } delete L; delete R; return v; } int count_inversion(int a[],int p,int r) { int v=0,q; if(p<r) { q=(p+r)/2; v+=count_inversion(a,p,q); v+=count_inversion(a,q+1,r); v+=merge_inversion(a,p,q,r); } return v; }