11-6.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 MergeSortDC(SeqList R,int low,int high)
{//用分治法对R[low..high]进行二路归并排序
       int mid;
       if(low<high){//区间长度大于1
          mid=(low+high)/2; //分解
          MergeSortDC(R,low,mid); //递归地对R[low..mid]排序
          MergeSortDC(R,mid+1,high); //递归地对R[mid+1..high]排序
          Merge(R,low,mid,high); //组合,将两个有序区归并为一个有序区
        }
}//MergeSortDC
void Initial(SeqList R)
{
	//初始化
}
void main()
{
	Seqlist R;
	Initial(R);
	MergeSort(R);
}