《各种排序算法的性能测试.doc》由会员分享,可在线阅读,更多相关《各种排序算法的性能测试.doc(13页珍藏版)》请在金锄头文库上搜索。
1、组的编号:28 作者姓名 : xxx xxx xxx实验名称:各种排序算法的性能测试算法设计与分析完成日期:2013年9月1日星期日 目录第一章:简介1第二章:算法规范2数据结构2伪代码3第三章:算法测试4随机数比较4最优表5最差表5第四章:分析讨论6算法分析6时间复杂度分析6附录7声明7第1章 :简介 问题的描述: 排序的主要目的是为了进行快速查找。排序就是将一个记录的无序序列调整成为一个有序序列的过程。在对记录进行排序的时候,需要选定一个信息作为排序的依据。 在数据结构课程中,我们已经学过了几种内部排序算法,没有一种排序算法在任何情况下都是最好的解决方案,有些排序算法比较简单,但速度相对比
2、较慢;有些排序算法速度比较快,但却很复杂。 利用随机函数产生N个随机整数(N=5000),利用冒泡排序,选择排序,快速排序(结果由小到大的排序)并统计每一种排序所消耗的时间。把排序花的时间排在表格里面。 第二章:算法规范数据结构:在所有的三个排序策略中,我们用了数组,函数作为主要的数据结构。因为我们只是测试了不同排序所需要的时间,没涉及其他复杂的操作,所以在这个项目中用了静态实现数组就可以。伪代码如下所示冒泡排序:1. int i,j,l,aN;2. 循环i从0到N-12.1. 产生随机数到ai;2.2. 输出随机数组(无序);3. 循环i:0到N-13.1循环j:0到N-1;3.2if ai
3、ai+1;aiai+1;3.3输出有序随机数组;选择排序:1.int i,j,l,aN,k;2.循环i从0到N-12.1产生随机数到ai;2.2输出随机数组(无序);3循环i:0到N-13.1循环j:i+1到N-1;3.2if aiai+1;aiaj;3.3输出有序随机数组;快速排序:1. int i,t,l,aN,mid,dataN,start,end;2.循环i从0到N2.1产生随机数到ai;2.2输出随机数组(无序);3. while startend 3.1 While start=mid3.2 while startend 和 dataendmid3.3输出有序随机数组; 第三章:测
4、试结果一:随机数比较表一:*随机数冒泡快速选择1000.0000000.0000000.00100010000.0070000.0000000.01300020000.0270000.0010000.03400040000.0720000.0000000.087000100000.3460000.0000000.376000200001.4000000.0000001.592000400005.8860000.0010006.305000注:该数据时间为注释数据的输出语句,运行程序所得的时间(s)图一:二:最优表表二:最优(升序)冒泡快速选择1000.0000000.0000000.00100
5、010000.0020000.0010000.00400020000.0320000.0000000.01700040000.0630000.0000000.048000100000.1870000.0000000.180000200000.7530000.0010000.594000400002.9600000.0000002.319000注:该数据时间为注释数据的输出语句,运行程序所得的时间(s)图二:三:最差表表三:最差(逆序)冒泡快速选择1000.0000000.0000000.00100010000.0070000.0000000.00800020000.0140000.000000
6、0.02700040000.0620000.0000000.089000100000.2700000.0000000.252000200000.9690000.0000000.949000400003.8190000.0010003.756000注:该数据时间为注释数据的输出语句,运行程序所得的时间(s)图三:第四章:分析和讨论(一)算法思想分析:1冒泡排序:通过对待排序序列从后向前(从下标较大的元素开始),依次比较相邻元素的排序码,若发现逆序则交换,使排序码较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元),就象水底下的气泡一样逐渐向上冒。2选择排序:假设待排序的列表的n个数
7、据元素放在数组a中,第一次从n个数据元素中找出最小的元素与a0交换,第二次从剩下的n-1个元素中找出最小的元素与a1交换,直到第n-1次在剩下的两个元素中找出最小的元素与an-1交换,剩下的最后一个元素的位置就在an.3快速排序:任取待排序序列中的某个元素作为基准(一般取第一个元素),通过一趟排序,将待排元素分为左右两个子序列,左子序列元素的排序码均小于或等于基准元素的排序码,右子序列的排序码则大于基准元素的排序码,然后分别对两个子序列继续进行排序,直至整个序列有序。(二)时间复杂度分析排序算法最差时间时间复杂度是否稳定?冒泡排序O(n2)O(n2)稳定选择排序O(n2)O(n2)稳定快速排序
8、O(n2)O(n* log2n)不稳定附录:源代码(基于c语言) #include#include#include#define N 40000void BubbleSort()/冒泡排序int i,j,l;int aN;for(i=0;iN;i+)ai=N-i;/最差情况,数组数据逆序/ai=i;/最优情况,数组数据正序/ai=(int)rand();/printf(%d ,ai);/输出无序随机数数组printf(n);printf(*);printf(n);for(i=0;ii;j-)if(aj-1aj)l=aj-1;aj-1=aj;aj=l;/printf(%dn,ai);/输出有序数
9、组int QuickSort()/快速排序 int i,t; int aN; int mid; int dataN; int start=0; int end=N; for(i=0;iN;i+) ai=N-i;/最差情况,数组数据逆序 /ai=i;/最优情况,数组数据正序/ai=(int)rand();/printf(%d ,ai);/输出无序随机数数组 printf(n); data0=datastart; mid=datastart; while(startend) while(start=mid) -end; t=dataend;dataend=datastart;datastart=t
10、; while(startend)&(dataendmid) +start; t=datastart;datastart=dataend; dataend=t; datastart=data0; return start;void ChooseSort()/选择排序int i,j,k,l;int aN;for(i=0;iN;i+)ai=N-i;/最差情况,数组数据逆序/ai=i;/最优情况,数组数据正序/ai=(int)rand();/printf(%d ,ai);输出无序随机数数组printf(n);printf(*);printf(n);for(i=0;iN;i+)k=i;for(j=i+
11、1;jaj)l=ai;ai=aj;aj=l;/printf(%dn,ai);void main() printf(一下是各个排序算法的代号:n);printf(一,冒泡排序n);printf(二,快速排序n);printf(三,选择排序n);int figure;/*统计时间所用的标记*/printf(请输入figure:);scanf(%d,&figure);time_t start=clock();/定义程序开始时间变量time_t finish=clock();/定义程序结束时间变量double duration;printf(*n);printf(n);printf(n);printf(n);printf(*n);switch(figure)case 1:start=clock();BubbleSort();/调用冒泡排序finish=clock();break;case 2:start=clock(); QuickSort();/调用快速排序finish=clock();break;case 3:start=clock