数据结构课程设计排序算法时间性能的分析

《数据结构》课程设计报告目录1需求分析....................................................................................................................11.1问题描述.........................................................................................................11.2设计内容.........................................................................................................12概要设计.....................................................................................................................22.1原始数据.........................................................................................................22.2程序的流程.....................................................................................................22.3总体设计图.....................................................................................................33详细设计和编码.........................................................................................................43.1算法基本思想.................................................................................................43.2算法描述.........................................................................................................43.3算法设计.........................................................................................................53.4算法时间分析..................................................................................................84测试结果.....................................................................................................................95小结.............................................................................................................................9参考文献...............................................................................................................10附录：程序源代码......................................................................................................10《数据结构》课程设计报告11需求分析1.1问题描述(1)输入的形式和输入值的范围：本程序要求实现各种算法的时间性能的比较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。用户输入随机数的个数n，然后调用随机事件函数产生n个随机数，对这些随机数进行排序。于是数据为整数。(2)输出的形式：输出在各种数目的随机数下，各种排序算法所用的时较次数。(3)程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。（4）测试数据。1.2设计内容对各种排序方法（快速排序、堆排序、希尔排序、冒泡排序、归并排序）的时间性能进行比较。（1）设计并实现上述各种排序算法；（2）在排序中实现比较时间性能；（3）在输入中分别调用上述排序算法，并比较时间性能。《数据结构》课程设计报告22概要设计2.1原始数据1.抽象数据类型ADTList数据对象D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}基本操作virtualvoidclear()=0;boolinsert(constElem&)=0;boolappend(constElem&)=0;lboolremove(Elem&)=0;voidsetStart()=0;voidsetEnd()=0;voidprev()=0;voidnext()=0;intleftLength()const=0;intrightLength()const=0;boolsetPos(intpos)=0;boolgetValue(Elem&)const=0;voidprint()const=0;2.2程序的流程（1）输入模块：输入要排序的数的数量n。（2）处理模块：系统产生n个随机数，对随机数进行排序。（3）输出模块：将排序的结果输出。《数据结构》课程设计报告32.3总体设计图图1主程序堆排序快速排序冒泡排序希尔排序归并排序输出整理排序数据，作出分析。输入数据主程序冒泡排序快速排序堆排序希尔排序归并排序《数据结构》课程设计报告43详细设计和编码3.1算法基本思想1.随机数的产生：利用srand()产生随机数。2.快速排序：选定一记录R，将所有其他记录关键字'K与记录R的关键字K比较,若KK'则将记录换至R之前,若KK'则将记录换至R之后，继续对R前后两部分记录进行快速排序，直至排序范围为1。3.希尔排序：将序列分割成若干子序列分别进行直接插入排序，待序列记录基本有序时再对整体进行一次直接插入排序。4.冒泡排序：比较并交换相邻的元素对，直到所有元素都被放到正确的地方为止。5.归并排序：将两个或者多个有序表归并成一个有序表。6.堆排序：首先将数组转化为一个满足堆定义的序列，然后将堆顶的最大元素取出，再将剩下的数排成堆，再取堆顶数值，…。如此下去，直到堆为空。到最后结束时，就排出了一个由小到大排列的数组。3.2算法描述（1）快速排序是对起泡排序的一种改进。它的基本思想是：通过一趟排序将待排记录分别分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字大小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。（2）堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或大于）它的父结点。只需一记录大小的辅助空间，每个待排序的记录仅占用一个存储空间。它的思想是：先是对堆做比较，左子数小于本数，右子数大于本数，然后不停比较、交换，最后达到整个数组的排序。《数据结构》课程设计报告5（3）希尔排序它又称“缩小增量排序”，又是一种属插入排序类的方法，但在时间效率上有很大改进。它的思想是：先把数组分成等长的两个数组，用r[i]与r[n/2+i]比较小的在前，大的在后，然后在一刚刚两两一组的两组做比较，就这样，每次比较，每组数的个数都是上一次的两倍，最后完成整个数组的排序。（4）冒泡排序它是一种“交换”进行排序的方法之中最简单的一种。它的思想是：相邻的两个元素进行比较，将小的调到前面，大的调到后面。（5）归并排序“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。它的算法思想是：先把数组对半分多次，直到每组只有两个数据时，进行比较、排序，然后再两两合并，最后做到整个数组的排序完成。3.3算法设计（1）产生随机数：直接调用函数srand(),以时间作为随机种子进行选择，并把随机数装入数组中。unsignedlongint*Sort::setRan(unsignedlongintnum){unsignedlongint*ra;ra=(unsignedlongint*)malloc(num*sizeof(unsignedlongint));srand(time(NULL));for(unsignedlongintm=0;mnum;m++){ra[m]=rand();}coutendl;returnra;}（2）快速排序：要实现快速排序首先选择一个轴值，这里选取数组第一个为轴值。定义两个标识low,high。high标识最后一个元素的位置，从后向前，将关键字与轴值比较，直至遇到小于轴值的关键字，前移，low标识在第二个元素的《数据结构》课程设计报告6位置，从前向后，将关键字与轴值比较，直至遇到大于轴值的关键字，后移。当low,high相遇后第一趟排序结束。调整数列，轴值左边的为比轴值小的，右边为比轴值大的。对轴值左边（即low到pivotkey-1的数）和右边的子列（pivotkey+1到high的数）分别进行上述递归快速排序，直到范围为1结束。intpartition(inta[],intlow,inthigh){//快速排序中的一趟intpivotkey;//作为枢轴来使用pivotkey=a[low];while(lowhigh){while(lowhigh&&a[high]=pivotkey)--high;a[low]=a[high];while(lowhigh&&a[low]=pivotkey)++low;a[high]=a[low];}a[low]=pivotkey;returnlow;}voidqsort(inta[],intlow,inthigh){//快速排序的递归形式intpivotloc;if(lowhigh){pivotloc=partition(a,low,high);//一趟排序结果的调用qsort(a,low,pivotloc-1);qsort(a,pivotloc+1,high);}}《数据结构》课程设计报告7（3）希尔排序：先把数组分成等长的两个数组，用r[i]与r[n/2+i]比较小的在前，大的在后，然后在一刚刚两两一组的两组做比较，就这样，每次比较，每组数的个数都是上一次的两倍，最后完成整个数组的排序。voidShellInsert(sqList&L,intdk){//对顺序表L作一趟希尔插入排序。For(i=dk+1;i=L.length;++i)If(LT(L.r[i].key,L.r[i-dk].key)){//需将L.r[i]插入有序增量子表L.r[0]=L.r[i];//暂存在L.r[0]For(j=i-dk;j0&<(L.r[0].key,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];//记录后移，查找插入位置L.r[j+dk]=L.r[0];