算法分析——实验一.doc

算法分析实验报告实验一 分治策略排序实验目的1）以排序问题为例，掌握分治法的基本设计策略；2）熟练掌握合并排序算法的实现；3）熟练掌握快速排序算法的实现；4) 理解常见的算法经验分析方法。实验环境计算机、C语言程序设计环境、VC+6.0实验步骤算法的基本描述：1、 合并排序的基本思想描述：首先将序列分为两部分，分到每组只有两个元素，然后对每一部分进行循环递归地合并排序，然后逐个将结果进行合并。2、 快速排序的基本思想描述：将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，最后达到排序效果。要求：编写一个函数data-generate，生成2000个在区间1,10000上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为本算法实验的输入数据。程序流程图：合并排序原理图快速排序流程图1.生成2000个随机整数的程序：#include#include#includeint main()FILE *fpt;fpt = fopen(D:/data.txt,w);srand(time(0);for(int i=0;i2000;i+)fprintf(fpt,%3dt,rand()%10000+1);return 0;fclose(fpt);并生成data.txt文件。2.读取data.txt文件，并排序。实现合并排序算法输入：待排数据文件data.txt；输出：有序数据文件resultsMS.txt合并排序算法：#include #include #include void mergesort(int a,int n); void merge(int a,int b,int i,int c,int j); int main() int a2000; int i=0,j; FILE *fpt; fpt=fopen(D:data.txt,r);if(fpt=fopen(D:data.txt,r)=NULL)printf(n error!);exit(0);while (fscanf(fpt,%d,&ai)!=EOF)i+; mergesort(a,2000); fpt = fopen(D:/resultMS.txt,w); srand(time(0); for(j=0;j2000;j+) printf(%d ,aj); fprintf(fpt,%3dt,aj); fclose(fpt); return 0; void mergesort(int a,int n) if(n=1) return; int i,j; int *b; int *c; b=(int *)malloc(sizeof(int)*(n/2); c=(int *)malloc(sizeof(int)*(n-n/2); for(i=0;in/2;i+) bi=ai; for(j=0;jn-n/2;j+) cj=aj+n/2; mergesort(b,(n/2); mergesort(c,(n-n/2); merge(a,b,(n/2),c,(n-n/2); void merge(int a,int b,int x,int c,int y) int i=0; int j=0; int k=0; while(ix)&(jy) if(bi=cj) ak=bi; i+; else ak=cj; j+; k+; int l; if(i=x) for(l=j;ly;l+) ak=cl; k+; else for(l=i;lx;l+) ak=bl; k+; 运行结果为：并且在D盘内生成resultMS.txt文件。resultMS.txt内的数即为随机生成的数的排序。3.实现QuickSort 算法。输入：待排数据文件data.txt；输出：有序数据文件resultsQS.txt程序：#include #include #include int partions(int l,int low,int high)int prvotkey=llow;l0=llow;while (lowhigh) while (low=prvotkey) -high; llow=lhigh; while (lowhigh&llow=prvotkey) +low; lhigh=llow;llow=l0;return low;void qsort(int l,int low,int high)int prvotloc;if(lowhigh) prvotloc=partions(l,low,high); /第排序结作枢轴 qsort(l,low,prvotloc-1); /递归调用排序 由low prvotloc-1 qsort(l,prvotloc+1,high); /递归调用排序 由 prvotloc+1 highvoid quicksort(int l,int n)qsort(l,1,n); /第作枢轴 第排第nvoid main()int a2000;int i=0;FILE *fpt; fpt=fopen(D:data.txt,r);if(fpt=fopen(D:data.txt,r)=NULL)printf(n error);exit(0);while (fscanf(fpt,%d,&ai)!=EOF)i+;quicksort(a,2000);fpt=fopen(D:resultsQS.txt,w);srand(time(0);for(int j=1;j2000;j+)printf(%3dt,aj);fprintf(fpt,%3dt,aj);fclose(fpt);运行的结果：生成resultsQS文件程序运行的时间：TimeMS的运行时间为0.0000msTimeQS的运行时间为：产生的原因：可能是计算机运行速度太快，两者运行时间没有太大的差距，所以程序运行的时间约为0.实验分析：从理论上看，快速排序最好情形的时间复杂度为O(NlogN)，最坏的情形为O(N*N)，平均时间复杂度O(NlogN)。归并排序最好情形的时间复杂度为O(NlogN)，最坏的情形为O(NlogN)，平均时间复杂度O(NlogN)。因此，可以看出,快速排序算法较之合并排序而言更有优势,尽管保持在