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