归并排序.cpp

数据结构学习中常用的程序．用c语言编写．vc＋＋６．０运行通过

#include <stdio.h>
#include <stdlib.h>
typedef int InfoType;

#define n 10					//假设的文件长度，即待排序的记录数目
typedef int KeyType;			//假设的关键字类型
typedef struct {				//记录类型
	KeyType key;				//关键字项
	InfoType otherinfo;			//其它数据项，类型InfoType依赖于具体应用而定义
} RecType;
typedef RecType SeqList[n+1];	//SeqList为顺序表类型，表中第0个单元一般用作哨兵
void Merge(SeqList R,int low,int m,int high);
void MergePass(SeqList R,int length);

void main()
{
	void MergeSort(SeqList R);
	int i;
	SeqList R;
	printf("请输入欲排序的数：");
	for (i=1;i<=n;i++)
		scanf("%d",&R[i].key);
	printf("排序前：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
	MergeSort(R);
	printf("排序后：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
}

void Merge(SeqList R,int low,int m,int high)
{	//将两个有序的子文件R[low..m]和R[m+1..high]归并成一个有序的子文件R[low..high]
	int i=low,j=m+1,p=0;		//置初始值
	RecType *R1;				//R1是局部向量，若p定义为此类型指针速度更快
	R1=(RecType *)malloc((high-low+1)*sizeof(RecType));
	if(!R1)						//申请空间失败
	{
		printf("Insufficient memory available!");
		exit(0);
	}
	while(i<=m && j<=high)		//两子文件非空时取其小者输出到R1[p]上
		R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];
	while(i<=m)					//若第1个子文件非空，则复制剩余记录到R1中
		R1[p++]=R[i++];
	while(j<=high)				//若第2个子文件非空，则复制剩余记录到R1中
		R1[p++]=R[j++];
	for(p=0,i=low;i<=high;p++,i++)
		R[i]=R1[p];				//归并完成后将结果复制回R[low..high]
}

void MergePass(SeqList R,int length)
{	//对R[1..n]做一趟归并排序
	int i;
	for(i=1;i+2*length-1<=n;i=i+2*length)
		Merge(R,i,i+length-1,i+2*length-1);
								//归并长度为length的两个相邻的子文件
	if(i+length-1<n)			//尚有两个子文件，其中后一个长度小于length
		Merge(R,i,i+length-1,n);//归并最后两个子文件
	//注意：若i≤n且i+length-1≥n时，则剩余一个子文件轮空，无须归并
}

void MergeSort(SeqList R)
{	//采用自底向上的方法，对R[1..n]进行二路归并排序
	int length;
	for(length=1;length<n;length*=2)	//进行二路归并排序
		MergePass(R,length);			//有序段长度≥n时终止
}