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

《数据结构课程设计排序算法时间性能的分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》课程设计报告目录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《数据结构》课程设计报告1需求分析1.1问题描述(1)输入的形式和输入值的范围：本程序要求实现各种算法的时间性能的比较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。用户输入随机数的个数n，然后调用随机事件函数产生n个随机数，对这些随机数进行排序。

2、于是数据为整数。(2)输出的形式：输出在各种数目的随机数下，各种排序算法所用的时较次数。(3)程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。（4）测试数据。1.2设计内容对各种排序方法（快速排序、堆排序、希尔排序、冒泡排序、归并排序）的时间性能进行比较。（1）设计并实现上述各种排序算法；（2）在排序中实现比较时间性能；（3）在输入中分别调用上述排序算法，并比较时间性能。19《数据结构》课程设计报告2概要设计2.1原始数据1.抽象数据类型ADTList数据对象D＝{

3、ai

4、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系R1＝{

5、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;bo

6、olsetPos(intpos)=0;boolgetValue(Elem&)const=0;voidprint()const=0;2.2程序的流程（1）输入模块：输入要排序的数的数量n。（2）处理模块：系统产生n个随机数，对随机数进行排序。（3）输出模块：将排序的结果输出。19《数据结构》课程设计报告2.3总体设计图主程序冒泡排序快速排序堆排序希尔排序归并排序主程序堆排序快速排序冒泡排序希尔排序归并排序输出整理排序数据，作出分析。输入数据图119《数据结构》课程设计报告3详细设计和编码3.1算法基本思想1.随机数的产生：利用srand(

7、)产生随机数。2.快速排序：选定一记录，将所有其他记录关键字与记录的关键字比较,若则将记录换至之前,若则将记录换至之后，继续对前后两部分记录进行快速排序，直至排序范围为1。3.希尔排序：将序列分割成若干子序列分别进行直接插入排序，待序列记录基本有序时再对整体进行一次直接插入排序。4.冒泡排序：比较并交换相邻的元素对，直到所有元素都被放到正确的地方为止。5.归并排序：将两个或者多个有序表归并成一个有序表。6.堆排序：首先将数组转化为一个满足堆定义的序列，然后将堆顶的最大元素取出，再将剩下的数排成堆，再取堆顶数值，…。如此下去，直到堆为空。

8、到最后结束时，就排出了一个由小到大排列的数组。3.2算法描述（1）快速排序是对起泡排序的一种改进。它的基本思想是：通过一趟排序将待排记录分别分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字大小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。（2）堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或大于）它的父结点。只需一记录大小的辅助空间，每个待排序的记录仅占用一个存储空间。它的思想是：先是对堆做比较，左子数小于本数，右子数大于本数

9、，然后不停比较、交换，最后达到整个数组的排序。19《数据结构》课程设计报告（2）希尔排序它又称“缩小增量排序”，又是一种属插入排序类的方法，但在时间效率上有很大改进。它的思想是：先把数组分成等长的两个数组，用r[i]与r[n/2+i]比较小的在前，大的在后，然后在一刚刚两两一组的两组做比较，就这样，每次比较，每组数的个数都是上一次的两倍，最后完成整个数组的排序。（3）冒泡排序它是一种“交换”进行排序的方法之中最简单的一种。它的思想是：相邻的两个元素进行比较，将小的调到前面，大的调到后面。（4）归并排序“归并”的含义是将两个或两个以上的有

10、序表组合成一个新的有序表。它的算法思想是：先把数组对半分多次，直到每组只有两个数据时，进行比较、排序，然后再两两合并，最后做到整个数组的排序完成。3.3算法设计（1）产生随机数：直接调用函数srand(),