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

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

2、，如图、表等。(3) 算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。(4) 实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。(5) 要给出实验的方案及其分析。说明本题重点在以下几个方面：理解和掌握以实验方式比较算法性能的方法；掌握测试实验方案的设计； 理解并实现测试数据的产生方法；掌握实验数据的分析和结论提炼；实验结果汇报等。一、需求分析(1) 输入的形式和输入值的范围： 本程序要求实现各种算法的时间性能的比较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。用户输入随机数的个数 n，然后调用随机事件函数产生 n 个随机数，对这些随机数进行排序。于是数据

3、为整数(2) 输出的形式：输出在各种数目的随机数下， 各种排序算法所用的时间和比较次数。(3) 程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。（ 4）测试数据：略二、概要设计标准文档实用文案1. 抽象数据类型ADT List数据对象D ai | ai ElemSet, i=1,2,.,n, n 0 数据关系R1 <ai-1 ,ai >|ai-1 ,ai D, i=2,.,n 基本操作virtual void clear() = 0;bool insert(const Elem&) = 0;bool a

4、ppend(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） 处理

5、模块：系统产生 n 个随机数，对随机数进行排序（ 3） 输出模块：将排序的结果输出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);sran

7、d(time(NULL);for(unsigned long int m=0;m<num;m+)ram=rand();cout<<endl;return ra;（ 2）快速排序：要实现快速排序首先选择一个轴值，这里选取数组第一个为轴值。定义两个标识 low,high 。 high 标识最后一个元素的位置，从后向前，将关键字与轴值比较，直至遇到小于轴值的关键字，前移， low 标识在第二个元素的位置，从前向后，将关键字与轴值比较，直至遇到大于轴值的关键字，后移。当 low,high 相遇后第一趟排序结束。 调整数列，轴值左边的为比轴值小的，右边为比轴值大的。对轴值左边（即low

8、 到 pivotkey-1的数）和右边的子列（ pivotkey+1 到 high 的数）分别进行上述递归快速排序，直到范围为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=pivot

9、key;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）插入排序：插入排序的思想是将一组无序的元素分别插入一个已经有序的的数组里，并保证插入后的数组也是有序的。当所有无序组的元素都插入完毕时，一个有序数组构造完成。数组 n1 r 为初始的一个无序数组（为了直观起见，我们这里

10、设定数组从 1 开始，而不是 0），则 n1 默认为只有一个元素的有序数组， n2 插入只有 n1 构成的有序数组中，则此时有序数组的元素数量变为 2。以此类推，到第 i 个元素时，前 i-1 个元素已经是有序的，此时只需将第i 个元素插入到有序数组中并使之保持有序。如此直至最后一个元素插入完毕，整个插入排序完成。void Sort:insertSort(unsigned long int *s)this->setNum();LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg

11、);QueryPerformanceCounter(&Count1);/ 获取时间 Count1 double d;int temp,j;for (unsigned long int 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);/ 获取时间 Count2 d=(d

12、ouble)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间差， d的单位为 ms.cout<<"插 入 排 序 算 法 对 "<<this->RanNum<<"个 随 机 数 排 序 时 间 为 为 "<<d<<"ms."<<endl;cout<<" 插 入 排 序 算 法 对 "<<this->RanNum<&l

13、t;" 个 随 机 数 交 换 次 数 为 "<<this->SortNum<<" 次。 "<<endl;标准文档实用文案(4) 冒泡排序（ bubble sort ）：将被排序的记录数组 R1.n 垂直排列，每个记录 Ri 看作是重量为 Ri.key 的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组 R：凡扫描到违反本原则的轻气泡，就使其向上 " 飘浮 " 。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、

14、重者在上，则交换二者的位置。即依次比较 (Rn ，Rn-1) ，(Rn-1，Rn-2) ， ，(R2 ，R1) ；对于每对气泡 (Rj+1，Rj)，若 Rj+1.key<Rj.key，则交换 Rj+1 和 Rj的内容。第一趟扫描完毕时，" 最轻 " 的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R1 上。扫描R2.n。扫描完毕时， " 次轻 " 的气泡飘浮到 R2 的位置上 最后，经过n-1趟扫描可得到有序区R1.nvoid Sort:bubbleSort(unsigned long int *s)this->setNum();

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

16、>SortNum+;QueryPerformanceCounter(&Count2);/获取时间 Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间差， d的单位为 ms.cout<<" 冒泡排序算法对"<<this->RanNum<<" 个随机数排序时间为"<<d<<"ms."<<endl;cout<<"

