用模板写的一个归并排序，并且注明了用归并排序求逆序数的方法……
#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 阅读(1998)
评论(3) 编辑 收藏 引用 所属分类:
Ar!thmEt!c.Self