各种算法地性能分析报告

1、实验项目一各种排序算法的性能测试第一章：简介(Introduction)排序就是将一个记录的无序序列调整成为一个有序序列的过程。在对记录进行排序的 时候，需要选定一个信息作为排序的依据，例如，可以按学生姓名对学生记录进行排序，这个特别选定的信息称为关键码。排序的主要目的是为了进行快速查找，这就是为什么字典、电话薄和班级名册都是排 好序的。在数据结构课程中，我们已经学过了几种内部排序算法，没有一种排序算法在任何情 况下都是最好的解决方案，有些排序算法比较简单， 但速度相对比较慢； 有些排序算法速度比较快，但却很复杂。1. 冒泡排序：设想被排序的数组 R1.N垂直竖立，将每个数据元素看作有重量的气

2、泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R,凡扫描到违反本原则的轻气泡，就使其向上”漂浮”(交换位置)，如此反复进行，直至最后任何两个气泡都是轻者在上， 重者在下为止。若记录序列的初始状态为”正序”，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行 n-1次比较，且不移动记录；反之，若记录序列的初始状态为”逆序”，则需进行n(n-1 )/2次比较和记录移动。因此冒泡排序总的时间复杂度为0(n*n)。2. 快速排序：快速排序(quicksort )是对冒泡排序的一种改进。由 C. A. R. Hoare在1962年提出。 它的基本思想是：通过一趟排序将要排序的数据分割成独立的两

3、部分，其中一部分的所有数 据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序， 整个排序过程可以递归进行，以此达到整个数据变成有序序列。3. 选择排序：每一趟从待排序的数据元素中选出最小(或最大)的一个元素，顺序放在已排好序的数 列的最后，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。通俗的解释：对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束

4、的时候， 我们应该找到了最小的那个数的下标了，然后进行判断，如 果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值， 以此类推。第二章：算法定义(Algorithm Specification )1.冒泡排序通过对待排序序列从后向前(从下标较大的元素开始)，依次比较相邻元素 的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部 (从下 标较大的单元移向下标较小的单元)，就象水底下的气泡一样逐渐向上冒。冒泡排序算法如下：void bubblesort。nt a,int n)/冒

5、泡排序 C语言描述，待排序的元素放在数组中int i,j;int temp;for(i=0;i< n-1;i+)for(j=n-1;j>i;j-)if(aj-1>aj)temp=aj_1;aj-1=aj;aj=temp;2快速排序任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排 序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准 元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。void quicksort nt a,i nt start,i nt en d)快速排序int i,j,

6、mid;i=start;j=end;mid=ai;while(start>=e nd)return;while(i<j)while(i<j && aj>mid)j-;if(i<j)ai=aj;i+;while(i<j && ai<mid)i+;if(i<j)aj=ai;j-;ai=mid;quicksort(a,start,i-1);/递归调用快速排序继续对前半部分的元素进行排序quicksort(a,i+1,e nd);/递归调用快速排序继续对后半部分的元素进行排序3.选择排序假设待排序的列表的n个数据元素放在数

7、组a中，第一次从n个数据元素中 找出最小的元素与a0交换，第二次从剩下的n-1个元素中找出最小的元素与a1交换，直到第n-1次在剩下的两个元素中找出最小的元素与an-1交换，剩下的最后一个元素的位置就在an.选择排序算法如下：void selectsort(i nt a,i nt n)/选择排序int i,j;int min, temp;for(i=0;i <n _1;i+)min=i;for(j=i+1;j <n ;j+)if(aj<ami n)min=j;temp=ami n;ami n=ai;ai=temp;第三章：测试结果（Testi ng Results ）算法随机

8、数组兀素个数（个）算法排序时间（seconds）10000.00300冒泡排序20000.00900030000.02100040000.03900050000.069000100000.26900010000.00800020000.014000快速排序30000.02800040000.04100050000.022000100000.00200010000.00500020000.021000选择排序30000.04200040000.04900050000.035000100000.159000三种算法排序时间散点图+冒泡排序时间 快速排序时间选择排序时间注：横轴为随机数个数，纵轴为排

