??? 用模板寫的一個歸并排序，并且注明了用歸并排序求逆序數的方法……
#include?<stdio.h>
template?<?class?T?>
void?mergeSort(?T?*a,?int?size?)
{
????int?*b=new?T[size];
????mergePass(a,b,0,size-1);
}
template?<?class?T?>
void?mergePass(?T?*a,?T?*b,?int?l,?int?r?)
{
????int?m;
????if(l<r)
????{
????????m=(l+r)/2;
????????mergePass(a,b,l,m);
????????mergePass(a,b,m+1,r);
????????merge(a,b,l,m,r);
????????copy(a,b,l,r);
????}
}
template?<?class?T?>
void?merge(?T?*a,?T?*b,?int?l,?int?m,?int?r?)
{
????int?i=l,j=m+1;
????while(i<=m&&j<=r)
????{
????????if(a[i]<=b[j])
????????????b[l++]=a[i++];
????????else
????????{
????????????b[l++]=a[j++];
????????????//num+=m-i+1;
????????????//用歸并排序求逆序數則在這里添加這句話，num為全局變量
????????????//num+=前路還沒有歸并的長度+1
????????}
????}
????while(i<=m)
????????b[l++]=a[i++];
????while(j<=r)
????????b[l++]=a[j++];
}
template?<?class?T?>
void?copy(?T?*a,?T?*b,?int?l,?int?r?)
{
????while(l<=r)
????{
????????a[l]=b[l];
????????l++;
????}
}
int?main()
{
????int?a[10]={10,9,8,7,6,5,4,3,2,1},i;
????mergeSort(a,10);
????for(i=0;i<10;i++)
????????printf("%d?",a[i]);
????putchar('\n');
????return?0;
}posted on 2006-10-26 23:01
Asp 閱讀(2044)
評論(3) 編輯 收藏 引用 所屬分類:
Ar!thmEt!c.Self