逆序对
设A[1..n]是一个包含N个非负整数的数组。如果在i < j的情况下，有A[ i ]>A[ j ]，则( i , j )就称为A中的一个逆序对。
例如，数组（3，1，4，5，2）的“逆序对”有<3,1>,<3,2><4,2><5,2>，共4个。
使用归并排序可以用O(nlogn)的时间解决统计逆序对个数的问题
定义：对于一个给定的数列,如果有i<j,且Ai>Aj,则称(i,j)为一逆序对.
要解决的问题是,给出一个数列,求出这个数列包含多少个逆序对
solution 1:最原始的方法，就是列举，两重循环，代码：
int count_inversion(int *a,int N)
{
int count = 0;
int i,j;
for (i = 0 ;i < N ;i ++)
for(j = i + 1; j < N ;j++)
if (a < a[j])
count ++;
return count;
}
这种时间复杂度是O(n^2)
不过还有更好的算法，树上提示用mergesort，可以达到o(nlogn),于是，我修改了mergesort代码：
void merge_inversion(int *a,int l,int m,int r)
{
int i,j,k;
int n1 = m - l + 1;
int n2 = r - m;
int *L = (int *)calloc(n1,sizeof(int));
int *R = (int *)calloc(n2,sizeof(int));
for(i = l; i <=m ;i ++)
L[i-l]=a;
for(j = m +1 ;j <= r ;j ++)
R[j -m-1] = a[j];
i = 0 ;
j = 0 ;
for(k = l ;k <= r ;k ++)
{
if ( i < n1 && j < n2 )
{
if( L < R[j])
{
a[k]=L[i++];
globa_count += n2-1-j+1;
}
else
a[k]=R[j++];
}
else
break;
}
// process if one part terminately early
if (i == n1 && j < n2)
while(j < n2)
a[k++]=R[j++];
if (i < n1 && j == n2)
while(i < n1)
a[k++]=L[i++];
free(L);
free(R);
}
修改这一行就可以了，这种算法甚是巧妙。
下面是我的pascal版merge sort方法（完整程序）
Program Bamboobrook;
Const MaxN=100000;
Lim=MaxLongint Div 10;
Var A,A1,A2:Array[1..MaxN]of Longint;
N,I:Longint;
Ans:Qword;
Procedure MergeSort(L,R:Longint);
Var Mid,L1,L2,I,J,K:Longint;
Begin
Mid:=(L+R)Shr 1;
If(L<Mid)Then
MergeSort(L,Mid);
If(Mid+1<R)Then
MergeSort(Mid+1,R);
L1:=Mid+1-L;
L2:=R-Mid;
For I:=1 to L1 do
A1[I]:=A[L+I-1];
For I:=1 to L2 do
A2[I]:=A[Mid+I];
A1[L1+1]:=Lim;
A2[L2+1]:=Lim;
I:=1; J:=1;
For K:=L to R do
If(A1[I]<=A2[J])Then
Begin
A[K]:=A1[I];
Inc(I);
End
Else Begin
A[K]:=A2[J];
Inc(J);
Inc(Ans,L1+1-I);
End;
End;
Begin
Readln(N);
Ans:=0;
For I:=1 to N do
Read(A[I]);
MergeSort(1,N);
Writeln(Ans);
End.