《排序实验报告.docx》由会员分享，可在线阅读，更多相关《排序实验报告.docx（28页珍藏版）》请在三一办公上搜索。
1、数据结构课程设计报告专业计算机科学与技术班级姓名学号指导教师起止时间2012.122013.1课程设计：排序综合一、任务描述排序综合任务：利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。要求：（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。二、问题分析1、功能分析分析设计课题的要求，要求编程实现以下功能：（1）排序表的建立一即创建顺序表;(2)顺序表的
2、排序一即直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序操作；(3)统计每一种排序方法的性能一即测试上机运行程序所花费的时间；2、数据对象分析数据信息：随机整数数据数量可以预先确定(20000以上)三、数据结构设计使用顺序表实现，有关定义如下：typedefintStatus;typedefintKeyType;设排序码为整型量typedefintInfoType;typedefStrUet定义被排序记录结构类型KeyTypekey;排序码InfoTypeOtherinfo;其它数据项RedType;typedefstructRedType*r;存储带排序记录的顺序表r作哨兵或缓冲区i
3、ntIength;顺序表的长度SqList;定义顺序表类型四、功能设计(一)主控菜单设计为实现通各种排序的功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。程序运行后，给出6个菜单项的内容和输入提示，如下：1 .直接插入排序2 .希尔排序3 .起泡排序4 .快速排序5 .简单选择排序0.退出系统(二)程序模块结构由课题要求可将程序划分为以下几个模块(即实现程序功能所需的函数)： 主控菜单项选择函数menu() 创建排序表函数lnitList_Sq() 对顺序表L进行直接插入排序函数Insertsortf) 希尔排序函数SheIISortO; 起泡排序函数Bubb
4、le_sort() 快速排序函数QSort() 简单选择排序函数SeIectSortO(三)函数调用关系程序的主要结构(函数调用关系)如下图所示。Menu()InitLiSJSq(L)Main()Insertsort(L)SheIISortOBubble_sort()QSort()SeIectSortO其中main()是主函数，它进行菜单驱动，根据选择项05调用相应的函数。main。函数使用for循环实现重复选择。其循环结构如下：for(;)(longstart,end;switch(menu()(case 1:printf(*直接插入排序*n);start=clock();Insertsor
5、t(L);end=clock();printf(,%dmsn,end-start);fp=fopen(D:直接插入排序.txt”Jw“);if(fp=NULL)打开文件失败(Printf(打开文件失败!n”)；函t；for(i=l;i=L.length;i+)fprintf(fp,%dzLri);fclose(fp);break;case 2:printf(*希尔排序*n);start=clock();ShellSOrt(L,an,14);end=clock();printf(,%dmsn,end-start);fp=fopen(D:希尔排序.txt7w);if(fp=NULL)打开文件失败(
6、Printf(打开文件失败!n)；exit(l);for(i=l;i=Llength;i+)fprintf(fp,%d,Lri);fclose(fp);break;case 3:printf(*起泡排序*n);start=clock();Bubble_sort(L);end=clock();printf(,%dmsnend-start);fp=fopen(D:起泡排序.txtw);if(fp=NULL)打开文件失败Prirrtf(打开文件失败!n”);exit(l);for(i=l;i=L.length;i+)fprintf(fpj,%d.ri);fclose(fp);break;case 4
7、:Printfr快速排序*n);start=clock();QSort(LzOzLIength);end=clock();printf(%dmsn,end-start);fp=fopen(,D:快速排序.tt,7w);if(fp=NULL)打开文件失败(Printv打开文件失败!n)；exit(l);)for(i=l;i=L.length;i+)fprintf(fpz,%dzLri);fclose(fp);break;printf（*简单选择排序*n）;start=clock();SeIectSort(L);end=clock();printf(,%dmsn,end-start);fp=fop
8、en(D:简单选择排序.txt,w);if(fp=NULL)打开文件失败(Printf(打开文件失败!n)；exit(l);for(i=l;i=Llength;i+)fprintf(fp,%d,Lri);fclose(fp);break;case0:printf(t退出!n);return;)(四)文件结构1、sort.h：顺序表相关的定义与函数声明2、sort.cpp：顺序表排序运算的实现3、menu.h：主菜单函数的声明4、menu.cpp：主菜单函数的实现5、mn.cpp：主函数（五）各函数的算法设计1、InitLisJSqO算法原理：数组指针r指示线性表的基址，length指示线性表的
9、当前长度，将随机生成的数赋给线性表，并生成相应文件。流程图：开始申请内存随机生成30000个数字生成文件Fp=NULL将顺序表打印到文件内终止程序关闭文件结束代码描述:StatusInitList_Sq(SqLiSt&L)构造一个线性表FILE*fp;1.r=(RedType*)malloc(LIST_INIT_SIZE*sizeof(RedType);if(!L.r)exit(OVERFLoW);存储分配失败IJength=30001;表长度为30001srand(unsigned)time(NULL);for(inti=l;i=L.length;i+)1.ri.key=rand()%300
10、01+l;fp=fopen(D:构造一个线性表.txt”Jw);if(fp=NULL)打开文件失败(Printf(打开文件失败!n)exit(l);)for(i=l;i=L.length;i+)fprintf(fpz%d,Lri);fclose(fp);returnOK;/lnitList_Sq算法的时间复杂度分析：0(n)2、InsertsortO算法原理：每步将一个待排序的对象，按其排序码大小，插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。在已形成的有序表中顺序查找,并在适当位置插入，把原来位置上的元素向后顺移。Oi=2iLlength否是1.ri.keyLri-l.k
11、ey否1二一YLrO=Lrij=i-l1.rO.keyLr0.key否是1.j+l=Lrjj-1.rj+l=LrOi+结束代码描述：voidInsertsortISqList&L)对顺序表L进行直接插入排序for(inti=2;i=L.length;i+)if(LT(Lri.keyzLri-l.key)需将L.ri插入有序表Lr=Lri;复制为“哨兵”，暂存for(intj=i-l;LT(L.rO.keyzL.rj.key);j-)1.rj+l=LrO;位置j指示了第一个keyLri.key的元素1.rj+l=LrO;将暂存在r中的记录插入到正确位置H算法的时间复杂度分析：0(n2)3、She
12、IIlnsertO分组、组内直接插入排序；2、组数逐次减小；3、组数=1,结束。流程图：开始i=dk+lKLIength否是1.ri.keyO)&(LT(L.r(O.keyzLrj.key)否1.rj+dk=Lrjj-=dk1.rj+dk=Lr0i+结束代码描述：voidShelllnsert(SqList&L,intdk)一趟Shell排序，dk为步长inti;for(i=dk+l;i0)&(LT(L.rO.keyzL.rj.key);j-=dk)1.rj+dk=Lr11;1.rj+dk=Lr0;)4、SheIISortO流程图：开始k=0ktShelllnsert(L,dltak)k+结束
13、代码描述：voidShellSort(SqList&LJntdltaJntt)SheIl排序,dlta。为增量序列,t为增量个数intk;for(k=0;kt;k+)Shelllnsert(Lzdltak);/SheIISort算法的时间复杂度分析：O(n(log2n)2)5Bubble_sort()算法原理：每趟不断将记录两两比较，若发现逆序，则交换两个记录，使排序码较小的元素逐渐从后部移向前部(就象水底的气泡一样逐渐向上冒)。c?n=L.lengthi=linflag=Oj=n-lj=i1.rj+l.keyLrU+lj-flag=Oi+结束代码描述：voidBubble_sort(SqLi
14、st&L)(RedTypex;intn;n=L.length;表长for(inti=l;i=i;j-)if(LT(Lrj+l.key,Lrj.key)(flag=l;有交换，置标志x=LrO;/LrjL.rj+l1.rj=LrD+l;1.rj+l=x;)if(flag=O)break;若无交换则可结束冒泡排序)算法的时间复杂度分析：O(n2)6Partition()算法原理：从n个待排记录中任取一个记录Ri作标准，调整序列中各个记录的位置，使得：排在ri前的记录排序码=ri.key排在ri后的排序码，该过程为一趟快速排序。这样就确定了Ri在序列中的最终位置，同时将序列分成两个子序列。流程图：开
15、始1.r0=L.rlowPivotkey=Lrlow.key1.owhigh否是low=pivotkey否-high1.rlowLrhighlowhigh&L.rlow.key=pivotkey否是+low1.rlowLrhigh1.rlow=Lr0returnlow结束代码描述：intPartition(SqList&L,intIowJnthigh)/*交换子表rlowhigh的记录，使枢轴记录到位，并返回其位置。返回时，在枢轴之前的记录排序码均不大于其排序码，之后的记录排序码均不小于其排序码。*/1.r0=L.rlow;以子表的首记录作为枢轴，放入r0单intpivotkey;PiVOtk
16、ey=L.rlow.key;取枢轴的排序码存入pivotkey变量while(lowhigh)从表的两端交替地向中间扫描RedType;RedTypet;while(low=pivotkey)-high;x=Lrlow;1.rlow=Lrhigh;1.mhigh=x;将比枢轴排序码小的记录交换到低端while(lowhigh&L,rlow.key=pivotkey)+low;t=Lrhigh;1.rhigh=Lrlow;1.rlow=t;将比枢轴排序码大的记录交换到高端)1.EoW=L.rO;枢轴记录到位returnIOw;返回枢轴记录所在位置/Partition7、QSort()算法原理：1
17、、对Partition()确定的两个子序列分别进行快速排序，则又可确定2个记录在序列中的最后位置，同时将序列分成4个子序列。2、重复直至每个序列的长度均为1时，全部记录排序完毕。1.owhightpivotloc=Partition(Lzlow,high)QSort(Lzlow,pivotloc-1)QSort(L,pivotloc+lzhigh)结束代码描述:VoidQSort(SqList&L,intlow,inthigh)对顺序表L中的子序列rlow.high作快速排序if(low1intpivotloc;pivotloc=Partition(Lzlow,high);一趟快排，将r分为二
18、QSort(L,low,PiVotloC-1);在左子区间进行递归快排，直到长度为1QSort(L,pivotloc+lzhigh);在右子区间进行递归快排，直到长度为1)算法的时间复杂度分析：O(nlogn)8、SeIectSortO算法原理：第1趟:从RnrR向中选取最小值,与Rm交换；第2趟：从R2Rn中选取最小值,与R交换;第i趟:从RiRn中选取最小值,与Ri交换;第n1趟：从Rn-lRn中选取最小值,与Rn1交换.共通过nl趟,得到一个按排序码从小到大排列的有序序列EJ流程图：开始iLlength否j=i+lj=Llength否1.rj.keyLrk.key)否lrLriLrj+j
19、代码描述：voidSelectSortISqList&L)对顺序表进行简单选择排序RedTypex;for(inti=l;iL.length;+i)在Lri.Llength中选择key最小的记录intk=i;for(intj=i+l;j=L.length;j+)if(LT(Lrj.key,Lrk.key)k=j;if(k!=i)=Lri;1.ri=Lrj;1.rj=x;)/SeIectSort算法的时间复杂度分析：算法的改进方法（这部分可以选择）：五、测试数据和结果1、测试数据随机产生30000个数2、测试结果本程序在VC+环境下实现，下面是对以上测试数据的运行结果。(1)主菜单显示如下：*F
20、:播康结梅实善searchDebugsezrch.exe直希fe性?123450(2)建立通信录单链表：F:焰searchDebugsearch.exe-12 3 4 5 0序 Ltr序 LLr 请选择0-5s:直接插入排序2666ms排序序LEr序LEr入赛系速盘 直希起修展12 3 4 5 0请选择05：F=SsearchDebugsearch.ee=N=N序序.=插系_www? 接尔泡速a 直希起请选择0-5.H快速排序请选择05： F:?5searchDebugsearch.exe12ms排序WW fl 插舞牌速 a IaIK起贽用WflWfl入CBUtLtIXnLU-，*、=p?;系
21、直希起搂醺请选择05:简单选择排序-3865ns排序 聚 一,mJLF APA，A FA -,XXJh， 拉*-,速 直希起n请选择05：序FFfl序th.序trr珥入茯插系速电直希起修昌123450请选择05：输入错误，重选。一5：序 LrF ,U序系 标尔泡速a- 暴起12 3 4 5 0请选择05：；简单选择排序3865ns排序序 hrr序 Ltl入象 UmlkFnrlr,u.yh T 速至 直希起快H12 3 4 5 0请选择0-5：0退出！Pressanykeytocontinue六、结束语本设计完成了课题要求的任务，较熟练地运用了顺序表来解决问题，实现了顺序表的各种排序的基本算法，设计了较便捷的操作界面。
