算法导论实验报告

实验一快速排序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.解决：2通过递归调用快速排序对子数组a[low..q]和a[q+1..high]进行排序。c.合并：快速排序经过一趟划分操作将数组分解成两个子数组，且位于底部区域的元素均不大于主元，位于顶部区域的元素均不小于主元，所以，一旦两个子数组已经完成分别排序，整个数组自然成为有序序列。2）快速排序算法:QuickSort(a，low，high)1iflowhigh2thenPartition(a，low，high)3QuickSort(a，low，q)4QuickSort(A，q+1，high)1.4.2随机快速排序算法在快速排序算法的每一步中，当数组还没有被划分时，可将元素a[p]与a[p..r]中随机选出的一个元素交换后再执PARTITION。1.4.3随机数生成方法头文件：#includetime.hsrand（（int）time（NULL））；设定随机数种子rand()%N；产生0-N的随机数。1.4.4函数运行时间统计方法gettimeofday()函数头文件：#includesys/time.h函数定义：intgettimeofday(structtimeval*tv，structtimezone*tz);功能描述：gettimeofday()把目前的时间信息存入tv指向的结构体，当地时区信息则放到tz指向的结构体。3intgettimeofday(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=1000000*(end.tv_sec-start.tv_sec)+(end.tv_usec-start.tv_usec);printf(QuickSortinterval=%f，interval/1000.0);printf(\n);1.5实验结果4图1快速排序算法部分运行结果截图表1快速排序算法运行时间统计表（单位：ms）QuickSort54.46200054.72300058.89200056.45000055.536000QuickSort_Random57.57900058.23300057.60600054.26300053.250000△-3.117000-3.5100001.2860002.1870002.286000QuickSort50.11900078.72400053.90600059.30000059.701000QuickSort_Random55.24800056.58900053.94000058.92200047.846000△-5.12900022.135000-0.0340000.37800011.8550001.6结果分析1）实验数据分析本实验这设置的随机数组长度为100000，分别统计了10次普通快速排序和随机快速排序的运行时间，如图1所示，其中△值等于QuickSort的运行时间与QuickSort_Random运行时间的差。不难看出，当△值为正时，QuickSort的运行时间大于QuickSort_Random运行时间，反之，QuickSort_Random运行时间较大。因为本实验中的快排对象是随机地一组数据，所以△值有正有负是正常的，当快排数据的量越多时，总体上QuickSort的平均运行时间大于QuickSort_Random运行时间。2）快速排序算法复杂度分析最坏情况划分：T(n)=T(n-1)+Θ(n)=Θ(n2)最佳情况划分：T(n)=2T(n/2)+Θ(n)=Θ(nlgn)随机快速排序在普通开速排序的基础上对主元进行随机选择，减小了排序算法趋于最坏情况的可能性，从某种程度上是对普通快速排序算法的改进。51.7实验总结通过本次实验，我对快速排序算法的原理和具体实现有了更深入的认识。此外，本次试验是我进一步熟悉了Linux环境下的编程方法，熟练掌握了VIM编辑指令，随机数生成方法，函数运行时间统计方法，程序的编译过程，Makefile文件的编写等知识点。为了养成良好的编程习惯和编码风格，我特地在网上下载并参考了华为的《C语言编程规范》，总之，虽然这次试验花费时间相当长，但是真的收获颇多，如有不尽完善之处还请老师指点，谢谢。1.8源代码1.8.1快排源代码/*********************************************************Corpyrigt@USTC_SSE.2013-2014.Allrightsreserved.Filename:QuickSort.cAuthor:YuJianID:SG13225026Version:1.0Date:2014/6/21Description:Thisprogramincludestwokindsofalgorithms，commonquicksortandrandomquicksortHistory:*********************************************************/#includestdio.h#includestdlib.h#includetime.h#includesys/time.h#defineN100000#defineMAX100000/**Function:swaptwodatas*Input:&ptr[i]，&ptr[low]*Output:NULL6*Return:NULL*/voidswap(int*ptr1，int*ptr2){inttemp;temp=*ptr1;*ptr1=*ptr2;*ptr2=temp;}/**Function:partitionanarrayintotwopartsbykeyvalue*eachvalueoftheleftsideisgreaterthankeyvalue*eachvalueoftherightsideisoppsite*Input:ptr，low，high*Output:NULL*Return:theposition(i)ofkeyvalueafteronetimepartition*/intPartition(int*ptr，intlow，inthigh){intkeyvalue;inti，j;i=low;j=high;keyvalue=ptr[i];while(i!=j){while(ij&&ptr[j]keyvalue)j--;if(ij){ptr[i]=ptr[j];i++;}while(ij&&ptr[i]keyvalue)i++;if(ij){ptr[j]=ptr[i];j--;}}ptr[i]=keyvalue;7returni;}/**Function:commonQuickSortalgorithm*ineachpartition，thelowdataisusedaskeyvalue*Input:array(a)，low，high*Output:NULL*Return:NULL*/voidQuickSort(int*ptr，intlow，inthigh){intpstn;if(lowhigh){pstn=Partition(ptr，low，high);QuickSort(ptr，low，pstn-1);QuickSort(ptr，pstn+1，high);}}/**Function:QuickSort_Randomalgorithm*ineachpartition，thekeyvalueisselectedfromarrayrandomly*Input:a，low，high*Output:NULL*Return:NULL*/voidQuickSort_Random(int*ptr，intlow，inthigh){inti;intpstn;if(lowhigh){i=low+rand()%(high-low+1);swap(&ptr[i]，&ptr[low]);QuickSort(ptr，low，high);pstn=Partition(ptr，low，high);QuickSort_Random(ptr，low，pstn-1);}8}/**Function:intmain()*Input:Thedatasofarrayaregeneratedbyfunctionrand()*theintervalofthealgorithms'runningtimeiscounted*byfunctionofgttimeofday()*Output:NULL*Return:0*/intmain(){inti;inta[MAX];intb[MAX];structtimevalstart，end;floatinterval;//setradomseedbasedthevalueoftime()srand((unsigned)time(NULL));for(i=0;iN;i++){a[i]=rand()%N;b[i]=a[i];}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(QuickSortinterval=%f，interval/1000.0);printf(\n);gettimeofday(&start，NULL);QuickSort_Random(b，0，N-1);gettimeofday(&end，NULL);9interval=1000000*(end.tv_sec-start.tv_sec)+(end.tv_usec-start.tv_usec);printf(QuickSort_Randominterval=%f，interval/1000.0);printf(\n);return0;}1.8.1快排Makefile#*********************************************************\#Corpyrigt@USTC_SSE.2013-2014.Allrightsreserved.#Filename:QuickSort.c#Author:YuJianID:SG13225026#Version:1.0Date:2014/6/21#Description:Thismakefileisusedtocompileandrunthequicksortalgorithm#History:#*********************************************************all:compileruncompile:QuickSort.cgcc-WallQuickSort.c-oQuickSortrun:Q