各种排序算法的性能测试.doc

..... word格式.整理版 组的编号：28 作者姓名 ： xxx 组的编号：28 作者姓名 ： xxx xxx xxx 实验名称：各种排序算法的性能测试 算法设计与分析 完成日期：2013年9月1日星期日 目录 第一章：简介 1 第二章：算法规范 2 数据结构 2 伪代码 3 第三章：算法测试 4 随机数比较 4 最优表 5 最差表 5 第四章：分析讨论 6 算法分析 6 时间复杂度分析 6 附录 7 声明 7 word格式.整理版 ：简介 问题的描述： 排序的主要目的是为了进行快速查找。排序就是将一个记录的无序序列调整成为一个有序序列的过程。在对记录进行排序的时候，需要选定一个信息作为排序的依据。 在数据结构课程中，我们已经学过了几种内部排序算法，没有一种排序算法在任何情况下都是最好的解决方案，有些排序算法比较简单，但速度相对比较慢；有些排序算法速度比较快，但却很复杂。 利用随机函数产生N个随机整数（N=5000），利用冒泡排序，选择排序，快速排序（结果由小到大的排序）并统计每一种排序所消耗的时间。把排序花的时间排在表格里面。 第二章:算法规范 数据结构： 在所有的三个排序策略中，我们用了数组，函数作为主要的数据结构。 因为我们只是测试了不同排序所需要的时间，没涉及其他复杂的操作，所以在这个项目中用了静态实现数组就可以。 伪代码如下所示 冒泡排序： int i,j,l,a[N]; 循环i从0到N-1 产生随机数到a[i]； 输出随机数组（无序）； 循环i：0到N-1 3.1．循环j：0到N-1； 3.2．if a[i]a[i+1];a[i]-a[i+1]; 3.3．输出有序随机数组； 选择排序： 1.int i,j,l,a[N]，k; 2.循环i从0到N-1 2.1产生随机数到a[i]； 2.2输出随机数组（无序）； 3循环i：0到N-1 3.1．循环j：i+1到N-1； 3.2．if a[i]a[i+1];a[i]-a[j]; 3.3．输出有序随机数组； 快速排序： int i,t,l,a[N]，mid,data[N],start,end; 2.循环i从0到N 2.1产生随机数到a[i]； 2.2输出随机数组（无序）； 3. while startend 3.1． While startend 和 data[end]=mid 3.2 while startend 和 data[end]mid 3.3．输出有序随机数组； 第三章：测试结果 一：随机数比较 表一： *随机数 冒泡 快速 选择 100 0.000000 0.000000 0.001000 1000 0.007000 0.000000 0.013000 2000 0.027000 0.001000 0.034000 4000 0.072000 0.000000 0.087000 10000 0.346000 0.000000 0.376000 20000 1.400000 0.000000 1.592000 40000 5.886000 0.001000 6.305000 注:该数据时间为注释数据的输出语句，运行程序所得的时间（s） 图一： 二：最优表 表二： 最优（升序） 冒泡 快速 选择 100 0.000000 0.000000 0.001000 1000 0.002000 0.001000 0.004000 2000 0.032000 0.000000 0.017000 4000 0.063000 0.000000 0.048000 10000 0.187000 0.000000 0.180000 20000 0.753000 0.001000 0.594000 40000 2.960000 0.000000 2.319000 注:该数据时间为注释数据的输出语句，运行程序所得的时间（s） 图二： 三：最差表 表三： 最差（逆序） 冒泡 快速 选择 100 0.000000 0.000000 0.001000 1000 0.007000 0.000000 0.008000 2000 0.014000 0.000000 0.027000 4000 0.062000 0.000000 0.089000 10000 0.270000 0.000000 0.252000 20