《数据结构课程设计排序算法时间性能的分析.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计排序算法时间性能的分析.doc（13页珍藏版）》请在三一文库上搜索。
1、数据结构课程设计排序算法时间性能的分析以下是为大家整理的数据结构课程设计排序算法时间性能的分析的 相关范文，本文关键词为数据结构 ,课程 ,设计,排序,算法,时间,性能,分 析,数据结构，您可以从右上方搜索框检索更多相关文章，如果您觉 得有用，请继续关注我们并推荐给您的好友， 您可以在教育文库中查 看更多范文。数据结构课程设计报告目录1 需 求 分 析 .11.111.2容1概2要设计22.1 原 始 数据 22.2程序的流程22.3总体设计图 3详3 细设计和编码43.1 算 法 基 本 思想43.2算法描述 43.3算法设计 53.484测试结果95 小结 9参考文献 10 附 录 ： 程
2、 序 源 代码10数据结构课程设计报告1 需求分析1.1 问题描述(1) 输入的形式和输入值的范围： 本程序要求实现各种算法的时间 性能的比较，由于需要比较的数目较大，不能手动输入，于是采用系 统生成随机数。用户输入随机数的个数 n然后调用随机事件函数产 生 n 个随机数，对这些随机数进行排序。于是数据为整数。(2) 输出的形式： 输出在各种数目的随机数下， 各种排序算法所用的时较次数。 （3）程序所能达到的功能： 该程序可以根据用户的输入而 产生相应的随机数， 然后对随机数进行各种排序， 根据排序进行时间 和次数的比较。（4）测试数据。1.2 设计内容 对各种排序方法（快速排序、堆排序、希尔
3、排序、冒泡排序、归 并排序）的时间性能进行比较。（ 1）设计并实现上述各种排序算法； （ 2）在排序中实现比较时 间性能；（3）在输入中分别调用上述排序算法，并比较时间性能。1数据结构课程设计报告2概要设计2.1 原始数据1. 抽象数据类型 ADTList数 据对象 D = ai|ai elemset,i=1,2,n,n 数据关）系 R1 = |ai-1,ai D,i=2,n 基本操作virtualvoidclear（）=0;boolinsert（constelemboolappend（constelemlboolre move（elemvoidsetstart（）=0;voidsetend(
4、)=0;voidprev()=0;voidnext()=0;intleftLength()const=0;intrightLength()const=0;boolsetpos(intpos)=0;boo lgetValue(elemvoidprint()const=0;2.2 程序的流程（1）输入模块：输入要排序的数的数量 n。（ 2）处理模块：系统产生 n 个随机数，对随机数进行排序。（3）输出模块：将排序的结果输出。2数据结构课程设计报告2.3 总体设计图冒泡排序快速排序主程序堆排序希尔排序归并排序冒泡排序输 出整理排序数据， 作出分析。 快速排序主程序堆排序希尔排序输入数 据归并排序图
5、13 数据结构课程设计报告3 详细设计和编码3.1 算法基本思想1. 随机数的产生：利用srand（）产生随机数。2. 快速排序：选定一记录R,将所有其他记录关键字 K'与记录R 的关键字K比较，若K'?K则将记录换至R之前若K'?K则将记录换至R 之后，继续对R前后两部分记录进行快速排序，直至排序范围为 1。3. 希尔排序：将序列分割成若干子序列分别进行直接插入排序， 待序列记录基本有序时再对整体进行一次直接插入排序。4. 冒泡排序：比较并交换相邻的元素对，直到所有元素都被放到 正确的地方为止。 5.归并排序：将两个或者多个有序表归并成一个有 序表。6.堆排序：首先将
6、数组转化为一个满足堆定义的序列，然后将堆 顶的最大元素取出，再将剩下的数排成堆，再取堆顶数值， ?。如此 下去，直到堆为空。到最后结束时，就排出了一个由小到大排列的数 组。3.2 算法描述（1）快速排序是对起泡排序的一种改进。 它的基本思想是： 通过一趟排序将待 排记录分别分割成独立的两部分， 其中一部分记录的关键字均比另一 部分记录的关键字大小， 则可分别对这两部分记录继续进行排序， 以 达到整个序列有序。 （ 2）堆排序是指利用堆这种数据结构所设计的一种排序算法。 堆是一个近似 完全二叉树的结构， 并同时满足堆性质： 即子结点的键值或索引总是 小于（或大于）它的父结点。只需一记录大小的辅助
7、空间，每个待排 序的记录仅占用一个存储空间。它的思想是：先是对堆做比较，左子 数小于本数，右子数大于本数，然后不停比较、交换，最后达到整个数组的排序。以下是为大家整理的数据结构课程设计排序算法时间性能的分析 (2) 的相关范文，本文关键词为数据结构 ,课程,设计 ,排序,算法 ,时间,性能 , 分析,数据结构，您可以从右上方搜索框检索更多相关文章，如果您 觉得有用， 请继续关注我们并推荐给您的好友， 您可以在教育文库中 查看更多范文。以下是为大家整理的数据结构课程设计排序算法时间性能的分析 (3) 的相关范文，本文关键词为数据结构 ,课程,设计 ,排序,算法 ,时间,性能 , 分析,数据结构，
8、您可以从右上方搜索框检索更多相关文章，如果您 觉得有用， 请继续关注我们并推荐给您的好友， 您可以在教育文库中 查看更多范文。数据结构课程设计报告参考文献 1王昆仑 ,李红等编著 .数据结构与算法 .北京 :中国铁道出版 社 ,20XX. 2苏仕华等编著 .数据结构课程设计 .北京：机械工业出版 社,20XX.3苏仕华编著数据结构与算法解析合肥:中国科学技术大 学出版社,20XX. :4郭嵩山等著国际大学生程序设计竞赛例题解北 京:电子工业出版社 ,20XX.5刘大有,唐海鹰等编著 .数据结构.北京:高等教育出版社 ,20XX.6徐孝凯编著 .数据结构实用教程 .北京:清华大学出版社 ,199
9、9.7严蔚敏 ,陈文博编著 .数据结构及算法教程 .北京 :清华大学出 版社,20XX.8刘振安，刘燕君等编著.c程序设计课程设计北京:机械 出版社 ,20XX. 9胡学钢.数据结构与算法设计指导 .北京:清华大学出 版社,1999.附录：程序源代码/*cout:输出cin：输入endl:换行：屏幕暂停（去掉这句屏幕瞬间自动关闭） */#include#include#include#includeusingnamespacestd;/ 命 名 空 间 ， 使 cout/cin? 起 作 用 constintmaxsize=9999;intnum=0;/ 定义全局变量，为每一趟的输出做准备 i
10、ntx=0;templateclasssortlist10数据结构课程设计报告private:intsortnum;intcurrentsize;/ 数据表中数据元素的个数public:type*arr;/ 存储数据元素的向量（排序表）sortlist():currentsize(0)arr=newtypemaxsize;/ 构 造 函 数 sortlist(intn)arr=newtypemaxsize;currentsize=n;voidinsert(inti,typex) arri=x;sortlist()deletearr;/ 析构函数 voidswap(typex=y;y=temp;
11、 voidbubblesort();/ 冒泡排序voidselectsort();/ 快速排序 voidheapsort();/ 堆排序 voidmergesort(sortlist/ 归并排序 voidshellsort();/ 希尔排序voidfilterdown(constintstart);/ 建立最大堆 void mergepass(sortlist/ 一趟归并 void merge(sortlist/ 两路归并算法 ;template/ 冒泡排序 oKvoidsortlist:bubblesort()11 数据结构课程设计报告 sortnum=0;LARge_InTegeRFreg
12、; LARge_InTegeRcount1,count2;QueryperformanceFrequency( Queryperformancecounter(/ 获取时间 count1inti=1;doubled;intfinish=0;/0 表 示 还 没 有 排 好 序 while(iQueryperformancecounter(/ 获取时间 count2 d=(double)(count2.Quadpart-count1.Quadpart)/(double)Freg.Quadpartfor(intj=0;j if(arrj>arrj+1)/ 逆序swap(arrj,arrj+1
13、);/ 相邻元素交换位置finish=0;sortnum+;/ 排序结束标志置为 ,表示本趟发生了交换，说明还没有排好序 i+;*1000.0;cout cout template/ 快 速 排 序oKvoidsortlist:selectsort()sortnum=0;12数据结构课程设计报告doubled;LARge_InTegeRFreg; LARge_InTegeRcount1,count2;QueryperformanceFrequency( Queryperformancecounter(/ 获取时间 count1inti=0;intfinish=0;/0 表 示 还 没 有 排
14、好 序 while(iQueryperformancecounter(/ 获取时间 count2 d=(double)(count2.Quadpart-count1.Quadpart)/(double)Freg.Quadpartfor(intj=i+1;jarrj)i+;swap(arri,arrj); finish=0;sortnum+;*1000.0;template/ 建立最大堆 voidsortlist:filterdown(constintstart)/ 向下调整使从 start 开始到 currentsize-1 为止的子表成为最大 堆cout13数据结构课程设计报告inti=st
15、art,j=2*i+1;/j 为 i 的 左 孩 子 inttablesize=currentsize;typetemp=arri;while(j if(jj+;/ 在两个孩子中选关键字较大者if(temp>=arrj)break;elsearri=arrj;sortnum+;i=j;j=2*j+1;sortnum+;template/ 堆排序 oKvoidsortlist:heapsort()sortnum=0; doubled;LARge_InTegeRFreg;LARge_InTegeRcount1,count2;QueryperformanceFrequency(Queryper
16、formancecounter(/ 获 取 时 间 count1inttablesize=currentsize,i;for(i=(currentsize-2)/2;i>=0;i-)14以下是为大家整理的数据结构课程设计排序算法时间性能的分析 (4) 的相关范文，本文关键词为数据结构 ,课程,设计 ,排序,算法 ,时间,性能 , 分析,数据结构，您可以从右上方搜索框检索更多相关文章，如果您 觉得有用， 请继续关注我们并推荐给您的好友， 您可以在教育文库中 查看更多范文。以下是为大家整理的数据结构课程设计排序算法时间性能的分析 (5) 的相关范文，本文关键词为数据结构 ,课程,设计 ,排序,算法 ,时间,性能 , 分析,数据结构，您可以从右上方搜索框检索更多相关文章，如果您 觉得有用， 请继续关注我们并推荐给您的好友， 您可以在教育文库中 查看更多范文。数据结构课程设计报告for(i=0;i number=100+rand()%(10000-100+1); table.shellsort();/ 希尔排序 table.insert(i,number);coutsystem(return0;20最后，小编希望文章对您有所帮助， 如果有不周到的地方请 多谅解，更多相关的文章正在创作中，希望您定期关注。谢谢支 持！