排序实验报告.docx

数据结构课程设计报告专业计算机科学与技术班级姓名学号指导教师起止时间2012.122013.1课程设计：排序综合一、任务描述排序综合任务：利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。要求：（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。二、问题分析1、功能分析分析设计课题的要求，要求编程实现以下功能：（1）排序表的建立一即创建顺序表;(2)顺序表的排序一即直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序操作；(3)统计每一种排序方法的性能一即测试上机运行程序所花费的时间；2、数据对象分析数据信息：随机整数数据数量可以预先确定(20000以上)三、数据结构设计使用顺序表实现，有关定义如下：typedefintStatus;typedefintKeyType;设排序码为整型量typedefintInfoType;typedefStrUet定义被排序记录结构类型KeyTypekey;排序码InfoTypeOtherinfo;其它数据项RedType;typedefstructRedType*r;存储带排序记录的顺序表r作哨兵或缓冲区intIength;顺序表的长度SqList;定义顺序表类型四、功能设计(一)主控菜单设计为实现通各种排序的功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。程序运行后，给出6个菜单项的内容和输入提示，如下：1 .直接插入排序2 .希尔排序3 .起泡排序4 .快速排序5 .简单选择排序0.退出系统(二)程序模块结构由课题要求可将程序划分为以下几个模块(即实现程序功能所需的函数)： 主控菜单项选择函数menu() 创建排序表函数lnitList_Sq() 对顺序表L进行直接插入排序函数Insertsortf) 希尔排序函数SheIISortO; 起泡排序函数Bubble_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();Insertsort(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,"%d"zLri);fclose(fp);break;case 2:printf('*希尔排序*n");start=clock();ShellSOrt(L,an,14);end=clock();printf(',%dmsn,end-start);fp=fopen("D:希尔排序.txt'7'w");if(fp=NULL)打开文件失败(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(',%dmsn'end-start);fp=fopen("D:起泡排序.txt"'w");if(fp=NULL)打开文件失败Prirrtf("打开文件失败!n”);exit(l);for(i=l;i<=L.length;i+)fprintf(fpj,%d".ri);fclose(fp);break;case 4:Printfr快速排序*n");start=clock();QSort(LzOzLIength);end=clock();printf("%dmsn,end-start);fp=fopen(',D:快速排序.t×t,7'w");if(fp=NULL)打开文件失败(Printv打开文件失败!n")；exit(l);)for(i=l;i<=L.length;i+)fprintf(fpz,%d"zLri);fclose(fp);break;printf（'*简单选择排序*n"）;start=clock();SeIectSort(L);end=clock();printf(',%dmsn,end-start);fp=fopen("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指示线性表的当前长度，将随机生成的数赋给线性表，并生成相应文件。流程图：开始申请内存随机生成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()%30001+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=2i<Llength否是1.ri.key<Lri-l.key否1二一YLrO=Lrij=i-l1.rO.key<Lr0.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指示了第一个key<Lri.key的元素1.rj+l=LrO;将暂存在r中的记录插入到正确位置H算法的时间复杂度分析：0(n2)3、SheIIlnsertO分组、组内直接插入排序；2、组数逐次减小；3、组数=1,结束。流程图：开始i=dk+lKLIength否是1.ri.key<Lri-dk.key否是1.rO=Lrij=i-dk(j>O)&&(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;i<=L.length;i+)(if(LT(Lri.key,L.ri-dk.key)(1.r0=Lri;intj;for(j=i-dk;(j>0)&&(LT(L.rO.keyzL.rj.key);j-=dk)1.rj+dk=Lr11;1.rj+dk=Lr0;)4、SheIISortO流程图：开始k=0k<tShelllnsert(L,dltak)k+结束代码描述：voidShellSort(SqList&LJntdltaJntt)SheIl排序,dlta。为增量序列,t为增量个数intk;for(k=0;k<t;k+)Shelllnsert(Lzdltak);/SheIISort算法的时间复杂度分析：O(n(log2n)2)5Bubble_sort()算法原理：每趟不断将记录两两比较，若发现逆序，则交换两个记录，使排序码较小的元素逐渐从后部移向前部(就象水底的气泡一样逐渐向上冒)。c?n=L.lengthi=li<nflag=Oj=n-lj<=i1.rj+l.key<Lrj.key)flag=l1.rj÷->LrU+lj-flag=Oi+结束代码描述：voidBubble_sort(SqList&L)(RedTypex;intn;n=L.length;表长for(inti=l;i<n;i+)intflag=。;进入循环，清标志for(intj=n-l;j>=i;j-)if(