早就想學(xué)一下歸并排序求逆序?qū)?，在這之前只會(huì)用樹狀數(shù)組來做，有時(shí)候還需要離散化，而且效率還不如歸并排序高。
其實(shí)還是蠻簡單的，知道歸并排序的原理就很容易知道如何求逆序?qū)α恕ＴO(shè)數(shù)組為A，關(guān)鍵是在合并的時(shí)候，用數(shù)組L 和 R 表示左右兩個(gè)子數(shù)組，因?yàn)槟嫘驅(qū)Φ膫€(gè)數(shù)f(A) = f(L) + f(R) + s(L,R);其中f(L) 和 f(R) 分別表示L 內(nèi)部 和R內(nèi)部的逆序?qū)€(gè)數(shù)，s(L.R)表示大數(shù)在L，小數(shù)在R的逆序?qū)?。因?yàn)長和R是已經(jīng)排好序的，故其實(shí)只需求s(L,R).這個(gè)可以在合并L和R依次進(jìn)行比較的時(shí)候算出。
for(k = p;k <= r;k ++){
if(L[i]<=R[j])
a[k] = L[i++];
else{ //如果L最上面的數(shù)大于R的，那么L[i]及后面的數(shù)可以和R[j]構(gòu)成n1-i+1個(gè)逆序?qū)?br> a[k] = R[j++];
count +=(n1 -i + 1); //累加
}
}
歸并排序的代碼：
void merge(int p,int q,int r){
int n1 = q-p+1,n2 = r-q;
int i,j,k;
for(i = 1;i <= n1; i++)
L[i] = a[p+i-1];
for(j = 1;j <= n2; j++)
R[j] = a[q+j];
L[n1+1] = INF;
R[n2+1] = INF;
i = 1;j = 1;
for(k = p;k <= r;k ++){
if(L[i]<=R[j])
a[k] = L[i++];
else{
a[k] = R[j++];
count +=(n1 -i + 1);
}
}
}
void merge_sort(int p,int r){
if(p<r){
int q = (p+r)/2;
merge_sort(p,q);
merge_sort(q+1,r);
merge(p,q,r);
}
}