排序实验报告

《数据构造》课程设计报告专业计算机科学与技术班级姓名学号指导教师起止时间.12~.1课程设计：排序综合任务描述排序综合任务：运用随机函数产生n个随机整数（0以上），对这些数进行多个办法进行排序。规定：（1）最少采用三种办法实现上述问题求解（提示，可采用的办法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的成果保存在不同的文献中。（2）统计每一种排序办法的性能（以上机运行程序所耗费的时间为准进行对比），找出其中两种较快的办法。二、问题分析1、功效分析分析设计课题的规定，规定编程实现下列功效：（1）排序表的建立—即创立次序表；（2）次序表的排序—即直接插入排序、希尔排序、起泡排序、快速排序、简朴选择排序操作；（3）统计每一种排序办法的性能—即测试上机运行程序所耗费的时间；2、数据对象分析数据信息：随机整数数据数量能够预先拟定（0以上）数据构造设计使用次序表实现，有关定义以下：typedefintStatus;typedefintKeyType;//设排序码为整型量typedefintInfoType;typedefstruct{//定义被排序统计构造类型 KeyTypekey;//排序码I nfoTypeotherinfo;//其它数据项}RedType;typedefstruct{ RedType*r;//存储带排序统计的次序表//r[0]作哨兵或缓冲区 intlength;//次序表的长度}SqList;//定义次序表类型四、功效设计（一）主控菜单设计为实现通多个排序的功效，首先设计一种含有多个菜单项的主控菜单程序，然后再为这些菜单项配上对应的功效。程序运行后，给出6个菜单项的内容和输入提示，以下：1.直接插入排序2.希尔排序3.起泡排序4.快速排序5.简朴选择排序0.退出系统（二）程序模块构造由课题规定可将程序划分为下列几个模块（即实现程序功效所需的函数）：主控菜单选函数menu()创立排序表函数InitList_Sq()对次序表L进行直接插入排序函数Insertsort()希尔排序函数ShellSort();起泡排序函数Bubble_sort()快速排序函数QSort()简朴选择排序函数SelectSort()（三）函数调用关系程序的重要构造（函数调用关系）以下图所示。Menu() InitList_Sq(L) Main()Insertsort(L) ShellSort() Bubble_sort() QSort() SelectSort()其中main()是主函数，它进行菜单驱动，根据选择项0~5调用对应的函数。main()函数使用for循环实现重复选择。其循环构造以下：for(;;) { longstart,end; switch(menu()) { case1: printf("*直接插入排序*\n"); start=clock(); Insertsort(L); end=clock(); printf("%dms\n",end-start); fp=fopen("D:直接插入排序.txt","w"); if(fp==NULL)//打开文献失败 { printf("打开文献失败!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case2: printf("*希尔排序*\n"); start=clock(); ShellSort(L,an,14); end=clock(); printf("%dms\n",end-start); fp=fopen("D:希尔排序.txt","w"); if(fp==NULL)//打开文献失败 { printf("打开文献失败!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case3: printf("*起泡排序*\n"); start=clock(); Bubble_sort(L); end=clock(); printf("%dms\n",end-start); fp=fopen("D:起泡排序.txt","w"); if(fp==NULL)//打开文献失败 { printf("打开文献失败!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case4: printf("*快速排序*\n"); start=clock(); QSort(L,0,L.length); end=clock(); printf("%dms\n",end-start); fp=fopen("D:快速排序.txt","w"); if(fp==NULL)//打开文献失败 { printf("打开文献失败!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case5: printf("*简朴选择排序*\n"); start=clock(); SelectSort(L); end=clock(); printf("%dms\n",end-start); fp=fopen("D:简朴选择排序.txt","w"); if(fp==NULL)//打开文献失败 { printf("打开文献失败!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case0: printf("\t退出！\n"); return; } }（四）文献构造1、sort.h：次序表有关的定义与函数声明2、sort.cpp：次序表排序运算的实现3、menu.h：主菜单函数的声明4、menu.cpp：主菜单函数的实现5、mn.cpp：主函数（五）各函数的算法设计1、InitList_Sq()算法原理：数组指针r批示线性表的基址，length批示线性表的现在长度，将随机生成的数赋给线性表，并生成对应文献。流程图： 开始申请内存随机生成30000个数字生成文献 Fp=NULL 将次序表打印到文献内终止程序关闭文献结束 代码描述：StatusInitList_Sq(SqList&L){//构造一种线性表 FILE*fp; L.r=(RedType*)malloc(LIST_INIT_SIZE*sizeof(RedType)); if(!L.r)exit(OVERFLOW);//存储分派失败 L.length=30001;//表长度为30001 srand((unsigned)time(NULL)); for(inti=1;i<=L.length;i++) L.r[i].key=rand()%30001+1; fp=fopen("D:构造一种线性表.txt","w"); if(fp==NULL)//打开文献失败 { printf("打开文献失败!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); returnOK;}//InitList_Sq算法的时间复杂度分析：O(n)Insertsort()算法原理：每步将一种待排序的对象，按其排序码大小，插入到前面已经排好序的一组对象的适宜位置上，直到对象全部插入为止。在已形成的有序表中次序查找，并在适宜位置插入，把原来位置上的元素向后顺移。流程图： 开始i=2i<L.length否 是L.r[i].key<L.r[i-1].key否是L.r[0]=L.r[i]j=i-1L.r[0].key<L.r[j].key否是L.[j+1]=L.r[j]j--L.r[j+1]=L.r[0]i++结束代码描述：voidInsertsort(SqList&L)//对次序表L进行直接插入排序{for(inti=2;i<=L.length;i++)if(LT(L.r[i].key,L.r[i-1].key))//需将L.r[i]插入有序表{L.r[0]=L.r[i];//复制为“哨兵”，暂存for(intj=i-1;LT(L.r[0].key,L.r[j].key);j--)L.r[j+1]=L.r[j];//位置j批示了第一种key≤L.r[i].key的元素L.r[j+1]=L.r[0];//将暂存在r[0]中的统计插入到对的位置}}算法的时间复杂度分析：O（n2）3、ShellInsert()算法原理：1、分组、组内直接插入排序；2、组数逐次减小；3、组数=1，结束。流程图： 开始i=dk+1i<L.length 否是L.r[i].key<L.r[i-dk].key 否是L.r[0]=L.r[i]j=i-dk(j>0)&&(LT(L.r[0].key,L.r[j].key) 否 是L.r[j+dk]=L.r[j]j-=dkL.r[j+dk]=L.r[0]i++结束代码描述：voidShellInsert(SqList&L,intdk){//一趟Shell排序，dk为步长 inti; for(i=dk+1;i<=L.length;i++) { if(LT(L.r[i].key,L.r[i-dk].key)){ L.r[0]=L.r[i]; intj; for(j=i-dk;(j>0)&&(LT(L.r[0].key,L.r[j].key));j-=dk) L.r[j+dk]=L.r[j]; L.r[j+dk]=L.r[0];}}}ShellSort()流程图： 开始k=0k<tShellInsert(L,dlta[k])k++结束代码描述：voidShellSort(SqList&L,intdlta[],intt){//Shell排序，dlta[]为增量序列，t为增量个数 intk; for(k=0;k<t;k++)ShellInsert(L,dlta[k]);}//ShellSort算法的时间复杂度分析：O(n(㏒2n)2)Bubble_sort()算法原理：每趟不停将统计两两比较，若发现逆序，则交换两个统计，使排序码较小的元素逐步从后部移向前部（就象水底的气泡同样逐步向上冒）。流程图： 开始n=L.lengthi=1i<nflag=0j=n-1j<=iL.r[j+1].key<L.r[j].key)flag=1L.r[j]←→L.r[j+1]j--flag=0i++结束代码描述：voidBubble_sort(SqList&L){RedTypex; intn;n=L.length;//表长for(inti=1;i<n;i++){intflag=0;//进入循环，清标志for(intj=n-1;j>=i;j--)if(LT(L.r[j+1].key,L.r[j].key)){ flag=1;//有交换，置标志x=L.r[j];//L.r[j]←→L.r[j+1]L.r[j]=L.r[j+1];L.r[j+1]=x;}if(flag==0)break;//若无交换则可结束冒泡排序}}算法的时间复杂度分析：O(n2)6、Partition()算法原理：从n个待排统计中任取一种统计Ri作原则，调节序列中各个统计的位置，使得：排在ri前的统计排序码<=ri.key排在ri后的排序码，该过程为一趟快速排序。这样就拟定了Ri在序列中的最后位置，同时将序列分成两个子序列。流程图： 开始L.r[0]=L.r[low]Pivotkey=L.r[low].keyLow<high否是low<high&&L.r[high].key>=pivotkey否是--highL.r[low]←→L.r[high]low<high&&L.r[low].key<=pivotkey否是++lowL.r[low]←→L.r[high]L.r[low]=L.r[0]returnlow结束代码描述：intPartition(SqList&L,intlow,inthigh){/*交换子表r[low…high]的统计，使枢轴统计到位，并返回其位置。返回时，在枢轴之前的统计排序码均不不不大于其排序码，之后的统计排序码均不不大于其排序码。*/L.r[0]=L.r[low];//以子表的首统计作为枢轴，放入r[0]单 intpivotkey;pivotkey=L.r[low].key;//取枢轴的排序码存入pivotkey变量while(low<high){ //从表的两端交替地向中间扫描 RedTypex; RedTypet; while(low<high&&L.r[high].key>=pivotkey)--high; x=L.r[low]; L.r[low]=L.r[high]; L.r[high]=x;//将比枢轴排序码小的统计交换到低端 while(low<high&&L.r[low].key<=pivotkey)++low; t=L.r[high]; L.r[high]=L.r[low]; L.r[low]=t;//将比枢轴排序码大的统计交换到高端 }L.r[low]=L.r[0];//枢轴统计到位returnlow;//返回枢轴统计所在位置}//Partition7、QSort()算法原理：1、对Partition()拟定的两个子序列分别进行快速排序，则又可拟定2个统计在序列中的最后位置，同时将序列分成4个子序列。2、重复直至每个序列的长度均为1时，全部统计排序完毕。流程图： 开始Low<hightpivotloc=Partition(L,low,high) QSort(L,low,pivotloc-1)QSort(L,pivotloc+1,high)结束代码描述：voidQSort(SqList&L,intlow,inthigh){//对次序表L中的子序列r[low…high]作快速排序if(low<high){//长度>1 intpivotloc;pivotloc=Partition(L,low,high);//一趟快排，将r[]一分为二QSort(L,low,pivotloc-1); //在左子区间进行递归快排，直到长度为1QSort(L,pivotloc+1,high);//在右子区间进行递归快排，直到长度为1}}算法的时间复杂度分析：O(nlogn)8、SelectSort()算法原理：第1趟：从R[1]~R[n]中选用最小值,与R[1]交换;第2趟：从R[2]~R[n]中选用最小值,与R[2]交换; ………第i趟：从