数据结构各种排序算法的时间性能.docx

题 目： 排序算法的时间性能学生姓名 学生学号 专业班级 指导老师 李晓鸿完成日期 设计一组实验来比较下列排序算法的时间性能快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为 比较的对象)要求(1) 时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时 间性能等。(2) 实验数据应具有说服力，包括：数据要有一定的规模(如元素个数从100 到10000)；数据的初始特性类型要多，因而需要具有随机性；实验数据的组数 要多，即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清 晰的形式给出，如图、表等。(3) 算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。(4) 实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。(5) 要给出实验的方案及其分析。说明本题重点在以下几个方面：理解和掌握以实验方式比较算法性能的方法；掌握测试实验方案的设计；理 解并实现测试数据的产生方法；掌握实验数据的分析和结论提炼；实验结果汇报一、需求分析(1) 输入的形式和输入值的范围：本程序要求实现各种算法的时间性能的比 较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。 用户输入随机数的个数n，然后调用随机事件函数产生n个随机数，对这些 随机数进行排序。于是数据为整数(2) 输出的形式：输出在各种数目的随机数下，各种排序算法所用的时间和 比较次数。(3) 程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机 数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。(4) 测试数据：略二、概要设计1. 抽象数据类型ADT List数据对象D= ai I ai EElemSet, i=1,2,.,n, nN0 数据关系R1= <ai-1 ,ai >|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() = 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、快速排序：选定一记录R,将所有其他记录关键字k与记录R的关键字k比较，若k<k则将记录换至R之前，若k >k则将记录换至R之后，继续对R前后两部分记录进行快速排序，直至排序范围为13、插入排序：逐个处理待排序的记录，每个新记录与前面已排序的子序列 进行比较，将它插入到子序列中正确的位置4、冒泡排序：比较并交换相邻的元素对，直到所有元素都被放到正确的地 方为止。5、归并排序：将两个或者多个有序表归并成一个有序表6、堆排序：首先将数组转化为一个满足堆定义的序列，然后将堆顶的最大 元素取出，再将剩下的数排成堆，再取堆顶数值，。如此下去，直到 堆为空。到最后结束时，就排出了一个由小到大排列的数组。三、详细设计(1) 产生随机数：直接调用函数srand(),以时间作为随机种子进行选择，并把 随机数装入数组中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;m<num;m+)ram=rand();cout<<endl;return ra;(2) 快速排序：要实现快速排序首先选择一个轴值，这里选取数组第一个为轴 值。定义两个标识low,higho high标识最后一个元素的位置，从后向前，将关键 字与轴值比较，直至遇到小于轴值的关键字，前移，low标识在第二个元素的位 置，从前向后，将关键字与轴值比较，直至遇到大于轴值的关键字，后移。当 low,high相遇后第一趟排序结束。调整数列，轴值左边的为比轴值小的，右边为 比轴值大的。对轴值左边(即10可到pivotkey-1的数)和右边的子列(pivotkey+1 到3或的数)分别进行上述递归快速排序，直到范围为1结束。int partition(int a,int low,int high)快速排序中的一趟int pivotkey;作为枢轴来使用pivotkey=alow;while(low<high)while(low<high&&ahigh>=pivotkey)-high;alow=ahigh;while(low<high&&alow<=pivotkey)+low;ahigh=alow;alow=pivotkey;return low;void qsort(int a,int low,int high)/ 快速排序的递归形式int pivotloc;if(low<high)(pivotloc=partition(a,low,high);/ 趟排序结果的调用qsort(a,low,pivotloc-1);qsort(a,pivotloc+1,high);(3) 插入排序：插入排序的思想是将一组无序的元素分别插入一个已经有序的 的数组里，并保证插入后的数组也是有序的。当所有无序组的元素都插入完毕 时，一个有序数组构造完成。数组n1r为初始的一个无序数组(为了直观起 见，我们这里设定数组从1开始，而不是0)，则n1默认为只有一个元素的有 序数组，皿2插入只有n1 构成的有序数组中，则此时有序数组的元素数量变为 2。以此类推，到第i个元素时，前i-1个元素已经是有序的，此时只需将第i个 元素插入到有序数组中并使之保持有序。如此直至最后一个元素插入完毕，整 个插入排序完成。void Sort:insertSort(unsigned long int *s)(this->setNum();LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/获 取时间 Count1double d;int temp,j;for (unsigned long int i=0;i<this->getRanNum();i+)jT;temp=si;while (j>=1 && temp<sj-1)sj=sj-1;j-;this->SortNum+;if(j>1)this->SortNum+;sj=temp;QueryPerformanceCounter(&Count2);/获 取时间C ount2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间 差，d的单位为ms.cout<<"插入排序算法对"<<this->RanNum<<"个随机数排序时间为为"<<d<<" ms."<<endl;cout<<"插入排序算法对"<<this->RanNum<<"个随机数交换次数为"<<this->SortNum<<" 次。"<<endl;(4) 冒泡排序(bubble sort)：将被排序的记录数组皿1口垂直排列，每个记录 Ri看作是重量为Ri.key的气泡。根据轻气泡不能在重气泡之下的原则，从下 往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反 复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。从无序区底部 向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二 者的位置。即依次比较(Rn，Rn-1)，(Rn-1，Rn-2)，(R2，R1)； 对于每对气泡(Rj+1，Rj)，若 Rj+1.key<R|j.key，则交换 Rj+1和 Rj的内 容。第一趟扫描完毕时，”最轻”的气泡就飘浮到该区间的顶部，即关键字最小 的记录被放在最高位置R1上。扫描R2.n。扫描完毕时，”次轻"的气泡飘浮 到R2的位置上最后，经过n-1趟扫描可得到有序区R1.n void Sort:bubbleSort(unsigned long int *s)(this->setNum();LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/获 取时间 Count1 double d;unsigned long int temp;for(unsigned long int i=0;i<(this->RanNum);i+) for(int j=i+1;j<(this->RanNum);j+) if(si>sj) temp = si; si=sj; sj=temp;this->SortNum+;QueryPerformanceCounter(&Count2);/获 取时间C ount2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间 差，d的单位为ms.cout<<"冒泡排序算法对"<<this->RanNum<<"个随机数排序时间为"<<d<<" ms."<<endl;cout<<"冒泡排序算法对"<<this->RanNum<<"个随机数交换次数为"vvthis->SortNumvv” 次。"vvendl;(5) 堆排序：堆排序与其他排序算法最大的区别是它依靠一种特殊的数据结 构一堆来进行排序。堆是一种完全二叉树，并且根节点不大于左右子树中的所有节点，ni<=n2*i&&ni<=n2*i+1。因此堆排序算法首先要将给出的无序数组构造成一个堆，然后输出根节点(最小元素)，将剩余元素重新恢复成堆， 再次输出根节点。依次类推，直至最后一个节点输出，此时堆排序完成。void Sort:heapRestor(unsigned long int *s,int i,int m) (int ma;if(i<=m/2)&&(si>min(s2*i,s2*i+1)if(s2*i<s2*i+1)ma=si;si=s2*i;s2*i=ma;this->heapRestor(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(i<=m/2)this->SortNum+;void Sort:heapCreat(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(&Count1);/获 取时间 Count1double d;this->heapCreat(s1,this->RanNum);for(i=0;i<this->RanNum;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<<"堆排序算法对"<<this->RanNum<<"个随机数排序时间为为”<<d<<” ms."<<endl;cout<<"堆排序算法对"<<this->RanNum<<"个随机数交换次数为"<<this->SortNum<<” 次。"<<endl;(6) 合并排序：这里的合并排序和下边要描述的快速排序都采用了分而治之 的思想，但两者仍然有很大差异。合并排序是将一个无序数组n1.r分成两个 数组n1.r/2与nr/2+1.r，分别对这两个小数组进行合并排序，然后再将这 两个数组合并成一个大数组。由此我们看出合并排序时一个递归过程(非递归 合并排序这里不做讨论)。合并排序的主要工作便是“合并”，两个小规模数组 合并成大的，两个大的再合并成更大的，当然元素比较式在合并的过程中进行 的。void Sort:mergeSort(unsigned long int *s,int left,int right)int i;if(left < right)i=(left + right)/2;mergeSort(s,left, i);mergeSort(s, i + 1, right);Merge(s, left, i, right);int Sort:partition(unsigned long int *s,int low,int high)int key,i,p,r;p=low;r=high;key=sp;while(p<r)for(i=r;i>p;i-)if(si<=key) sp=sr;p+；this->SortNum+;break;r-;this->SortNum+;for(i=p;i<r;i+)if(si>key)sr=sp;r-;this->SortNum+;break;p+;this->SortNum+;sp=key;return p;(7) 基本操作AList(int size=DefaultListSize) maxSize = size;listSize = fence = 0;listArray = new ElemmaxSize;AList() delete listArray; <1>清空。释放数组，将数组大小和栅栏置0.void clear() delete listArray;listSize = fence = 0;listArray = new ElemmaxSize;<2>将栅栏赋初值0,放在开头。void setStart() fence = 0; <3>将栅栏指向数组最后。void setEnd() ( fence = listSize; <4>获得当前的位置。用栅栏的指向即可直接获得。void prev() ( if (fence != 0) fence-; <5>获得最大值的大小，由栅栏可直接获得。void next() ( if (fence <= listSize)fence+; <6>返回当前位置左边的长度。直接返回栅栏的值获得。int leftLength() const return fence; <7>返回当前位置右边的长度。用最大长度减去当前栅栏的值。int rightLength() const return listSize - fence; <8>设置当前位置，将值直接赋予栅栏。bool setPos(int pos) if (pos >= 0) && (pos <= listSize)fence = pos;return (pos >= 0) && (pos <= listSize);<9>返回当前的值。bool getValue(Elem& it) const if (rightLength() = 0) return false;else it = listArrayfence;return true;(4) 算法的时空分析<1>插入排序：直接插入排序算法必须进行n-1趟。最好情况下，即初始序 列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是 (n-1)，移动元素次数是2(n-1)。因此最好情况下的时间复杂度就是O(n)。最坏 情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为 O(n2)。<2>冒泡排序：当原始数据正向有序时，冒泡排序出现最好情况。此时，只需 进行一趟排序，作n-1次关键字比较，因此最好情况下的时间复杂度是O(n)。 当原始数据反向有序时，冒泡排序出现最坏情况。此时，需进行n-1趟排序，第 i趟作(n-i)次关键字间的比较，并且需执行(n-i)次元素交换，所以，比较次数 为：因此,最坏情况下的时间复杂度为O(n2)<3>快速排序：如果每一次分划操作后，左、右两个子序列的长度基本相等， 则快速排序的效率最高，其最好情况时间复杂度为O(nlogn)；反之，如果每次 2分划操作所产生的两个子序列，其中之一为空序列，此时，快速排序效率最低， 其最坏情况时间复杂度为O(n2)。如果选择左边第一个元素为主元，则快速排序 的最坏情况发生在原始序列正向有序或反向有序时。快速排序的平均情况时间复 杂度为O(nlog n)。2<4>堆排序：堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时 间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为 O(nlogn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数 较多，所以堆排序不适宜于记录数较少的文件。堆排序是不稳定的，算法时间复 杂度 O(nlogn)。<5>归并排序：在最佳、平均、最差情况下，时间复杂度为(n log n)，不 足的就是需要两倍的空间代价，当输入的待排序数据存储在链表中时，归并排序 是一个很好的选择.(5) 函数的调用关系图用户输入排序的元素个数n产生n个随机数主程序对随机数进行排序输出(6) 输入和输出的格式输入请输入排序规模：提示输入等待输入输出插入排序算法对n个随机数排序时间为插入排序算法对n个随机数交换次数为冒泡排序算法对n个随机数排序时间为冒泡排序算法对n个随机数交换次数为 堆排序算法对n个随机数排序时间为堆排序算法对n个随机数交换次数为合并排序算法对n个随机数排序时间为合并排序算法对n个随机数交换次数为快速排序算法对n个随机数排序时间为快速排序算法对n个随机数交换次数为排序后，前50个有序兀素为：四、用户使用说明（可选）1、本程序的运行环境为DOS操作系统，执行文件为conversion.exe2、运行程序时输入请输入排序规模：提示输入等待输入输出插入排序算法对n个随机数排序时间为插入排序算法对n个随机数交换次数为冒泡排序算法对n个随机数排序时间为冒泡排序算法对n个随机数交换次数为堆排序算法对n个随机数排序时间为堆排序算法对n个随机数交换次数为合并排序算法对n个随机数排序时间为合并排序算法对n个随机数交换次数为快速排序算法对n个随机数排序时间为快速排序算法对n个随机数交换次数为排序后，前50个有序兀素为：五：实现图1控制台程序实验结果：实验分别实现插入排序、冒泡排序、堆排序、合并排序、快速排序，以不同规 模（100，1000，2000，5000，10000，100000个数据）的随机数作为测试数据 集，实验结果截图如下：E C:Wi n d owssyste m 3 2cmd. exe请输入排序规模:100近恳法飘询气、障叽数排度时间为为0452563 叽数交盛次数为2782次。1=11=1近恳法飘询气、障叽数排度时间10.100777 叽数交盛次数为2684次。叽数排度时间为10.0737164 叽数交盛次数为丽次。近恳法飘询气、障叽数排度时间为为0.370915 叽数交盛次数为码5次。法法504 一.B-W-前53蒸1跛个随机数排度时间为为虬祀3S923 寸1.如鸯腿S交僚次数为迥凑 个有J予兀素为f1465148215922140359839574244461461646654716782059614 1240081769569 11767蒲按任意键继续82781921248183361071112816854710839128938547109541315186241159513170218678519100116681361031627856947511684139943328815595161169314043排序规模为100排序规模为：2000raw C:Win dcw5syste m 3 2crrd, exe序昙法5000个随:近恳法 -5000-f®：疗昇法黄林卜随哇恳法汁弱驹个障 琼畀法蒙用龄卜随札数排序时间为为应海4 ms. 孔数交技次数为队弱明2吹。孔数排底时间为M3.? ms.孔数交技夜数为础弱？抑次.叽数排序时间为93-59577凯数交搦次数为说6叫6成。近恳法-5000-f®疗昇法菠膈酶卜随:中顾个_没拈43理个 前3个有序无29301271272012&227JS 27614133 2明 287ns.凯数排序时间为为11英网4 凯数交骚次数为弱3成成。成机数排序时间为加-3也蜜型数交技孜数为?1必成。弱1施 154 211 291Ils?16022ifl297116 1商 256 297ms.116168257阳桩74879 s?116119125173180182257265267315318319请按任意键继续排序规模为：10000（六）算法性能分析在程序中我们根据数据规模的不同产生不同的随机整型数组，然后分别让不同 的排序算法来进行从小到大的排序。这里需要注意的是：每种排序算法在相同的 输入规模中原始无序数据都是一样的。例如五种排序算法要对长度为100的无序 数组进行排序，它们所要排序的无序数组都是一样的，我们以此来保证实验的公 正性。在这里我们认为比较次数是排序算法的主要操作，因此我们在每个排序算 法中加入计数器来记录排序过程中的比较次数，以此来作为对算法性能分析的主 要参数（排序时间作为辅助参数）。表1为在输入规模分别为100，1000，2000， 5000，10000，100000时各个算法的元素交换次数。表2为在输入规模分别为100， 1000，2000，5000，10000，100000时各个算法的排序时间。排序 规模（n）算法'10010002000500010000100000插入排序27822462559832116266052248708162509250617冒泡排序26842420119631585956790224520141127169842堆排序100016480370631060262319032985016合并排序555871919432553011204091536596快速排序5991037723702714311528791946925表1排序算法比较次数性能比较排序规模（n）算法*一10010002000500010000100000插入排序0.04523.058312.126358.2854177.5416694冒泡排序0.10079.4697621.3535133.777526.97142698.7堆排序0.07370.5794671.284443.595778.03182102.961合并排序0.37092.191434.1192511.679420.8016192.61快速排序0.03350.2029530.4287681.31712.6953129.9569表2排序算法排序时间比较（单位ms）为了直观起见，根据实验数据画出各种排序算法在不同输入规模下交换次数的变 化趋势图如图2所示：图2排序算法交换次数趋势图由上图我们基本上看出插入排序和冒泡排序的比较次数随输入规模的呈非线性 增长，而后三种排序方法堆排序，合并排序，快速排序的比较次数随输入规 模的增长基本呈线性变化趋势。根据实验数据画出各种排序算法在不同输入规模下交换次数的变化趋势图如图 3所示：实验结果与我们对这五种算法的性能理论分析基本吻合:插入排序与冒泡排序的时间复 杂度为O(n*n)，而后三种排序算法的时间复杂度为O(nlogn)。图4还显示出虽然冒泡排序 和插入排序的时间复杂度相同，但插入排序的性能仍然比冒泡排序好，尤其在排序时间方面。（七）结论最后得出结论：时间性能上，快速排序 > 堆排序 > 合并排序 > 插入排序 > 冒泡排序交换次数上，合并排序 > 快速排序 > 堆排序 > 冒泡排序 > 插入排序（八）心得作为拿来复习的一个报告还是蛮有成就感的，但是输入1000000个数据的时 候等得太久，实在等不出结果，而且放入值太大不方便作图，于是就不参与数据 分析，但是估计结果应该相同。以前不懂排序只会用冒泡，因为冒泡排序是接触 编程的第一个排序，印象很深刻，而且几乎不会用错，当数据比较大时它的弊端 就真的出现了。本以为这个实验还是比较好做的，排序几乎都会，连助教都说一 句你这个选题太没难度了。但是平心而论，真正实现起来还真是问题多多，首先 是怎么样调用时间的问题，这也是第一个先想的问题，本来打算就只比较交换次 数和比较次数的，但是这些其实没有比时间更直观的反应排序的效率。寻找半天 无果本来都打算放弃了，结果竟然有一个回复贴说QueryPerformanceCounter 函数，于是就发现这个问题可以解决了。结果是想象的有点偏差，没想到堆排序 的速度也能这么快，合并排序的次数会那么少。本以为快速排序就是万能的了， 看来想多了。或许以后在研究算法方面的确需要好好分析效率，数据结构的确是 一门很有用的学科，以后不能丢弃。