11-5.c

这些是数据结构结构的经典实现算法

#include  < stdio.h>
#define n 100 //假设的文件长度,即待排序的记录数目
#define MAX_SIZE  1000
typedef int KeyType; //假设的关键字类型
typedef struct{ //记录类型
   	 	KeyType key; //关键字项
    	//其它数据项,类型InfoType依赖于具体应用而定义
}RecType;
typedef RecType SeqList[n];
typedef  struct {
	int key;
	/*其他数据域*/
}element;
void merge(element list[],element sorted[ ],int i,int m,  int n)
{	/* 合并两个已排好的记录list[i], ..., list[m],和list[m+1], ..., list[n]*/
    int  j, k, t;
    j = m+1; 
    k = i;      
    while ( i <= m && j <= n){
        if ( list[i].key <= list[j].key)
            sorted[k++] = list[i++];
        else 
            sorted[k++] = list[j++];
    }
    if (i>m)
        for(t = j; t <= n; t++)
           sorted[k+t-j] = list[t];
    else
		for (t = i; t <= m; t++)
			sorted[k+t-i] = list[t];
}
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时,则剩余一个子文件轮空,无须归并
} //MergePass二路归并排序算法
void MergeSort(SeqList R)
{//采用自底向上的方法,对R[1..n]进行二路归并排序
     int length;
     for(1ength=1;length<n;length*=2) //做  趟归并
        MergePass(R,length); //有序段长度≥n时终止
}
void Initial(SeqList R)
{
	//初始化
}
void main()
{
	Seqlist R;
	Initial(R);
	MergeSort(R);
}