欢迎来到天天文库
浏览记录
ID:38830468
大小:79.66 KB
页数:3页
时间:2019-06-20
《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("");}测试结果
此文档下载收益归作者所有