9、序时间（1/100）第四章：分析和讨论1.冒泡排序如果有n个数，则要进行n-1趟比较。在第1趟比较中要进行n-1次相邻元素的 两两比较，在第j趟比较中要进行n-j次两两比较。比较的顺序从前往后，经过 一趟比较后，将最值沉底（换到最后一个元素位置），最大值沉底为升序，最小 值沉底为降序。（1）算法的最好时间复杂度若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较 次数J和记录移动次数I均达到最小值：min =n-1min =0。冒泡排序最好的时间复杂度为O(n)。（2 ）算法的最坏时间复杂度若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较（1W i W

10、n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和 移动次数均达到最大值：J max =n(n-1)/2=0( n 2 )2I max =3n(n-1)/2=0( n )冒泡排序的最坏时间复杂度为0(n2 )。(3) 算法的平均时间复杂度为0(n2 )虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平 均时间性能比直接插入排序要差得多。(4) 算法稳定性冒泡排序是就地排序，且它是稳定的。2快速排序：(1)算法的最坏时间复杂度无论适用哪一种方法来选择基准 pivot，由于我们不知道各个元素间的相对大小 关系(若知道就已经排好序了)，所以我们无法确定pi

11、vot的选择对划分造成的 影响。因此对各种pivot选择法而言，最坏情况和最好情况都是相同的。我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候(设输入的表有n个元素)。下面我们暂时认为该 猜测正确，在后文我们再详细证明该猜测。对于有n个元素的表pi，由于函数Partition的计算时间为B( n)，所以快速排序在序坏情况下的复杂性有递归式如下：T(1)= 0( 1),T(n)=T(n-1)+T(1)+B( n) (1)用迭代法可以解出上式的解为T(n)= 0( n2)。这个最坏情况运行时间与插入排序是一样的。下面我们来证明这种每次划分过程产生的

12、两个区间分别包含n-1个元素和1个元素的情况就是最坏情况。设T(n)是过程quicksort作用于规模为n的输入上的最坏情况的时间，则T(n)=max(T(i)+T(n-i)+0( n)，其中 1W i w n-1 (2)我们假设对于任何 k<n，总有T(k) w ck，其中c为常数；显然当k=1时是成立的。将归纳假设代入(2)，得到：T(n) < max(ci2+c( n-i)2)+B(n )=c*max(i2+( n-i)2)+B( n)因为在1,n-1上i2+(n-i)2关于i递减，所以当i=1时i2+(n-i)2 有最大值n2-2(n-1 )。于是有：T(n )w cn2-

13、2c(n-1)+0( n)w cn2只要c足够大，上面的第二个小于等于号就可以成立。于是对于所有的n都有T(n )< cn。这样，排序算法的最坏情况运行时间为0(n2),且最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候，时间复杂度为0(n2)。(2)算法的最好时间复杂度如果每次划分过程产生的区间大小都为n/2，则快速排序法运行就快得多了。这时有：T(n)=2T(n/2)+0( n),T(1)= 0( 1) (3)解得：T(n)= 0( nlogn)由于快速排序法也是基于比较的排序法，其运行时间为Q (nlogn),所以如果每次划分过程产生的区间大小都为n/2

14、，则运行时间0( nlogn )就是最好情况运行时间。(3 )算法的平均时间复杂度要想对快速排序的平均情况有个较为清楚的概念，我们就要对遇到的各种输入作个假设。通常都假设输入数据的所有排列都是等可能的。当我们对一个随机的输入数组应用快速排序时，要想在每一层上都有同样的划分是不太可能的。 我们所能期望的是某些划分较对称，另一些则很不对称。平均情况下，Partition 产生的划分中既有 “好的”，又有“差的”。这时，与Partition执行过程对应的递归树中，好、差划分是随机地分布在树的各层上的。为与我们的直觉相一致，假设好、差划分交替出现在树的各层上，且好的划分是最佳情况划分，而 差的划分是最

15、坏情况下的划分。在表pi处，划分的代价为n,划分出来的两个子表的大小为n-1和1,即最坏情况。在表的下一层pn-1处，大小为n-1的子表按最佳情况划分成大小各为(n-1)/2的两个子表。在一个差的划分后接一个好的划分后，产生出三个子表，大小各为1, (n-1)/2和(n-1)/2，代价共为2n-仁0(n)。从直觉上看，差的划分的代价0(n)可被吸收到好的划分的代价0(n)中去，结果是一个好的划分。这样，当好、差划分交替分布划分都是好的一样：仍是0 (nlogn )，但0记号中隐含的常数因子要略大一些，快速算法的平均时间复杂度为O(nlogn)。3.选择排序：每趟选出一个最值和无序序列的第一个数

16、交换，n个数共选n-1趟。第i趟假设i为最值下标，然后将最值和i+1至最后一个数比较，找出最值的下标，若最值下标不为初设值，则将最值元素和下标为i的元素交换。选择排序不关心表的初始次序，它的最坏情况的排序时 间与其最佳情况没多少区别，其比较次数为n(n-1)/2 ，时间复杂度为 O(n2 )。所以有：(1) 算法的最好时间复杂度 为0(n2 )(2) 算法的最坏时间复杂度 为0(n2 )："(3) 算法的平均时间复杂度为0(n2 )对于序列初始状态基本有正序，可选择对有序性较敏感的如冒泡排序、选择排序等方法 对于序列长度比较大的随机序列，应选择平均时间复杂度较小的快速排序方法。各种排

17、序算法都有各自的优缺点，适应于不同的应用环境，因此在选择一种排序算法解决实际问题之前，应当先分析实际问题的类型，再结合各算法的特点，选择一种合适的算法。附录：源代码(基于C语言的)#i nclude "stdio.h"#i nclude "time.h"#i nclude "stdlib.h"#define SIZE 10000 /待排序数组的规模#define PRT_RT 0/控制是否显示排序后的数组的常量PRT_RT=1，则显示输出,为0则不输出void bubblesort( int m, int n) /冒泡排序算法，待排序

18、元素存放在数组 n中 int i,j;int temp;for (i=0;i<n-1;i+)for (j=n-1;j>i;j-)if (mj-1>mj)temp=mj-1;mj-1=mj;mj=temp;void selectsort( int k, int n) /选择排序算法，待排序元素存放在数组 k中 int i,j;int min,temp;for (i=0;i<n-1;i+) min=i;for (j=i+1;j<n;j+)if (kj<kmin)min=j;temp=kmi n;kmi n=ki;ki=temp;void quicksortint

19、 p, int start, int end) / 快速排序算法，待排序元素存放在数组p中int i,j,mid;i=start;j=e nd;mid=pi;while (start>=end)return ;while (i<j)while (i<j && pj>mid)j-;if (i<j)pi=pj;i+;while (i<j && pi<mid)i+;if (i<j)pj=pi;j-;pi=mid;quicksort(p,start,i-1); /递归调用快速排序对数组前半部分元素进行排 quicksort

