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

《数据结构各种排序算法的时间性能.》由会员分享，可在线阅读，更多相关《数据结构各种排序算法的时间性能.（24页珍藏版）》请在装配图网上搜索。

1、HUNAN UNIVERSITY课程实习报告题 目： 排序算法的时间性能 学生姓名 学生学号 专业班级 指引教师 李晓鸿 完 成 日 期 设计一组实验来比较下列排序算法的时间性能 迅速排序、堆排序、希尔排序、冒泡排序、归并排序(其她排序也可以作为比较的对象） 规定 (1)时间性能涉及平均时间性能、最佳状况下的时间性能、最差状况下的时间性能等。 (2)实验数据应具有说服力，涉及：数据要有一定的规模（如元素个数从100到10000）；数据的初始特性类型要多，因而需要具有随机性；实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。实验成果要能以清晰的形式给出，如图、表等。 (3)算法

2、所用时间必须是机器时间，也可以涉及比较和互换元素的次数。 (4)实验分析及其成果要能以清晰的方式来描述，如数学公式或图表等。(5)要给出实验的方案及其分析。阐明 本题重点在如下几种方面：理解和掌握以实验方式比较算法性能的措施；掌握测试实验方案的设计；理解并实现测试数据的产生措施；掌握实验数据的分析和结论提炼；实验成果报告等。一、需求分析(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&) =

4、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、 随机数

5、的产生：运用srand()产生随机数。2、 迅速排序：选定一记录R，将所有其她记录核心字k与记录R的核心字k比较, 若 kk 则将记录换至R之后，继续对R前后两部分记录进行迅速排序，直至排序范畴为13、 插入排序：逐个解决待排序的记录，每个新记录与前面已排序的子序列进行比较，将它插入到子序列中对的的位置4、 冒泡排序：比较并互换相邻的元素对，直到所有元素都被放到对的的地方为止。5、 归并排序：将两个或者多种有序表归并成一种有序表6、 堆排序：一方面将数组转化为一种满足堆定义的序列，然后将堆顶的最大元素取出，再将剩余的数排成堆，再取堆顶数值，。如此下去，直到堆为空。到最后结束时，就排出了一种由小

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;mnum;m+)ram=rand();coutendl;return ra;（2）迅速排序：要实现迅速排序一方面选择一种

7、轴值，这里选用数组第一种为轴值。定义两个标记low,high。high标记最后一种元素的位置，从后向前，将核心字与轴值比较，直至遇到不不小于轴值的核心字，前移，low标记在第二个元素的位置，从前向后，将核心字与轴值比较，直至遇到不小于轴值的核心字，后移。当low,high相遇后第一趟排序结束。调节数列，轴值左边的为比轴值小的，右边为比轴值大的。对轴值左边（即low到pivotkey-1的数）和右边的子列（pivotkey+1到high的数）分别进行上述递归迅速排序，直到范畴为1结束。int partition(int a,int low,int high)/迅速排序中的一趟 int pivot

