各种排序算法的性能测试

《各种排序算法的性能测试》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.....组的编号：28作者姓名：xxxxxxxxx实验名称：各种排序算法的性能测试算法设计与分析完成日期：2013年9月1日星期日word格式.整理版.....目录第一章：简介1第二章：算法规范2数据结构2伪代码3第三章：算法测试4随机数比较4最优表5最差表5第四章：分析讨论6算法分析6时间复杂度分析6附录7声明7word格式.整理版.....第一章：简介问题的描述：排序的主要目的是为了进行快速查找。排序就是将一个记录的无序序列调整成为一个有序序列的过程。在对记录进行排序的时候，需要选定一个信

2、息作为排序的依据。在数据结构课程中，我们已经学过了几种内部排序算法，没有一种排序算法在任何情况下都是最好的解决方案，有些排序算法比较简单，但速度相对比较慢；有些排序算法速度比较快，但却很复杂。利用随机函数产生N个随机整数（N=5000），利用冒泡排序，选择排序，快速排序（结果由小到大的排序）并统计每一种排序所消耗的时间。把排序花的时间排在表格里面。word格式.整理版.....第二章:算法规范数据结构：在所有的三个排序策略中，我们用了数组，函数作为主要的数据结构。因为我们只是测试了不同排序所需要

3、的时间，没涉及其他复杂的操作，所以在这个项目中用了静态实现数组就可以。伪代码如下所示冒泡排序：1.inti,j,l,a[N];2.循环i从0到N-12.1.产生随机数到a[i]；2.2.输出随机数组（无序）；3.循环i：0到N-13.1．循环j：0到N-1；3.2．ifa[i]>a[i+1];a[i]<->a[i+1];3.3．输出有序随机数组；选择排序：1.inti,j,l,a[N]，k;word格式.整理版.....2.循环i从0到N-12.1产生随机数到a[i]；2.2输出随机数组（无序）

4、；3循环i：0到N-13.1．循环j：i+1到N-1；3.2．ifa[i]>a[i+1];a[i]<->a[j];3.3．输出有序随机数组；快速排序：1.inti,t,l,a[N]，mid,data[N],start,end;2.循环i从0到N2.1产生随机数到a[i]；2.2输出随机数组（无序）；3.whilestart=mid3.2whilestart

5、整理版.....第三章：测试结果一：随机数比较表一：*随机数冒泡快速选择1000.0000000.0000000.00100010000.0070000.0000000.01300020000.0270000.0010000.03400040000.0720000.0000000.087000100000.3460000.0000000.376000200001.4000000.0000001.592000400005.8860000.0010006.305000注:该数据时间为注释数据的输出语

6、句，运行程序所得的时间（s）图一：二：最优表表二：最优（升序）冒泡快速选择1000.0000000.0000000.00100010000.0020000.0010000.00400020000.0320000.0000000.01700040000.0630000.0000000.048000word格式.整理版.....100000.1870000.0000000.180000200000.7530000.0010000.594000400002.9600000.0000002.319000

7、注:该数据时间为注释数据的输出语句，运行程序所得的时间（s）图二：三：最差表表三：最差（逆序）冒泡快速选择1000.0000000.0000000.00100010000.0070000.0000000.00800020000.0140000.0000000.02700040000.0620000.0000000.089000100000.2700000.0000000.252000200000.9690000.0000000.949000400003.8190000.0010003.75600

8、0注:该数据时间为注释数据的输出语句，运行程序所得的时间（s）图三:word格式.整理版.....第四章：分析和讨论（一）算法思想分析：1．冒泡排序：通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就象水底下的气泡一样逐渐向上冒。2．选择排序：假设待排序的列表的n个数据元素放在数组a中，第一次从n个数据元素中找出最小的元素与a[0]交换，第二次从剩下的n-1个元素中找出最小的