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

1、HUNANUNIVERSITY课程实习报告题 目： 排序算法的时间性能学生姓名 学生学号专业班级指导老师 李晓鸿 完 成 日 期设计一组实验来比较下列排序算法的时间性能 快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为比较的对象）要求 (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 ,ai >|ai-1 ,aiD, i=2,.,n 基本操作 virtual void clear() = 0;bool insert(const Elem&) = 0;bool append(const Elem&) = 0;lbool re

4、move(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） 输出模块：将排序的结果输出

5、3.算法的基本思想1、 随机数的产生：利用srand()产生随机数。2、 快速排序：选定一记录R，将所有其他记录关键字k与记录R的关键字k比较, 若k<k则将记录换至R之前,若k >k 则将记录换至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;m<num;m+)ram=rand();cou

7、t<<endl;return ra;（2）快速排序：要实现快速排序首先选择一个轴值，这里选取数组第一个为轴值。定义两个标识low,high。high标识最后一个元素的位置，从后向前，将关键字与轴值比较，直至遇到小于轴值的关键字，前移，low标识在第二个元素的位置，从前向后，将关键字与轴值比较，直至遇到大于轴值的关键字，后移。当low,high相遇后第一趟排序结束。调整数列，轴值左边的为比轴值小的，右边为比轴值大的。对轴值左边（即low到pivotkey-1的数）和右边的子列（pivotkey+1到high的数）分别进行上述递归快速排序，直到范围为1结束。int partition(

8、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 pivot

9、loc; if(low<high) pivotloc=partition(a,low,high);/一趟排序结果的调用 qsort(a,low,pivotloc-1); qsort(a,pivotloc+1,high); （3）插入排序：插入排序的思想是将一组无序的元素分别插入一个已经有序的的数组里，并保证插入后的数组也是有序的。当所有无序组的元素都插入完毕时，一个有序数组构造完成。数组n1r为初始的一个无序数组（为了直观起见，我们这里设定数组从1开始，而不是0），则n1默认为只有一个元素的有序数组，n2插入只有n1构成的有序数组中，则此时有序数组的元素数量变为2。以此类推，到第i个元素

10、时，前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

11、 i=0;i<this->getRanNum();i+)j=i;temp=si;while (j>=1 && temp<sj-1)sj=sj-1;j-;this->SortNum+;if(j>1)this->SortNum+;sj=temp;QueryPerformanceCounter(&Count2);/获取时间Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间差，d的单位为ms.cout<<&q

12、uot;插入排序算法对"<<this->RanNum<<"个随机数排序时间为为"<<d<<" ms."<<endl;cout<<"插入排序算法对"<<this->RanNum<<"个随机数交换次数为"<<this->SortNum<<"次。"<<endl;(4) 冒泡排序（bubble sort）：将被排序的记录数组R1.n垂直排列，每个

13、记录Ri看作是重量为Ri.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(Rn，Rn-1)，(Rn-1，Rn-2)，(R2，R1)；对于每对气泡(Rj+1，Rj)，若Rj+1.key<Rj.key，则交换Rj+1和Rj的内容。第一趟扫描完毕时，"最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R1上。扫

14、描R2.n。扫描完毕时，"次轻"的气泡飘浮到R2的位置上最后，经过n-1 趟扫描可得到有序区R1.nvoid Sort:bubbleSort(unsigned long int *s)this->setNum();LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/获取时间Count1double d;unsigned long int temp;for(unsigne

15、d 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);/获取时间Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间差，d的单位为ms.cout<<"冒泡排序算法对&qu

16、ot;<<this->RanNum<<"个随机数排序时间为"<<d<<" ms."<<endl;cout<<"冒泡排序算法对"<<this->RanNum<<"个随机数交换次数为"<<this->SortNum<<"次。"<<endl; (5) 堆排序：堆排序与其他排序算法最大的区别是它依靠一种特殊的数据结构堆来进行排序。堆是一种完全二叉树，并且根

17、节点不大于左右子树中的所有节点，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->heapResto

18、r(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,uns

19、igned 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;thi

20、s->heapRestor(s1,1,-num);QueryPerformanceCounter(&Count2);/获取时间Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间差，d的单位为ms.cout<<"堆排序算法对"<<this->RanNum<<"个随机数排序时间为为"<<d<<" ms."<<endl;cout<

21、;<"堆排序算法对"<<this->RanNum<<"个随机数交换次数为"<<this->SortNum<<"次。"<<endl; (6) 合并排序：这里的合并排序和下边要描述的快速排序都采用了分而治之的思想，但两者仍然有很大差异。合并排序是将一个无序数组n1r分成两个数组n1r/2与nr/2+1r，分别对这两个小数组进行合并排序，然后再将这两个数组合并成一个大数组。由此我们看出合并排序时一个递归过程（非递归合并排序这里不做讨论）。合并排序的主要工作便是“合

22、并”，两个小规模数组合并成大的，两个大的再合并成更大的，当然元素比较式在合并的过程中进行的。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

23、=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; li

24、stArray = 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 pre

25、v() 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)

26、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-

27、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>快速排序

28、：如果每一次分划操作后，左、右两个子序列的长度基本相等，则快速排序的效率最高，其最好情况时间复杂度为O(nlog2n)；反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，此时，快速排序效率最低，其最坏情况时间复杂度为O(n2)。如果选择左边第一个元素为主元，则快速排序的最坏情况发生在原始序列正向有序或反向有序时。快速排序的平均情况时间复杂度为O(nlog2n)。<4>堆排序：堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为O(nlogn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比

29、较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是不稳定的，算法时间复杂度O(nlogn)。<5>归并排序：在最佳、平均、最差情况下，时间复杂度为Q(n log n)，不足的就是需要两倍的空间代价，当输入的待排序数据存储在链表中时，归并排序是一个很好的选择.（5）函数的调用关系图用户输入排序的元素个数n产生n个随机数主程序对随机数进行排序输出（6）输入和输出的格式输入 请输入排序规模：/提示输入 等待输入 输出 插入排序算法对n个随机数排序时间为 插入排序算法对n个随机数交换次数为 冒泡排序算法对n个随机数排序时间为 冒泡排序算法对n个随机数交换次数为 堆排序算法对n个随机数

30、排序时间为 堆排序算法对n个随机数交换次数为 合并排序算法对n个随机数排序时间为 合并排序算法对n个随机数交换次数为快速排序算法对n个随机数排序时间为 快速排序算法对n个随机数交换次数为 排序后，前50个有序元素为：四、用户使用说明（可选）2、运行程序时输入 请输入排序规模：/提示输入 等待输入 输出 插入排序算法对n个随机数排序时间为 插入排序算法对n个随机数交换次数为 冒泡排序算法对n个随机数排序时间为 冒泡排序算法对n个随机数交换次数为 堆排序算法对n个随机数排序时间为 堆排序算法对n个随机数交换次数为 合并排序算法对n个随机数排序时间为 合并排序算法对n个随机数交换次数为快速排序算法对

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

32、数据都是一样的。例如五种排序算法要对长度为100的无序数组进行排序，它们所要排序的无序数组都是一样的，我们以此来保证实验的公正性。在这里我们认为比较次数是排序算法的主要操作，因此我们在每个排序算法中加入计数器来记录排序过程中的比较次数，以此来作为对算法性能分析的主要参数（排序时间作为辅助参数）。表1为在输入规模分别为100，1000，2000，5000，10000，100000时各个算法的元素交换次数。表2为在输入规模分别为100，1000，2000，5000，10000，100000时各个算法的排序时间。 排序规模（n） 算法10010002000500010000100000插入排序27822462559832116266052248708162509250617冒泡排序26842420119631585956790224520141127169842堆排