17、 冒泡排序算法对"<<this->RanNum<<" 个随机数交换次数为"<<this->SortNum<<"次。 "<<endl;(5) 堆排序：堆排序与其他排序算法最大的区别是它依靠一种特殊的数据结标准文档实用文案构堆来进行排序。堆是一种完全二叉树，并且根节点不大于左右子树中的所有节点， ni<=n2*i&&ni<=n2*i+1。因此堆排序算法首先要将给出的无序数组构造成一个堆，然后输出根节点（最小元素） ，将剩余元素重新恢复成堆，再次输出根

18、节点。依次类推，直至最后一个节点输出，此时堆排序完成。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

19、;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,C

20、ount2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/获取时间 Count1标准文档实用文案double d;this->heapCreat(s1,this->RanNum);for(i=0;i<this->RanNum;i+)s2i=s11;s11=s1num;this->heapRestor(s1,1,-num);QueryPerformanceCounter(&Count2);/ 获取时间 Count2 d=(double)(Count2.Qu

21、adPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/计算时间差， d的单位为 ms.cout<<" 堆排序算法对"<<this->RanNum<<" 个随机数排序时间为为"<<d<<"ms."<<endl;cout<<" 堆排序算法对"<<this->RanNum<<" 个随机数交换次数为"<<this->

22、;SortNum<<"次。 "<<endl;(6) 合并排序：这里的合并排序和下边要描述的快速排序都采用了分而治之的思想，但两者仍然有很大差异。 合并排序是将一个无序数组 n1 r 分成两个数组 n1 r/2 与 nr/2+1 r ，分别对这两个小数组进行合并排序，然后再将这两个数组合并成一个大数组。由此我们看出合并排序时一个递归过程（非递归合并排序这里不做讨论） 。合并排序的主要工作便是“合并” ，两个小规模数组合并成大的，两个大的再合并成更大的，当然元素比较式在合并的过程中进行的。void Sort:mergeSort(unsigned long

23、 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+;thi

24、s->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>清空。释放数组，将数组大小和栅栏置

25、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 (fe

26、nce <= 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 &g

27、t;= 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) 。最

28、坏情况 ( 非递增 ) 下，最多比较 i 次，因此需要的比较次数是：所以，时间复杂度为 O(n2) 。<2>冒泡排序： 当原始数据正向有序时，冒泡排序出现最好情况。此时，只需进行一趟排序，作n-1 次关键字比较，因此最好情况下的时间复杂度是O(n) 。当原始数据反向有序时，冒泡排序出现最坏情况。此时，需进行 n-1 趟排序，第 i 趟作 (n-i) 次关键字间的比较，并且需执行 (n-i) 次元素交换，所以，比较次数标准文档实用文案为：因此 , 最坏情况下的时间复杂度为O(n2 )<3>快速排序：如果每一次分划操作后， 左、右两个子序列的长度基本相等，则快速排序的效率最

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

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

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

32、机数交换次数为合并排序算法对 n 个随机数排序时间为合并排序算法对 n 个随机数交换次数为快速排序算法对 n 个随机数排序时间为快速排序算法对 n 个随机数交换次数为标准文档实用文案排序后，前 50 个有序元素为：五：实现图 1 控制台程序实验结果：实验分别实现插入排序、冒泡排序、堆排序、合并排序、快速排序，以不同规模（ 100，1000，2000，5000，10000， 100000 个数据）的随机数作为测试数据集，实验结果截图如下：标准文档实用文案排序规模为100排序规模为：1000标准文档实用文案排序规模为：2000排序规模为：5000标准文档实用文案排序规模为：10000排序规模为：1

33、00000标准文档实用文案（六）算法性能分析在程序中我们根据数据规模的不同产生不同的随机整型数组， 然后分别让不同的排序算法来进行从小到大的排序。 这里需要注意的是： 每种排序算法在相同的输入规模中原始无序数据都是一样的。 例如五种排序算法要对长度为 100 的无序数组进行排序， 它们所要排序的无序数组都是一样的， 我们以此来保证实验的公正性。在这里我们认为比较次数是排序算法的主要操作， 因此我们在每个排序算法中加入计数器来记录排序过程中的比较次数， 以此来作为对算法性能分析的主要参数（排序时间作为辅助参数） 。表 1 为在输入规模分别为 100，1000，2000，5000，10000，10

34、0000 时各个算法的元素交换次数。 表 2 为在输入规模分别为 100，1000，2000，5000，10000， 100000 时各个算法的排序时间。排序规模（ n）10010002000500010000100000算法插入排序27822462559832116266052248708162509250617冒泡排序26842420119631585956790224520141127169842堆排序100016480370631060262319032985016合并排序555871919432553011204091536596快速排序5991037723702714311528791946925表 1 排序算法比较次数性能比较排序规模（ n）10010002000500010000100000算法插入排序0.04523.058312.126358.2854177.54