8、key; /作为枢轴来使用 pivotkey=alow; while(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;QueryPerformanceFrequen

9、cy(&Freg);QueryPerformanceCounter(&Count1);/获取时间Count1double d;int temp,j;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;

10、/计算时间差，d的单位为ms.cout插入排序算法对RanNum个随机数排序时间为为d ms.endl;cout插入排序算法对RanNum个随机数互换次数为SortNum次。endl;(4) 冒泡排序（bubble sort）：将被排序的记录数组R1.n垂直排列，每个记录Ri看作是重量为Ri.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违背本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则互换两者的位置。即依次比较(Rn，Rn-1)，(Rn-1，

11、Rn-2)，(R2，R1)；对于每对气泡(Rj+1，Rj)，若Rj+1.keysetNum();LARGE_INTEGER Freg;LARGE_INTEGER 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;

12、this-SortNum+; QueryPerformanceCounter(&Count2);/获取时间Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间差，d的单位为ms.cout冒泡排序算法对RanNum个随机数排序时间为d ms.endl;cout冒泡排序算法对RanNum个随机数互换次数为SortNum次。endl; (5) 堆排序：堆排序与其她排序算法最大的区别是它依托一种特殊的数据构造堆来进行排序。堆是一种完全二叉树，并且根节点不不小于左右子树中的所有节点，ni=

13、n2*i&ni=n2*i+1。因此堆排序算法一方面要将给出的无序数组构导致一种堆，然后输出根节点（最小元素），将剩余元素重新恢复成堆，再次输出根节点。依次类推，直至最后一种节点输出，此时堆排序完毕。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

14、(iSortNum+;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);Que

15、ryPerformanceCounter(&Count1);/获取时间Count1double d;this-heapCreat(s1,this-RanNum);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个随机数排序时

16、间为为d ms.endl;cout堆排序算法对RanNum个随机数互换次数为SortNum次。endl; (6) 合并排序：这里的合并排序和下边要描述的迅速排序都采用了分而治之的思想，但两者仍然有很大差别。合并排序是将一种无序数组n1r提成两个数组n1r/2与nr/2+1r，分别对这两个小数组进行合并排序，然后再将这两个数组合并成一种大数组。由此我们看出合并排序时一种递归过程（非递归合并排序这里不做讨论）。合并排序的重要工作便是“合并”，两个小规模数组合并成大的，两个大的再合并成更大的，固然元素比较式在合并的过程中进行的。void Sort:mergeSort(unsigned long in

17、t *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(pp;i-)if(siSortNum+;break; r-;this-SortNum+;for(i=p;ikey)sr=sp

18、;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; 清空。释放数组，将数组大小和栅栏置0.void clear() delete listArray; listSize = fence = 0; listArray = new ElemmaxSize;将栅栏赋初值0，放在

19、开头。void setStart() fence = 0; 将栅栏指向数组最后。void setEnd() fence = listSize; 获得目前的位置。用栅栏的指向即可直接获得。void prev() if (fence != 0) fence-; 获得最大值的大小，由栅栏可直接获得。void next() if (fence = listSize) fence+; 返回目前位置左边的长度。直接返回栅栏的值获得。int leftLength() const return fence; 返回目前位置右边的长度。用最大长度减去目前栅栏的值。int rightLength() const r

20、eturn listSize - fence; 设立目前位置，将值直接赋予栅栏。bool setPos(int pos) if (pos = 0) & (pos = 0) & (pos = listSize);返回目前的值。bool getValue(Elem& it) const if (rightLength() = 0) return false; else it = listArrayfence; return true; （4）算法的时空分析插入排序：直接插入排序算法必须进行n-1趟。最佳状况下，即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1)

21、，移动元素次数是2(n-1)。因此最佳状况下的时间复杂度就是O(n)。最坏状况(非递增)下，最多比较i次，因此需要的比较次数是：因此，时间复杂度为O(n2)。冒泡排序：当原始数据正向有序时，冒泡排序浮现最佳状况。此时，只需进行一趟排序，作n-1次核心字比较，因此最佳状况下的时间复杂度是O(n)。当原始数据反向有序时，冒泡排序浮现最坏状况。此时，需进行n-1趟排序，第i趟作(n-i)次核心字间的比较，并且需执行(n-i)次元素互换，因此，比较次数为：因此,最坏状况下的时间复杂度为O(n2)迅速排序：如果每一次分划操作后，左、右两个子序列的长度基本相等，则迅速排序的效率最高，其最佳状况时间复杂度为

22、O(nlog2n)；反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，此时，迅速排序效率最低，其最坏状况时间复杂度为O(n2)。如果选择左边第一种元素为主元，则迅速排序的最坏状况发生在原始序列正向有序或反向有序时。迅速排序的平均状况时间复杂度为O(nlog2n)。堆排序：堆排序的时间，重要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为O(nlogn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，因此堆排序不合适于记录数较少的文献。堆排序是不稳定的，算法时间复杂度O(nlogn)。归并排序：在最佳、平

23、均、最差状况下，时间复杂度为Q(n log n)，局限性的就是需要两倍的空间代价，当输入的待排序数据存储在链表中时，归并排序是一种较好的选择.（5）函数的调用关系图顾客输入排序的元素个数n产生n个随机数主程序对随机数进行排序输出（6）输入和输出的格式输入 请输入排序规模：/提示输入 等待输入 输出 插入排序算法对n个随机数排序时间为 插入排序算法对n个随机数互换次数为 冒泡排序算法对n个随机数排序时间为 冒泡排序算法对n个随机数互换次数为 堆排序算法对n个随机数排序时间为 堆排序算法对n个随机数互换次数为 合并排序算法对n个随机数排序时间为 合并排序算法对n个随机数互换次数为迅速排序算法对n个

24、随机数排序时间为 迅速排序算法对n个随机数互换次数为 排序后，前50个有序元素为：四、顾客使用阐明（可选）1、本程序的运营环境为DOS操作系统，执行文献为conversion.exe2、运营程序时输入 请输入排序规模：/提示输入 等待输入 输出 插入排序算法对n个随机数排序时间为 插入排序算法对n个随机数互换次数为 冒泡排序算法对n个随机数排序时间为 冒泡排序算法对n个随机数互换次数为 堆排序算法对n个随机数排序时间为 堆排序算法对n个随机数互换次数为 合并排序算法对n个随机数排序时间为 合并排序算法对n个随机数互换次数为迅速排序算法对n个随机数排序时间为 迅速排序算法对n个随机数互换次数为

25、排序后，前50个有序元素为：五：实现图1 控制台程序实验成果：实验分别实现插入排序、冒泡排序、堆排序、合并排序、迅速排序，以不同规模（100，1000，5000，10000，100000个数据）的随机数作为测试数据集，实验成果截图如下：排序规模为100排序规模为：1000排序规模为：排序规模为：5000排序规模为：10000排序规模为：100000（六）算法性能分析在程序中我们根据数据规模的不同产生不同的随机整型数组，然后分别让不同的排序算法来进行从小到大的排序。这里需要注意的是：每种排序算法在相似的输入规模中原始无序数据都是同样的。例如五种排序算法要对长度为100的无序数组进行排序，它们所要

26、排序的无序数组都是同样的，我们以此来保证明验的公正性。在这里我们觉得比较次数是排序算法的重要操作，因此我们在每个排序算法中加入计数器来记录排序过程中的比较次数，以此来作为对算法性能分析的重要参数（排序时间作为辅助参数）。表1为在输入规模分别为100，1000，5000，10000，100000时各个算法的元素互换次数。表2为在输入规模分别为100，1000，5000，10000，100000时各个算法的排序时间。 排序规模（n） 算法1001000500010000100000插入排序2782246255983211626605224870816冒泡排序26842496315859567902

27、245堆排序100016480370631060262319032985016合并排序555871919432553011204091536596迅速排序5991037723702714311528791946925表1 排序算法比较次数性能比较 排序规模（n） 算法1001000500010000100000插入排序0.04523.058312.126358.2854177.5416694冒泡排序0.10079.4697621.3535133.777526.97142698.7堆排序0.07370.5794671.284443.595778.03182102.961合并排序0.37092.1

28、91434.1192511.679420.8016192.61迅速排序0.03350.2029530.4287681.31712.6953129.9569表2 排序算法排序时间比较（单位ms）为了直观起见，根据实验数据画出多种排序算法在不同输入规模下互换次数的变化趋势图如图2所示：图2排序算法互换次数趋势图由上图我们基本上看出插入排序和冒泡排序的比较次数随输入规模的呈非线性增长，而后三种排序措施堆排序，合并排序，迅速排序的比较次数随输入规模的增长基本呈线性变化趋势。根据实验数据画出多种排序算法在不同输入规模下互换次数的变化趋势图如图3所示：图3排序算法排序时间趋势图（单位：ms）实验成果与我们

29、对这五种算法的性能理论分析基本吻合：插入排序与冒泡排序的时间复杂度为O(n*n)，而后三种排序算法的时间复杂度为O(nlogn)。图4还显示出虽然冒泡排序和插入排序的时间复杂度相似，但插入排序的性能仍然比冒泡排序好，特别在排序时间方面。（七）结论最后得出结论：时间性能上，迅速排序 堆排序 合并排序 插入排序 冒泡排序互换次数上，合并排序 迅速排序 堆排序 冒泡排序 插入排序(八)心得 作为拿来复习的一种报告还是蛮有成就感的，但是输入1000000个数据的时候等得太久，实在等不出成果，并且放入值太大不以便作图，于是就不参与数据分析，但是估计成果应当相似。此前不懂排序只会用冒泡，由于冒泡排序是接触

30、编程的第一种排序，印象很深刻，并且几乎不会用错，当数据比较大时它的弊端就真的浮现了。本觉得这个实验还是比较好做的，排序几乎都会，连助教都说一句你这个选题太没难度了。但是平心而论，真正实现起来还真是问题多多，一方面是怎么样调用时间的问题，这也是第一种先想的问题，本来打算就只比较互换次数和比较次数的，但是这些其实没有比时间更直观的反映排序的效率。寻找半天无果本来都打算放弃了，成果居然有一种答复贴说QueryPerformanceCounter函数，于是就发现这个问题可以解决了。成果是想象的有点偏差，没想到堆排序的速度也能这样快，合并排序的次数会那么少。本觉得迅速排序就是万能的了，看来想多了。或许后来在研究算法方面的确需要好好分析效率，数据构造的确是一门很有用的学科，后来不能丢弃。