归并排序

( Merging Sort )就是将两个或两个以上的有序表合并成一-个有序表的过程。将两个有序表合并成个有序表的过程称为2-路归并，2-路归并最为简单和常用。

算法思想：

假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为1的有序序列为止。

书上的例子：

时间复杂度

O(n$lo{g}_2$n)

空间复杂度

O(n)

算法特点：

1）是稳定排序。
2）可用于链式结构，且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈。

完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100  //顺序表最大容量，可以自行加大 

typedef struct 
{
	int key;//关键字项 
	char *otherinfo;//其他数据项 
}ElemType;//记录类型 
typedef struct
{
	ElemType Data[MAXSIZE+1];//静态顺序表的数据域，这里Data[0]为空闲或者为哨兵单元 
	int length;//顺序表的长度 
}SqList;//顺序表 

void InitList(SqList &L)//顺序表的初始化 
{
	L.length = 0;//使顺序表长度归0，便是顺序表的初始化 
}

void CreateList(SqList &L)//顺序表的创建 
{
	printf("请输入："); 
	while(1)//建立一个死循环，循环终止条件是按了enter键 
	{
		L.length++;//顺序表长度加一 
		if(L.length>MAXSIZE)//判断是否超出最大容纳量 
		{
			printf("顺序表已满！\n");
			return ;
		}
		scanf("%d",&L.Data[L.length].key);//顺序表数据的输入 
		if(getchar() == '\n')//循环终止条件 
			break;
	}
}

void InputList(SqList L)//顺序表的输出 
{
	int i;//记录次数 
	if(L.length == 0)//判断顺序表是否为空 ，若为空结束该函数 
	{
		printf("顺序表是空的！\n");
		return ;
	}
	printf("打印为：");
	for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据 
		printf("%d ",L.Data[i].key);	
}

void Merge(ElemType R[],int low,int mid,int high)//将两个有序表R[low…mid]和R[mid+1…high]归并为有序表 
{
	ElemType T[MAXSIZE+1];//申请一个辅助表 
	int i,j,k;
	i = low;
	j = mid+1;
	for(k=low;k<=high;k++)//辅助表R[]中要排序的两个子表的数据到表T[]中 
		T[k] = R[k];
	k = low;
	while(i<=mid&&j<=high)//将R中记录由小到大地并入T中 
	{
		if(T[i].key <= T[j].key)
			R[k] = T[i++];
		else
			R[k] = T[j++];
		k++;
	}
	while(i<=mid)//将剩余的T[i…mid]复制到R中 
		R[k++] = T[i++];
	while(j<=high)//将剩余的T[j…high]复制到R中 
		R[k++] = T[j++];
	
}
void MSort(ElemType R[],int low,int high)//利用递归将R[low…high]归并排序 
{
	if(low<high)//递归终止条件 
	{
		int mid = (low+high)/2;//将当前序列一分为二,求出分裂点mid 
		MSort(R,low,mid);//对子序列R[low…mid]递归归并排序 
		MSort(R,mid+1,high);//对子序列R[mid+1…high]递归归并排序 
		Merge(R,low,mid,high);//将R[low…mid]和R[mid+1…high]归并 
	}
}
void MergeSort(SqList &L)//对顺序表L做归并排序 
{
	MSort(L.Data,1,L.length);
}

int main()
{
	SqList L;
	InitList(L);//初始化顺序表 
	CreateList(L);//创建顺序表 
	MergeSort(L);//归并排序 
	InputList(L);//打印排序后结果 
	return 0;
}

（完）