《各种排序算法的性能测试.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
