博客

C语言实现二路归并算法

#include<stdio.h>
//将有序的sr[i...m]和sr[m+1...n]归并为有序的tr[i...n]
void merge(int sr[],int tr[],int i,int m,int n)
{
	int j,k;
	for(j=m+1,k=i;i<=m&&j<=n;++k)
		if(sr[i]<sr[j]) tr[k]=sr[i++];
		else tr[k]=sr[j++];
	while(i<=m) tr[k++]=sr[i++];
	while(j<=n) tr[k++]=sr[j++];
}

//将无序的sr[s...t]归并为有序的tr1[s...t]
void msort(int sr[],int tr1[],int s,int t)
{
	int m;
	int tr2[100];
	if(s==t) tr1[s]=sr[s];
	else
	{
		m=(s+t)/2;
		msort(sr,tr2,s,m);
		msort(sr,tr2,m+1,t);
		merge(tr2,tr1,s,m,t);
	}
}

void main()
{
	int x[11]={0,1,34,56,23,40,90,78,60,100,30};
	int d[11],i;
	msort(x,d,1,10);
	for(i=1;i<=10;i++)
		printf("%d   ",d[i]);
}