数据结构各种排序算法的时间性能.docx
《数据结构各种排序算法的时间性能.docx》由会员分享,可在线阅读,更多相关《数据结构各种排序算法的时间性能.docx(19页珍藏版)》请在三一办公上搜索。
1、题 目: 排序算法的时间性能学生姓名 学生学号 专业班级 指导老师 李晓鸿完成日期 设计一组实验来比较下列排序算法的时间性能快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为 比较的对象)要求(1) 时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时 间性能等。(2) 实验数据应具有说服力,包括:数据要有一定的规模(如元素个数从100 到10000);数据的初始特性类型要多,因而需要具有随机性;实验数据的组数 要多,即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清 晰的形式给出,如图、表等。(3) 算法所用时间必须是机器时间,也可以包括比较和交换元素
2、的次数。(4) 实验分析及其结果要能以清晰的方式来描述,如数学公式或图表等。(5) 要给出实验的方案及其分析。说明本题重点在以下几个方面:理解和掌握以实验方式比较算法性能的方法;掌握测试实验方案的设计;理 解并实现测试数据的产生方法;掌握实验数据的分析和结论提炼;实验结果汇报一、需求分析(1) 输入的形式和输入值的范围:本程序要求实现各种算法的时间性能的比 较,由于需要比较的数目较大,不能手动输入,于是采用系统生成随机数。 用户输入随机数的个数n,然后调用随机事件函数产生n个随机数,对这些 随机数进行排序。于是数据为整数(2) 输出的形式:输出在各种数目的随机数下,各种排序算法所用的时间和 比
3、较次数。(3) 程序所能达到的功能:该程序可以根据用户的输入而产生相应的随机 数,然后对随机数进行各种排序,根据排序进行时间和次数的比较。(4) 测试数据:略二、概要设计1. 抽象数据类型ADT List数据对象D= ai I ai EElemSet, i=1,2,.,n, nN0 数据关系R1= |ai-1 ,aiED, i=2,.,n 基本操作virtual void clear() = 0;bool insert(const Elem&) = 0;bool append(const Elem&) = 0;lbool remove(Elem&) = 0;void setStart() =
4、0;void setEnd() = 0;void prev() = 0;void next() = 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、快速排序:选
5、定一记录R,将所有其他记录关键字k与记录R的关键字k比较,若kk则将记录换至R之后,继续对R前后两部分记录进行快速排序,直至排序范围为13、插入排序:逐个处理待排序的记录,每个新记录与前面已排序的子序列 进行比较,将它插入到子序列中正确的位置4、冒泡排序:比较并交换相邻的元素对,直到所有元素都被放到正确的地 方为止。5、归并排序:将两个或者多个有序表归并成一个有序表6、堆排序:首先将数组转化为一个满足堆定义的序列,然后将堆顶的最大 元素取出,再将剩下的数排成堆,再取堆顶数值,。如此下去,直到 堆为空。到最后结束时,就排出了一个由小到大排列的数组。三、详细设计(1) 产生随机数:直接调用函数sr
6、and(),以时间作为随机种子进行选择,并把 随机数装入数组中unsigned 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,hig
7、ho high标识最后一个元素的位置,从后向前,将关键 字与轴值比较,直至遇到小于轴值的关键字,前移,low标识在第二个元素的位 置,从前向后,将关键字与轴值比较,直至遇到大于轴值的关键字,后移。当 low,high相遇后第一趟排序结束。调整数列,轴值左边的为比轴值小的,右边为 比轴值大的。对轴值左边(即10可到pivotkey-1的数)和右边的子列(pivotkey+1 到3或的数)分别进行上述递归快速排序,直到范围为1结束。int partition(int a,int low,int high)快速排序中的一趟int pivotkey;作为枢轴来使用pivotkey=alow;while
8、(lowhigh)while(low=pivotkey)-high;alow=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);
9、/获 取时间 Count1double d;int temp,j;for (unsigned long int i=0;igetRanNum();i+)jT;temp=si;while (j=1 & tempSortNum+;if(j1)this-SortNum+;sj=temp;QueryPerformanceCounter(&Count2);/获 取时间C ount2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间 差,d的单位为ms.cout插入排序算法对RanNum个随机数排序时
10、间为为d ms.endl;cout插入排序算法对RanNum个随机数交换次数为SortNum 次。endl;(4) 冒泡排序(bubble sort):将被排序的记录数组皿1口垂直排列,每个记录 Ri看作是重量为Ri.key的气泡。根据轻气泡不能在重气泡之下的原则,从下 往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上飘浮。如此反 复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。从无序区底部 向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二 者的位置。即依次比较(Rn,Rn-1),(Rn-1,Rn-2),(R2,R1); 对于每对气泡(Rj+1,Rj),若 R
11、j+1.keysetNum();LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/获 取时间 Count1 double 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+;QueryPerfo
12、rmanceCounter(&Count2);/获 取时间C ount2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间 差,d的单位为ms.cout冒泡排序算法对RanNum个随机数排序时间为d ms.endl;cout冒泡排序算法对RanNumSortNumvv” 次。vvendl;(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:hea
14、pCreat(unsigned long int *s,int m)int num;for(num=m/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(&Co
15、unt1);/获 取时间 Count1double d;this-heapCreat(s1,this-RanNum);for(i=0;iRanNum;i+)s2i=s11;s11=s1num;this-heapRestor(s1,1,-num);QueryPerformanceCounter(&Count2);/获 取时间C ount2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间 差,d的单位为ms.cout堆排序算法对RanNum个随机数排序时间为为”d” ms.endl;cout
16、堆排序算法对RanNum个随机数交换次数为SortNum” 次。endl;(6) 合并排序:这里的合并排序和下边要描述的快速排序都采用了分而治之 的思想,但两者仍然有很大差异。合并排序是将一个无序数组n1.r分成两个 数组n1.r/2与nr/2+1.r,分别对这两个小数组进行合并排序,然后再将这 两个数组合并成一个大数组。由此我们看出合并排序时一个递归过程(非递归 合并排序这里不做讨论)。合并排序的主要工作便是“合并”,两个小规模数组 合并成大的,两个大的再合并成更大的,当然元素比较式在合并的过程中进行 的。void Sort:mergeSort(unsigned long int *s,in
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 各种 排序 算法 时间 性能
链接地址:https://www.31ppt.com/p-5306597.html