C语言版数据结构归并排序

《C语言版数据结构归并排序》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、归并排序详细设计#include#include#include#defineMax_Size500typedefintKeyType;typedefintOtherType;typedefstruct{KeyTypekey;OtherTypeother_data;}RecordType;voidMerge(RecordTyper1[],intlow,intmid,inthigh,RecordTyper2[])/*已知r1[low..mid]和r1[mid+1..high]分别按关键字有序排列，将它们合并成一个有序序列，存放在r2[

2、low..high]*/{intj,k;for(j=mid+1,k=low;low<=mid&&j<=high;++k)//将ri中的纪律由小到大的并入r2中{if(r1[low].key<=r1[j].key)r2[k]=r1[low++];elser2[k]=r1[j++];}while(low<=mid)//将剩余的ri[low..mid]复制到r2中r2[k++]=r1[low++];while(j<=high)r2[k++]=r1[j++];//将剩余的ri[j..mid]复制到r2中}/*Merge*/voidMSort(RecordTyper1[],intlow,inth

3、igh,RecordTyper3[])/*r1[low..high]经过排序后放在r3[low..high]中，r2[low..high]为辅助空间*/{intmid;RecordTyper4[500];//开设用于存放归并排序中间结果的辅助空间if(low==high)r3[low]=r1[low];else{mid=(low+high)/2;//将r1[low...high]平均分为r1[low..mid]和r1[mid+1..high]MSort(r1,low,mid,r4);//递归将r1[low..mid]归并为有序的r3[low..mid]MSort(r1,mid+1,hi

4、gh,r4);//递归将r1[mid+1..high]归并为有序的r3[mid+1..high]Merge(r4,low,mid,high,r3);//递归将r4[low..mid]和r4[mid+1..high]归并为有序的r3[low..high]}}/*MSort*/voidmain(){inti;RecordTyper[Max_Size];intlen;printf("请输入待排序记录的长度(<500):");scanf("%d",&len);srand((unsigned)time(NULL));for(i=1;i<=len;i++)r[i].key=rand();print

5、f("待排序记录:");for(i=1;i<=len;i++)printf("%6d",r[i].key);printf("");MSort(r,1,len,r);printf("排序后的记录:");for(i=1;i<=len;i++)printf("%6d",r[i].key);printf("");}测试结果