《算法设计第二章排序算法》由会员分享，可在线阅读，更多相关《算法设计第二章排序算法（21页珍藏版）》请在金锄头文库上搜索。
1、实验报告实验目的：理解递归算法的基本思想和递归程序的执行过程，并熟悉编写递归算法。掌握递归算法的思想，对给定的问题能设计出分治算法予以解决。实验内容：编程实现讲过的例题：二分搜索、合并排序、快速排序。实验过程：1.二分搜索：1.1问题描述 在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查找元素x和线性表L，输出x在L中的位置或者x不在L中的信息。1.2算法分析(1)首先将链表中第一个元素给参数low，最后一个元素给参量high；(2)在lowhigh的条件下：取d=(low+high)/2;若所查找元素第d个元素：则将d+1赋值给参量high;继续在low与hig
2、h的范围内查找；找到则输出。(3)当不满足 lowhigh的条件时：输出没有查找到此元素。 1.3程序框图假定要搜索x=9：145789101215222327323514578910 8910 2. 合并排序2.1问题描述 假定有一个数组A1mp.q.r是它的三个索引，并且有1=p=qr=m,两个子数组Apq Aq+1r各自按升序排列。我们要重新安排A中的元素的位置，使得子数组Apr也按升序排列。 2.2算法思想.使用两个指针s.t.初始化时各自指向Ap Ap+1，再用一个空数组Bpr作暂存器。 .每一次比较元素As.At,将小的元素添加到辅助数组Bpr中，如果相同就把As添加进去。同时更新
3、指针，若添加是As，则s+；若添加是At，则t+；.当条件s=q+1 or t=q+1时过程结束，在前一种情况下把数组Atr中剩余的元素添加到在B中. 在后一种情况下把数组Asq中剩余的元素添加到在B中.最后，把数组Bpq复制到Apr.2.3程序框图如图：给出有序数组两个：78910 78910101215101215 3. 快速排序3.1问题描述假定有一个数组A1m.其中的元素为无序排列；我们要重新安排A中的元素的位置，使得子数组Apr也按升序排列。 3.2算法思想(1)首先将链表中第一个元素给参数low，最后一个元素给参量high；(2)在lowhigh的条件下：将low与high之间的元
4、素以low元素为轴，比low小的元素交换到low以前；比low大的元素交换到low以后。此时得到一个以low为轴的划分，然后分别对low前和其后的数列再进行划分，直到数列成为单个元素，此时完成排序；(3)程序用递归实现。3.3程序框图57164832 i j51764832 i j51467832 i j51437862 i j51432867 i j21435867 i j4.程序源代码：（说明：我是将本试验的的三个小试验放在同一个函数中实现：首先从文件“data.txt”中读取无序数列存入动态数组中，然后进行快速排序，再读入数据进行合并排序，然后对此有序数列进行二分查找）#includes
5、tdio.h#includemath.h#includestdlib.hint *L,*C;int Num;int tag=0;void readindata()FILE *fpin;int a,i=0;if(fpin=fopen(data.txt,r)=NULL)printf(Can not open!); exit(0);while(!feof(fpin)fscanf(fpin,%d,&a);i+;Num=i;rewind(fpin);L=(int*)malloc(sizeof(int)*(Num+1);for(i=1;i=Num;i+)fscanf(fpin,%d,&a);*(L+i)=
6、a;int Partition(int low,int high)int key;*(L+0)=*(L+low);key=*(L+low);while(lowhigh)while(low=key) high-; *(L+low)=*(L+high); while(lowhigh&*(L+low)=key) low+; *(L+high)=*(L+low);*(L+low)=*(L+0);return low;void QSort(int low,int high)int point; if(lowhigh)point=Partition(low,high);QSort(low,point-1)
7、; QSort(point+1,high);void QuickSort()QSort(1,Num);void Merge(int i,int m,int n)int p;int k,t,j;t=i;C=(int*)malloc(sizeof(int)*(n-i+2); for(j=m+1,k=1;i=m&j=n;k+)if(*(L+i)=(*(L+j) *(C+k)=*(L+(i+);else *(C+k)=*(L+(j+);while(i=m) *(C+(k+)=*(L+(i+);while(j=n) *(C+(k+)=*(L+(j+);for(p=t,k=1;p=high) printf
8、(Cant find the number!n);elsed=(low+high)/2; midkey=*(L+d); if(x=midkey)printf(find the number,its the %dth one,d);tag=1; else if(xmidkey)Bsearch(x,low,d); else Bsearch(x,d,high);void search()int x;char c;while(1)printf(Input the number for searching:); scanf(%d,&x);Bsearch(x,1,Num);if(tag=0) printf
9、(Cant find the number!n);printf(nGo on?(input:yorn); c=getchar();c=getchar();if(c=n|c=N) break;void readoutdata(int *L)int i;for(i=1;i=n)/递归结束条件putout();/全部搜索完，得到一组解，相应的结果else /不放入此物search(m+1); /搜索下一个am=1;/ 放入此物search(m+1); /，搜索下一个am=0;/恢复1.3程序框图 1.4程序源代码#includestdio.h#includemath.hint c,n,max;int w20;int v20;int a20=0;void readdata()int i;printf(输入背包的容量：);scanf(%d,&c);printf(物品的件数为：);scanf(%d,&n);for(i=0;in;i+) printf(输入第%d背包的重量和价值是：,i+1); scanf(%d%d,&wi,&vi);void checkmax()int i;int weight=0;int value=0;for(i=0;in;i+)if(a
