数据结构-归并排序

归并排序

基本概念

归并是指将两个或两个以上的有序表合并成一个有序表。

基本思想

假设有N个记录，则可以看成是N个有序的子序列，每个子序列的长度为1，然后两两归并得到[n/2]

个（上取整）长度为2的子序列，然后再两两归并，最终得到一个长度为N的序列，就是所求序

列。

这种归并方法也被称为二路归并排序。

示例图

代码

#include<stdio.h>
#define MAX 100
typedef int KeyType;
typedef struct{
	KeyType key;
}RecordType;
typedef struct{
	RecordType data[MAX+1];
	int length;
}OrderList;

void InitMyOrderList(OrderList *L)    //初始化数据
{
	int sample_data[11] = {0,5,9,1,100,101,55,66,22,33,22};
	int i;
	L->length = 10;
	for(i=1;i<=L->length;i++)
		L->data[i].key = sample_data[i];
}

void OutPutMyOrderList(OrderList *L)        //打印数据
{
	int i;
	for(i=1;i<=L->length;i++)
		printf("%d ",L->data[i].key);
}

void Merge(OrderList *L,OrderList *T,int i,int m,int n)		//归并算法 
{
	int j,k;            //处理L[i,m],L[m+1,n]这两组数据
	for(j=m+1,k=i;j<=n&&i<=m;k++){
		if(L->data[i].key < L->data[j].key){    //将较小的数据存入到T中
			T->data[k] = L->data[i++];
		}
		else{
			T->data[k] = L->data[j++];
		}
	}
	if(i<=m){        //处理剩余未排序的数据
		while(i<=m){
			T->data[k++] = L->data[i++];
		}
	}
	else{
		while(j<=n){
			T->data[k++] = L->data[j++];
		}
	}
}

void OneMergePass(OrderList *L,OrderList *T,int n,int h)	//一趟归并排序 
{
	int i = 1,k;
	while(i<n-2*h+1){    //n-2*h+1为数据最多可以分几组[2*h]
		Merge(L,T,i,i+h-1,i+2*h-1);
		i += 2*h;
	}
	if(i<n-h+1){    //此时剩余数据长度大于h但是小于2h,仍然进行一次Merge排序
		Merge(L,T,i,i+h-1,n);
	}
	else{        //此时剩余数据长度小于等于h,直接将剩余数据作为一组放到T中
		for(k=i;k<=n;k++)
			T->data[k] = L->data[k];
	}
}

void MergeSort(OrderList *L,OrderList *T)		//归并排序
{
	int len = L->length;
	int h = 1;
	int k = 0,i;
	while(h<len){
		k++;
		OneMergePass(L,T,len,h);    //L做排序表,T做辅助表
		h = 2*h;
		if(h<len){
			OneMergePass(T,L,len,h);    //T做排序表,L做辅助表
			h = 2*h;
			k++;
		}
	}
	if(k%2==0){        //当为偶数趟的时候,结果存储在L中，此时将结果转移到T中。
		for(i=1;i<=L->length;i++)
			T->data[i] = L->data[i];
	}
} 

int main()
{
	OrderList L,T;
	T.length = 10;
	InitMyOrderList(&L);
	MergeSort(&L,&T);
	OutPutMyOrderList(&T);
	return 0;
}