存储于数组中的自然排序.cpp

递归和分治法解一系列经典算法

#include<iostream.h>

void merge(int *a,int *b,int lo,int mid,int hi)
{    
	int i=lo,j=mid+1,k=0;
	while((i<=mid)&&(j<=hi)){
		if(a[i]<=a[j]) b[k++]=a[i++];
		else b[k++]=a[j++];
	}
	while(i<=mid) b[k++]=a[i++];
	while(j<=hi) b[k++]=a[j++];
}

bool mergeruns(int *a,int *b,int n)
{
	int i=0,k=0;
	int x,l;
	while(i<n)
	{  
		k=i ;
		//找到相邻的排好序的两个子序列
		do x=a[i++]; while(i<n&&x<=a[i]);
		l=i; x=a[i++];
		while(i<n&&x<=a[i]) x=a[i++];
		//对这两个子序列进行合并排序
		merge(a,b,k,l-1,i-1);
	}
	return k==0;
}


void main()
{
	int *a,*b,n,i;
	cout<<"请输入整数的个数n:";
	cin>>n;
	a=new int[n];
	b=new int[n];
	cout<<"请输入"<<n<<"个整数：";
	for(i=0;i<n;i++){
		b[i]=0;
		cin>>a[i];
	}
	mergeruns(a,b,n);
	cout<<"排好序的整数序列为：";
	for(i=0;i<n;i++)cout<<b[i]<<" ";
	cout<<endl;
}