算法导论实验报告.docVIP

实验一 快速排序 1.1 问题描述 实现对数组的普通快速排序与随机快速排序。 1.2 实验要求 （1）实现上述两个算法 （2）统计算法的运行时间 （3）分析性能差异，作出总结 1.3 编程环境及语言 编程环境：Linux 编程语言：C 1.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..high]进行排序。 c.合并： 快速排序经过一趟划分操作将数组分解成两个子数组，且位于底部区域的元素均不大于主元，位于顶部区域的元素均不小于主元，所以，一旦两个子数组已经完成分别排序，整个数组自然成为有序序列。 2）快速排序算法: QuickSort(a，low，high) 1 if low high 2 then Partition(a，low，high) 3 QuickSort(a，low，q) 4 QuickSort(A，q+1，high) 1.4.2 随机快速排序算法 在快速排序算法的每一步中，当数组还没有被划分时，可将元素a[p]与a[p..r]中随机选出的一个元素交换后再执PARTITION。 1.4.3 随机数生成方法 头文件：#include time.h srand（（int）time（NULL））；设定随机数种子rand()% N；产生0-N的随机数。 1.4.4 函数运行时间统计方法 gettimeofday( )函数 头文件：#include sys/time.h 函数定义：int gettimeofday(struct timeval *tv， structtimezone *tz); 功能描述：gettimeofday( )把目前的时间信息存入tv指向的结构体，当地时区信息则放到tz指向的结构体。 int gettimeofday(struct timeval *tv， struct timezone *tz); 其中timeval结构定义如下： struct timeval{ time_t tv_sec; /* seconds */ suseconds_t tv_usec; /* microseconds */ }; 获取当前时刻，可以精确到微妙级别。 具体该函数在本程序中的应用程序段如下所示： gettimeofday(start， NULL); QuickSort(a， 0， N-1); gettimeofday(end， NULL); interval = 1000000 * (end.tv_sec - start.tv_sec) + (end.tv_usec - start.tv_usec); printf(QuickSort interval = %f， interval/1000.0); printf(\n); 1.5实验结果 图1 快速排序算法部分运行结果截图 表1 快速排序算法运行时间统计表（单位：ms） QuickSort 54.462000 54.723000 58.892000 56.450000 55.536000 QuickSort_Random 57.579000 58.233000 57.606000 54.263000 53.250000 △ -3.117000 -3.510000 1.286000 2.187000 2.286000 QuickSort 50.119000 78.724000 53.906000 59.300000 59.701000 QuickSort_Random 55.248000 56.589000 53.940000 58.922000 47.846000 △ -5.129000 22.135000 -0.034000 0.378000 11.855000 1.6结果分析 1）实验数据分析 本实验这设置的随机数组长度为100000，分别统计了10次普通快速排序和随机快速排序的运行时间，如图1所示，其中△值等于QuickSort的运行时间与QuickSort_Random运行时间的差。 不难看出，当△值为正时，QuickSort的运行时间大于QuickSort_Random运行时间，反之，QuickSort_Random运行时间较大。因为本实验中的快排对象是随机地一组数据，所以△值有正有