20、(p,i+1,e nd);/递归调用快速排序继续对数组后半部分元素进行排序int main() /返回值类型为整型的主函数int i;long start,end;/定义两个存放时间的变量double duration;/定义一个存放计算时间的变量int *a; /定义指针变量为随机数分配存储空间a=(int *)malloc( sizeof (int )*SIZE); / 分配SIZE字节的存储空间srand( unsigned )time(NULL); /设置时间作为随机函数的种子 for (i=0;i<SIZE;i+)/ 随机赋值ai=rand()%SIZE; / 取0,SIZE间

21、的随机整数/如果PRT_RT=,1则输出待排序的序列，否则输出：“不输出待排序序列” if (PRT_RT = 1)printf( "%d " ,ai);/ 输出这个数组elseprintf("不输出待排序序列");printf( "n");printf("各种算法排序时间及排序后序列如下：");printf( "n");/以下统计冒泡排序时间start=clock();bubblesort(a,SIZE); /在这里插入你要计算时间的算法，这里计算的是冒 泡排序算法当规模为SIZE的时候的算法

22、的时间end = clock();duration=( double )(end-start)/CLOCKS_PER_SEC;printf( "the bubblesort time is :%f seco nds",duratio n); / 输出冒泡排序时间printf( "n");/以下显示冒泡排序结果，如果PRT_RT=,1则输出排序后的序列，否则输 出：“不输出冒泡排序后序列”if (PRT_RT = 1)for (i=0; i<SIZE; i+)printf( "%d ", ai);elseprintf("

23、不输出冒泡排序后的序列");printf( "n");printf( "n");system( "pause");/以下统计快速排序时间start = clock();quicksort(a,0,SIZE-1); /在这里插入你要计算时间的算法，这里计算的是 快速排序算法当规模为SIZE的时候的算法的时间end = clock();duration = ( double )(e nd-start)/CLOCKS_PER_SEC;printf( "the quicksort time is :%f sec on ds",duratio n);/ 输出统计最后时间printf( "n");/