gui.cpp

理解递归算法的思想和递归程序的执行过程

#include<stdio.h>
void twomerge(int a[],int r[],int s,int m,int t)
{
	int i,j,k;
	i=s;j=m+1;k=s;
	while(i<=m&&j<=t)
	{
		if(a[i]<=a[j])
		{
			r[k]=a[i];i++;k++;
		}
		else
		{
			r[k]=a[j];j++;k++;
		}
	}
	while(i<=m)
	{
		r[k]=a[i];i++;k++;
	}
	while(j<=t)
	{
		r[k]=a[j];j++;k++;
	}
}
void mergepass(int a[],int r[],int n,int len)
{
	int p=0;
	while(p+2*len-1<=n-1)
	{
		twomerge(a,r,p,p+len-1,p+2*len-1);
		p+=2*len;
	}
	if(p+len-1<n-1)
		twomerge(a,r,p,p+len-1,n-1);
	else
		for(int i=p;i<=n-1;i++)
			r[i]=a[i];
}
void mergesort(int a[],int n)
{
	int *r=new int[n];
	int len=1;
	while(len<n)
	{
		mergepass(a,r,n,len);
		len*=2;
		mergepass(r,a,n,len);
		len*=2;
	}
	delete []r;
}
void print(int a[],int sum)
{
	for(int i=0;i<sum;i++)
		printf("%d\n",a[i]);
}
void main()
{
	int sum=0,i=0;
	scanf("%d\n",&sum);
	int *a=new int[sum];
	for(i=0;i<sum;i++)
		scanf("%d",&a[i]);
	mergesort(a,sum);
	print(a,sum);
}