数据结构各种排序算法的时间性能.doc
《数据结构各种排序算法的时间性能.doc》由会员分享,可在线阅读,更多相关《数据结构各种排序算法的时间性能.doc(18页珍藏版)》请在沃文网上搜索。
1、设计一组实验来比较下列排序算法的时间性能 快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为比较的对象) 要求 (1)时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。 (2)实验数据应具有说服力,包括:数据要有一定的规模(如元素个数从100到10000);数据的初始特性类型要多,因而需要具有随机性;实验数据的组数要多,即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清晰的形式给出,如图、表等。 (3)算法所用时间必须是机器时间,也可以包括比较和交换元素的次数。 (4)实验分析及其结果要能以清晰的方式来描述,如数学公式或图表等。(5)要给出实
2、验的方案及其分析。说明 本题重点在以下几个方面:理解和掌握以实验方式比较算法性能的方法;掌握测试实验方案的设计;理解并实现测试数据的产生方法;掌握实验数据的分析和结论提炼;实验结果汇报等。一、需求分析(1) 输入的形式和输入值的范围:本程序要求实现各种算法的时间性能的比较,由于需要比较的数目较大,不能手动输入,于是采用系统生成随机数。用户输入随机数的个数n,然后调用随机事件函数产生n个随机数,对这些随机数进行排序。于是数据为整数(2) 输出的形式:输出在各种数目的随机数下,各种排序算法所用的时间和比较次数。(3) 程序所能达到的功能:该程序可以根据用户的输入而产生相应的随机数,然后对随机数进行
3、各种排序,根据排序进行时间和次数的比较。(4)测试数据:略二、概要设计1.抽象数据类型ADT List 数据对象 D ai | ai ElemSet, i=1,2,.,n, n0 数据关系 R1 |ai-1 ,aiD, i=2,.,n 基本操作 virtual void clear() = 0; bool insert(const Elem&) = 0; bool append(const Elem&) = 0; lbool remove(Elem&) = 0;void setStart() = 0; void setEnd() = 0; void prev() = 0; void next(
4、) = 0; int leftLength() const = 0; int rightLength() const = 0; bool setPos(int pos) = 0; bool getValue(Elem&) const = 0; void print() const = 0;2.程序的流程(1) 输入模块:输入要排序的数的数量n(2) 处理模块:系统产生n个随机数,对随机数进行排序(3) 输出模块:将排序的结果输出3.算法的基本思想1、 随机数的产生:利用srand()产生随机数。2、 快速排序:选定一记录R,将所有其他记录关键字k与记录R的关键字k比较, 若 kk 则将记录换至
5、R之后,继续对R前后两部分记录进行快速排序,直至排序范围为13、 插入排序:逐个处理待排序的记录,每个新记录与前面已排序的子序列进行比较,将它插入到子序列中正确的位置4、 冒泡排序:比较并交换相邻的元素对,直到所有元素都被放到正确的地方为止。5、 归并排序:将两个或者多个有序表归并成一个有序表6、 堆排序:首先将数组转化为一个满足堆定义的序列,然后将堆顶的最大元素取出,再将剩下的数排成堆,再取堆顶数值,。如此下去,直到堆为空。到最后结束时,就排出了一个由小到大排列的数组。三、详细设计(1)产生随机数:直接调用函数srand(),以时间作为随机种子进行选择,并把随机数装入数组中 unsigned
6、 long int *Sort:setRan(unsigned long int num)unsigned long int *ra;ra=(unsigned long int*)malloc(num*sizeof(unsigned long int);srand(time(NULL);for(unsigned long int m=0;mnum;m+)ram=rand();coutendl;return ra;(2)快速排序:要实现快速排序首先选择一个轴值,这里选取数组第一个为轴值。定义两个标识low,high。high标识最后一个元素的位置,从后向前,将关键字与轴值比较,直至遇到小于轴值的
7、关键字,前移,low标识在第二个元素的位置,从前向后,将关键字与轴值比较,直至遇到大于轴值的关键字,后移。当low,high相遇后第一趟排序结束。调整数列,轴值左边的为比轴值小的,右边为比轴值大的。对轴值左边(即low到pivotkey-1的数)和右边的子列(pivotkey+1到high的数)分别进行上述递归快速排序,直到范围为1结束。int partition(int a,int low,int high)/快速排序中的一趟 int pivotkey; /作为枢轴来使用 pivotkey=alow; while(lowhigh) while(low=pivotkey) -high; alo
8、w=ahigh; while(lowhigh&alow=pivotkey) +low; ahigh=alow; alow=pivotkey; return low;void qsort(int a,int low,int high)/快速排序的递归形式 int pivotloc; if(lowsetNum();LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/获取时间Count1double d;int temp,j;
9、for (unsigned long int i=0;igetRanNum();i+)j=i;temp=si;while (j=1 & tempSortNum+;if(j1)this-SortNum+;sj=temp;QueryPerformanceCounter(&Count2);/获取时间Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间差,d的单位为ms.cout插入排序算法对RanNum个随机数排序时间为为d ms.endl;cout插入排序算法对RanNum个随机数交
10、换次数为SortNum次。endl;(4) 冒泡排序(bubble sort):将被排序的记录数组R1.n垂直排列,每个记录Ri看作是重量为Ri.key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上飘浮。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(Rn,Rn-1),(Rn-1,Rn-2),(R2,R1);对于每对气泡(Rj+1,Rj),若Rj+1.keysetNum();LARGE_INTEGER Freg;LARGE_I
11、NTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/获取时间Count1double d;unsigned long int temp;for(unsigned long int i=0;iRanNum);i+)for(int j=i+1;jRanNum);j+)if(sisj)temp = si;si=sj;sj=temp;this-SortNum+; QueryPerformanceCounter(&Count2);/获取时间Count2d=(double)(Coun
12、t2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间差,d的单位为ms.cout冒泡排序算法对RanNum个随机数排序时间为d ms.endl;cout冒泡排序算法对RanNum个随机数交换次数为SortNum次。endl; (5) 堆排序:堆排序与其他排序算法最大的区别是它依靠一种特殊的数据结构堆来进行排序。堆是一种完全二叉树,并且根节点不大于左右子树中的所有节点,ni=n2*i&ni=n2*i+1。因此堆排序算法首先要将给出的无序数组构造成一个堆,然后输出根节点(最小元素),将剩余元素重新恢复成堆,再次输出根节点。依
13、次类推,直至最后一个节点输出,此时堆排序完成。void Sort:heapRestor(unsigned long int *s,int i,int m) int ma;if(imin(s2*i,s2*i+1)if(s2*iheapRestor(s,2*i,m);elsema=si;si=s2*i+1;s2*i+1=ma;this-heapRestor(s,2*i+1,m);this-SortNum=this-SortNum+2;else if(iSortNum+;void Sort:heapCreat(unsigned long int *s,int m)int num;for(num=m/
14、2;num=1;num-)this-heapRestor(s,num,m);void Sort:heapSort(unsigned long int *s1,unsigned long int *s2)this-setNum();int i,num;num=this-RanNum;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/获取时间Count1double d;this-heapCreat(s1,this-Ran
15、Num);for(i=0;iRanNum;i+)s2i=s11;s11=s1num;this-heapRestor(s1,1,-num);QueryPerformanceCounter(&Count2);/获取时间Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间差,d的单位为ms.cout堆排序算法对RanNum个随机数排序时间为为d ms.endl;cout堆排序算法对RanNum个随机数交换次数为SortNum次。endl; (6) 合并排序:这里的合并排序和下边要描述的
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
10 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 各种 排序 算法 时间 性能