数据结构课程设计—综合排序

东华理工大学1东华理工大学课程设计报告课程设计题目：综合排序的设计学生姓名：何杨班级：1223202专业：信息与计算科学指导教师：郭树蕻2014年12月13日东华理工大学2目录摘要..............................................................2一、题目的内容及要求-------------------------------------------------------------------------------4二、需求分析--------------------------------------------------------------------------------------------4三、概要设计--------------------------------------------------------------------------------------------5四、四种排序源代码详细设计----------------------------------------------------------------------5五、程序输出的结果---------------------------------------------------------------------------------10六、运行结果及分析---------------------------------------------------------------------------------12七、收获及体会---------------------------------------------------------------------------------------13八、参考文献-------------------------------------------------------------------------------------------14东华理工大学3摘要数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有其特点。对排序算法比较的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。关键字：数据结构；算法比较；比较次数；时间复杂度东华理工大学4一、题目的内容及要求排序综合利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：(1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。(2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。(3)如果采用4种或4种以上的方法者，可适当加分。二、需求分析2.1问题描述此次的任务要求是输入20000个以上的随机整数，对这些数进行多种方法进行排序。（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。约束：程序可由用户自行设定排序数的个数，但排序数具体值需要由计算机生成，然后用三种以上的排序方法对随机数组进行排序，每一种排序方法执行后需统计出数据移动次数以判断排序方法的对比随机数组的执行优劣性。另：用户自行算出每一种排序方法的时间复杂度与空间复杂度。2.2基本要求2.2.1输入的形式和输入值的范围；设定的随机数据的范围为20000以上，用户自定义随机数的个数n，随机数的数据类型均为整形。2.2.2输出的形式；程序是以一个完整的有序数组来进行输出。2.2.3程序所达到的功能：将一个无序数组进行排序随机生成20000以上个随机整数，对这些数进行多种方法进行排序。分别采用以下方法实现上述问题求解（可采用的方法有简单排序、希尔排序、冒泡排序、快速排序这四种排序方法）。东华理工大学5三、概要设计3.1可排序表的抽象数据类型定义：typedefintKeyType;//关键字为整型typedefintOtherType;//关键字为整型typedefstruct{KeyTypekey;//关键字为KeyType型OtherTypeother_data;}RecordType;//定义一个RecordType型结构体，存放关键字voidquicksort(RecordTypea[],intleft,intright)//快速排序voidbubbleSort(RecordTypea[],intlength)//冒泡排序voidshellSort(RecordTypea[],intn)//希尔排序voidBinSort(RecordTyper[],intlength)//折半插入排序voidmain()//主函数运行入口四、四种排序源代码详细设计：4.1快速排序模块：voidquicksort(RecordTypea[],intleft,intright){RecordTypet;inti,j,temp;if(leftright)return;temp=a[left].key;i=left;j=right;while(i!=j){while(a[j].key=temp&&ij)j--;while(a[i].key=temp&&ij)东华理工大学6i++;if(ij){t=a[i];a[i]=a[j];a[j]=t;}}a[left]=a[i];a[i].key=temp;quicksort(a,left,i-1);//继续处理左边的，这是一个递归的过程quicksort(a,i+1,right);//继续处理右边的，这是一个递归的过程}/*快速排序算法*/4.2冒泡排序模块：//此处是一次冒泡排序过程，在主函数中会通过循环调用此冒泡函数过程voidbubbleSort(RecordTypea[],intlength){inti,temp;for(i=1;ilength;i++){if(a[i].keya[i+1].key){temp=a[i].key;a[i].key=a[i+1].key;a[i+1].key=temp;}}}/*冒泡排序算法*/4.3希尔排序模块：voidshellSort(RecordTypea[],intn){inti,j,temp;intgap=0;while(gap=n)//根据待排序的个数生成合适的步长，gap是步长{gap=gap*3+1;东华理工大学7}while(gap0){for(i=gap;in;i++){j=i-gap;temp=a[i+1].key;while((j=0)&&(a[j+1].keytemp)){a[j+gap+1].key=a[j+1].key;j=j-gap;}a[j+gap+1].key=temp;}gap=(gap-1)/3;}}4.4希尔折半插入排序模块：/*折半插入排序法*/voidBinSort(RecordTyper[],intlength)/*对记录数组r进行折半插入排序，length为数组的长度*/{inti,j;RecordTypex;intlow,high,mid;for(i=2;i=length;++i){x=r[i];low=1;high=i-1;while(low=high)/*确定插入位置*/{mid=(low+high)/2;if(x.keyr[mid].key)high=mid-1;elselow=mid+1;}for(j=i-1;j=low;--j)r[j+1]=r[j];/*记录依次向后移动*/r[low]=x;/*插入记录*/}}/*BinSort*/东华理工大学84.5主函数模块：voidmain(){intn,i,j,t;charb;boolq=false;RecordTypea[40000];while(1){printf(\n\n);printf(**************综合排序*****************************\n\n);printf(*********************菜单***************************\n\n);printf(*=======================================================*\n);printf(*1.读取待排序长度*\n);printf(*2.产生随机数并输出*\n);printf(*3.采用快速排序法排序*\n);printf(*4.采用冒泡排序法排序*\n);printf(*5.采用希尔排序法排序*\n);printf(*6.采用折半插入排序法排序*\n);printf(*7.输出*\n);printf(*0.退出系统*\n);printf(*-------------------------------------------------------*\n);printf();b=getch();switch(b){case'1':printf(%c\n,b);printf(请输入待排序记录的长度：);scanf(%d,&n);break;东华理工大学9case'2':printf(%c\n,b);srand((unsigned)time(NULL));printf(下面随机生成%d个数字存储在数组中\n,n);for(i=1;i=n;i++){a[i].key=rand()%20000;printf(%d\t,a[i].key);if(i%100==0)printf(\n);}printf(\n);break;case'3':printf(%c\n,b);printf(\n-----------------快速排序结束-------------------\n\n);quicksort(a,1,n);q=true;break;case'4':printf(%c\n,b);for(i=0;in-1;i++){bubbleSort(a,n-i);}printf(\n-----------------冒泡排序结束-------------------\n\n);q=true;break;case'5':printf(%c\n,b);printf(\n-----------------希尔排序结束-------------------\n\n);shellSort(a,n);q=true;break;case'6':printf(%c\n,b);BinSort(a,n);printf(\n-----------------折半插入排序结束-------------------\n\n)