自然合并排序（数组）.cpp

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

// Natualmergesort.cpp : Defines the entry point for the console application.
//
#include <iostream.h>
#define n 8
void merge(int a[],int b[],int lo,int hi,bool asc)
{
	int k = asc ?lo:hi;
	int c = asc ? 1:-1;
	int i =lo,j = hi;
	while(i<=j)
	{
		if(a[i]<=a[j]) b[k] = a[i++];
		else
			b[k] = a[j--];
		k+=c;
	}
}

bool mergesuns(int a[],int b[])
{
	int i=0,k=0,x;
	bool asc = true;
	while (i<n)
	{
	   k = i;
	   do x= a[i++];
	   while(i<n&&x<=a[i]);
	   while(i<n&&x>=a[i])
		   x=a[i++];
	   merge(a,b,k,i-1,asc);
	   asc = !asc;
	}
	return k == 0;
}


void sort(int a0[],int m)
{
	int i=0;
	int b[n] = {0};
	while(!mergesuns(a0,b)&!mergesuns(b,a0));
	cout << "The sorted_Array is :" << endl;
	for(i=0;i<m;i++)
		cout << a0[i] <<", ";
	 cout << endl;
}

int main()
{
    int i;
    int a[n] = {0};
	cout << "Please enter 8 numbers!"<< endl;
     for(i=0;i<n;i++)
		cin >> a[i];
	 sort(a,n);
	return 0;
}