l9_8.cpp

《数据结构（C++描述）》-李根强-源代码

//归并排序
#include<iostream.h>
typedef int ElemType;
const int n=10;
ElemType a[n]={12,6,14,8,10,7,1,5,38,9};
void merge(ElemType R[],ElemType A[],int s,int m,int t)
//对两个子区间R[s]--R[m]和R[m+1]--R[t]合并，结果存入A中
{ int i,j,k;
 i=s;j=m+1;k=s;
 while((i<=m)&&(j<=t))
  if(R[i]<=R[j])
  { A[k]=R[i];i++;k++;}
  else
  {A[k]=R[j];j++;k++;}
  while(i<=m)            //复制第一个区间中剩下元素
  { A[k]=R[i];i++;k++;}
  while(j<=t)             //复制第二个区间中剩下元素
  { A[k]=R[j];j++;k++;} 
 
}

void mergepass(ElemType R[],ElemType A[],int n,int c)
//对R数组做一趟归并，结果存入A数组中,n为元素个数，c为区间长度
{ int i,j;
  i=0;
  while(i+2*c-1<=n-1)
  {   //长度均为c的两个区间合并成一个区间
	  merge(R,A,i,i+c-1,i+2*c-1);
	  i+=2*c;
  }
   if(i+c-1<n)//长度不等的两个区间合并成一个区间
	   merge(R,A,i,i+c-1,n-1);
	else
		for(j=i;j<=n-1;j++)//仅剩一个区间时，直接复制到A中
		A[j]=R[j];
}
void mergesort(ElemType R[],int n)
{int c=1;ElemType A[10];
 while(c<n)
 {
	 mergepass(R,A,n,c);//一次合并，结果存入A中
	 c*=2;               //区间长度扩大一倍
	 mergepass(A,R,n,c);//再次合并，结果存入R中
	 c*=2;
 }
}


void print(ElemType r[n])
{ int i;
for(i=0;i<n;i++)
cout<<r[i]<<" ";
cout<<endl;
}
void main()
{ cout<<endl<<"排序前的结果为:"<<endl;
 print(a);
 mergesort(a,n);
 cout<<endl<<"排序后的结果为:"<<endl;
print(a);
}