算法导论实验报告.doc

《算法导论实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验一快速排序1.1问题描述实现对数组的普通快速排序与随机快速排序。1.2实验要求（1）实现上述两个算法（2）统计算法的运行时间（3）分析性能差异，作出总结1.3编程环境及语言编程环境：Linux编程语言：C1.4实验原理1.4.1普通排序算法1）解决排序问题的基本思路：使用分治法基本步骤：a.分解：数组a[low..high]被划分为两个非空子数组a[low..q]和a[q+1..high]，使得a[low..q]的每一个元素都小于等于a[q+1..high]的元素。b.解决：通过递归调用快速排序对子数组a[low..q]和a[q+1.

2、.high]进行排序。c.合并：快速排序经过一趟划分操作将数组分解成两个子数组，且位于底部区域的元素均不大于主元，位于顶部区域的元素均不小于主元，所以，一旦两个子数组已经完成分别排序，整个数组自然成为有序序列。2）快速排序算法:QuickSort(a，low，high)1iflow

3、一个元素交换后再执PARTITION。1.4.3随机数生成方法头文件：#includesrand（（int）time（NULL））；设定随机数种子rand()%N；产生0-N的随机数。1.4.4函数运行时间统计方法gettimeofday()函数头文件：#include函数定义：intgettimeofday(structtimeval*tv，structtimezone*tz);功能描述：gettimeofday()把目前的时间信息存入tv指向的结构体，当地时区信息则放到tz指向的结构体。intg

4、ettimeofday(structtimeval*tv，structtimezone*tz);其中timeval结构定义如下：structtimeval{time_ttv_sec;/*seconds*/suseconds_ttv_usec;/*microseconds*/};获取当前时刻，可以精确到微妙级别。具体该函数在本程序中的应用程序段如下所示：gettimeofday(&start，NULL);QuickSort(a，0，N-1);gettimeofday(&end，NULL);interval=*(end.tv_sec-star

5、t.tv_sec)+(end.tv_usec-start.tv_usec);printf("QuickSortinterval=%f"，interval/1000.0);printf("");1.5实验结果图1快速排序算法部分运行结果截图表1快速排序算法运行时间统计表（单位：ms）QuickSort54.54.58.56.55.QuickSort_Random57.58.57.54.53.△-3.-3.1.2.2.QuickSort50.78.53.59.59.QuickSort_Random55.56.53.58.47.△-5.22

6、.-0.0.11.1.6结果分析1）实验数据分析本实验这设置的随机数组长度为，分别统计了10次普通快速排序和随机快速排序的运行时间，如图1所示，其中△值等于QuickSort的运行时间与QuickSort_Random运行时间的差。不难看出，当△值为正时，QuickSort的运行时间大于QuickSort_Random运行时间，反之，QuickSort_Random运行时间较大。因为本实验中的快排对象是随机地一组数据，所以△值有正有负是正常的，当快排数据的量越多时，总体上QuickSort的平均运行时间大于QuickSort_Random

7、运行时间。2）快速排序算法复杂度分析最坏情况划分：T(n)=T(n-1)+Θ(n)=Θ(n2)最佳情况划分：T(n)=2T(n/2)+Θ(n)=Θ(nlgn)随机快速排序在普通开速排序的基础上对主元进行随机选择，减小了排序算法趋于最坏情况的可能性，从某种程度上是对普通快速排序算法的改进。1.7实验总结通过本次实验，我对快速排序算法的原理和具体实现有了更深入的认识。此外，本次试验是我进一步熟悉了Linux环境下的编程方法，熟练掌握了VIM编辑指令，随机数生成方法，函数运行时间统计方法，程序的编译过程，Makefile文件的编写等知识点。为了

8、养成良好的编程习惯和编码风格，我特地在网上下载并参考了华为的《C语言编程规范》，总之，虽然这次试验花费时间相当长，但是真的收获颇多，如有不尽完善之处还请老师指点，谢谢。1.8源代码1.8.1快