#include<stdio.h>
void msort(long *a,long *t,long begin,long end)
{
long mid=(begin+end)/2,p=begin,q=mid+1,i=begin;
if(begin<end)
{
msort(a,t,begin,mid);
msort(a,t,mid+1,end);
while(i<=end)
{
if(q>end||a[p]<=a[q]) t[i++]=a[p++];
else t[i++]=a[q++];
}
for(long i=begin;i<=end;i++) a[i]=t[i];
}
}
int main()
{
//*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
const long maxn=108;
long n=0,a[maxn],t[maxn];
bool first=true;
while(scanf("%ld",&a[n+1])==1) n++;
// Read In
msort(a,t,1,n);
// M_sort
for(long i=1;i<=n;i++)
{
if(first) first=false;
else printf(" ");
printf("%ld",a[i]);
}
putchar('\n');
return 0;
}
在上面的歸并排序程序的基礎上，很容易修改得出求一個序列逆序對個數的程序。
以下是我的代碼，只給出函數，main()與上面的基本相同：
long count(long *a,long *t,long begin,long end)
{
long mid=(begin+end)/2,p=begin,q=mid+1,i=begin,re=0;
if(begin<end)
{
re+=count(a,t,begin,mid);
re+=count(a,t,mid+1,end);
while(i<=end)
{
if(q>end||a[p]<=a[q]) t[i++]=a[p++];
else
{
t[i++]=a[q++];
re+=mid-p+1;
}
}
for(long i=begin;i<=end;i++) a[i]=t[i];
}
return re;
}
posted on 2010-01-09 18:26
lee1r 閱讀(363)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數據結構