二路归并排序的递归实现和非递归实现

叁歲伎倆 2023-02-11 03:19 19阅读 0赞

递归实现：

#include<iostream>
    using namespace std;
    void print(int a[],int n)
    { 
    	for(int i=1;i<=n;i++)
    	cout<<a[i]<<' ';
    	cout<<endl;
    }
    void Merge(int a[],int l,int m,int r)
    { 
    	int temp[1000],k,i,j;
    	k=l,i=l,j=m+1;
    	while(i<=m&&j<=r)
    	{ 
    		if(a[i]<=a[j])
    		temp[k++]=a[i++];
    		else
    		temp[k++]=a[j++];
    	}
    	while(i<=m)
    	temp[k++]=a[i++];
    	while(j<=r)
    	temp[k++]=a[j++];
    	for(i=l;i<=r;i++)
    	a[i]=temp[i];
    }
    void Msort(int a[],int l,int r)
    { 
    	if(l==r)
    	return;
    	int m=(l+r)/2;
    	Msort(a,l,m);
    	Msort(a,m+1,r);
    	Merge(a,l,m,r);
    }
    int main()
    { 
    	int a[1000],n,i;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	cin>>a[i];
    	Msort(a,1,n);
    	print(a,n);
    	return 0;
    }

非递归实现：

#include<iostream>
    #include<algorithm>
    using namespace std;
    void print(int a[],int n)
    { 
    	for(int i=1;i<=n;i++)
    	cout<<a[i]<<' ';
    	cout<<endl;
    }
    void Merge(int a[],int l,int m,int r)
    { 
    	int temp[1000],k,i,j;
    	k=l,i=l,j=m+1;
    	while(i<=m&&j<=r)
    	{ 
    		if(a[i]<=a[j])
    		temp[k++]=a[i++];
    		else
    		temp[k++]=a[j++];
    	}
    	while(i<=m)
    	temp[k++]=a[i++];
    	while(j<=r)
    	temp[k++]=a[j++];
    	for(i=l;i<=r;i++)
    	a[i]=temp[i];
    }
    void Msort(int a[],int n)
    { 
    	int k,left1,right1,left2,right2;
    	for(k=1;k<n;k*=2)//子段长为k 
    	{ 
    		left1=1;
    		right1=k;
    		left2=1+k;
    		right2=min(2*k,n);//注意边界
    		while(left2<=n)//存在第二段才有可能去归并
    		{ 
    		   Merge(a,left1,right1,right2);
    		   left1+=2*k;
    		   right1+=2*k;
    		   left2+=2*k;
    		   right2=min(right2+2*k,n);			
    		}
    		 print(a,n);
    	}
    }
    int main()
    { 
    	int a[1000],n,i;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	cin>>a[i];
    	Msort(a,n);
    	return 0;
    }