merge.h

各种排序方法源码

#include<string.h>
//-------------------------------归并函数------------------------------------------//
void merge(node *rs,node *d,int i,int m,int n)
{//将有序rs[s...m]和rs[m+1...t]归并为有序的d[s...t]
	int k,j,p=i;
	for(j=m+1,k=i;i<=m&&j<=n;++k)  //将rs中记录由小到大地并入d
	{
		if(rs[i].data<rs[j].data)
		{
			d[k].data=rs[i].data;
			strcpy(d[k].c,rs[i].c);
			i++;
		}
        else
		{
			d[k].data=rs[j].data;
			strcpy(d[k].c,rs[j].c);
			j++;
		}
	}
	if(i<=m)     //将剩余的rs[i...m]复制到d
		for(;i<=m&&k<=n;++i,++k)
		{
			d[k].data=rs[i].data;
			strcpy(d[k].c,rs[i].c);
		}
		if(j<=n)    //将剩余的rs[j...n]复制到d
			for(;j<=n&&k<=n;++j,++k)
			{
				d[k].data=rs[j].data;
				strcpy(d[k].c,rs[j].c);
			}
   for(j=p;j<=n;++j)
   {
    rs[j].data=d[j].data;
        strcpy(rs[j].c,d[j].c);
   }
}
//---------------------------------归并排序递归函数-----------------------------------//
void msort(node *d,node *p,int s,int t)
{//将d[s...t]归并为p[s...t]
	int m;
	if(s==t)
	{
		p[s].data=d[s].data;
        strcpy(p[s].c,d[s].c);
	}
	else
	{
		m=(s+t)/2;      //将d[s..t]平分为d[s...m]和d[m+1...t]
		msort(d,p,s,m);    //递归地将d[s...m]归并为有序的p[s...m]
		msort(d,p,m+1,t);   //递归地将d[m+1...t]归并为有序的p[m+1...t]
		merge(p,d,s,m,t);	//将p[s...m]和p[m+1...t]归并到d[s...t]
	}
}
//-------------------------------归并排序驱动函数---------------------------------------//
void mergesort(node *&d,int num)
{//对顺序表d作归并排序
	node *p;
	p=(node *)malloc((num+1)*sizeof(node));  //辅助空间
	msort(d,p,1,num);
	free(p);
}