算法分析_自然合并排序.cpp

自然合并排序算法 与归并算法MergeSort相比 没有递归的过程 是按照数组的大小依次进行合并来实现排序的算法

/************************************************************************/
/* 从分治策略的机制入手，容易消除归并排序算法中的递归，事实上，算法Mergesort的递归过程只是将待排序列
集合一分为二，直到待排序列集合只剩下一个元素为止，然后不断合并两个排好序的数组段。按此机制，可以首先
将数组a中相邻元素两两配对。用合并算法将它们排序，构成n/2组长度为2的排好序的子数组段，然后再将它们
排序成长度为4的排好序的子数组段，如此继续下去，直至整个数组排好序。按照此思想，消去递归后的
合并排序算法描述如下： */
/************************************************************************/
#include <stdio.h>
template <typename Type>
void Merge(Type c[],Type d[],int l,int m,int r)
{//合并c[l:m]和c[m+1:r]到d[l:r]
	int i=l,j=m+1,k=l;
	while ((i<=m)&&(j<=r))
	{
		if (c[i]<=c[j])
		{
			d[k++]=c[i++];
		} 
		else
		{
			d[k++]=c[j++];
		}
	}
	if (i>m)
	{
		for (int q=j;q<=r;q++)
		{
			d[k++]=c[q];
		}
	} 
	else
	{
		for (int q=i;q<=m;q++)
		{
			d[k++]=c[q];
		}
	}
}
template <typename Type>
void MergePass(Type x[],Type y[],int s,int n)
{//合并大小为s的相邻子数组
	int i=0;
	while (i<=n-2*s)
	{//合并大小为s的相邻2段子数组
		Merge(x,y,i,i+s-1,i+2*s-1);
		i=i+2*s;
	}
	//剩下的元素个数小于2s
	if (i+s<n)
	{
		Merge(x,y,i,i+s-1,n-1);
	} 
	else
	{
		for (int j=i;j<=n-1;j++)
		{
			y[j]=x[j];
		}
	}
}
template <typename Type>
void MergeSort(Type a[],int n)
{
	Type *b=new Type[n];
	int s=1;
	while (s<n)
	{
		MergePass(a,b,s,n);//合并到数组a
		s+=s;
		MergePass(b,a,s,n);//合并到数组b
		s+=s;
	}
}
void main()
{
	int x[]={1,89,23,5,7,90,0,2,5,78,1,5},m;
	m=sizeof(x)/sizeof(*x);
	printf("before sorted:\n");
	for (int j=0;j<m;j++)
	{
		printf("%d ",x[j]);
	}
	MergeSort(x,m);
	printf("\nafter sorted:\n");
	for (int i=0;i<m;i++)
	{
		printf("%d ",x[i]);
	}
	printf("\n");
}
/*
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
void Merge(int a[],int TmpArray[],int Lpos,int Rpos,int RightEnd)
{//Lpos=start of left half,Rpos=start of right half
  int i,LeftEnd,NumElements,TmpPos;
  LeftEnd=Rpos-1;
  TmpPos=Lpos;
  NumElements=RightEnd-Lpos+1;
  while (Lpos<=LeftEnd&&Rpos<=RightEnd)
  {
	if (a[Lpos]<=a[Rpos])
	{
	  TmpArray[TmpPos++]=a[Lpos++];
	}
    else
       TmpArray[TmpPos++]=a[Rpos++];
	 }
  while(Lpos<=LeftEnd)//copy rest of first half
    TmpArray[TmpPos++]=a[Lpos++];
  while(Rpos<=RightEnd)//copy rest of second half
    TmpArray[TmpPos++]=a[Rpos++];
  //copy TmpArray back
	for (i=0;i<NumElements;i++,RightEnd--)
	{
    	a[RightEnd]=TmpArray[RightEnd];
	}
}
////////////////////////////////////////////////////////////
void MSort(int a[],int TmpArray[],int Left,int Right)
{
   int Center;
	if (Left<Right)
	{
		Center=(Left+Right)/2;
		MSort(a,TmpArray,Left,Center);
		MSort(a,TmpArray,Center+1,Right);
		Merge(a,TmpArray,Left,Center+1,Right);
	}
}
//////////////////////////////////////////////////////
void Mergesort(int a[],int n)
{
	int *TmpArray;
	TmpArray=(int *)malloc(n*sizeof(int));
	if (TmpArray)
	{
		MSort(a,TmpArray,0,n-1);
		free(TmpArray);
	}
	else
	  exit(0);
}
////////////////////////////////
void main()
{
	int x[]={1,89,23,5,7,90,0,2,5,78,1,5},m;
	m=sizeof(x)/sizeof(*x);
	printf("before sorted:\n");
	for (int j=0;j<m;j++)
	{
	   printf("%d ",x[j]);
	}
	Mergesort(x,m);
	printf("\nafter soerted:\n");
	for (int i=0;i<m;i++)
	{
	  printf("%d  ",x[i]);
	}
}
*/