算法设计分析期末报告

《算法设计分析期末报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、实验目的(1)了解分治策略算法思想和贪心算法思想(2)详细掌握快速排序、归并排序算法以及最小生成树算法(3)了解其他分治问题典型算法二．实验内容：(1)编写一个简单的程序，实现归并排序。(2)编写一段程序，实现快速排序。(3)编写一段程序，实现最小生成树算法三．实验要求：（1）写出源程序，并编译运行（2）详细记录程序调试及运行结果第18页共14页第一章分治算法中的快速排序和归并排序分治算法概念：我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分

2、解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。归并排序：将待排序元素分成大小大致相同的两个集合，分别把对两个子集合进行排序，最终将排序号的子集合合并成为所要求的排好序的集合算法实现：#includeusingnamespacestd;voidmerge(intarray[],intp,intq,intr){inti,k;intbegin1,end1,begin

3、2,end2;int*temp=newint[r-p+1];//申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后、//的序列第18页共14页//设定两个指针，最初位置分别为两个已经排序序列的起止位置begin1=p;end1=q;begin2=q+1;end2=r;k=0;while((begin1<=end1)&&(begin2<=end2)){if(array[begin1]

4、2++;}k++;}//若第一个序列有剩余，拷贝出来粘到合并序列尾while(begin1<=end1)temp[k++]=array[begin1++];//若第二个序列有剩余，拷贝出来粘到合并序列尾while(begin2<=end2)temp[k++]=array[begin2++];for(i=0;i<(r-p+1);i++)//将排序好的序列拷贝回数组中array[p+i]=temp[i];第18页共14页delete[](temp);}voidmerge_sort(intdata[],intleft,intright){if(left

5、ight){intmid=(left+right)/2;merge_sort(data,left,mid);merge_sort(data,mid+1,right);merge(data,left,mid,right);}}intmain(){inta[8]={10,8,98,56,42,40,7,5};merge(a,0,3,7);merge_sort(a,0,7);cout<<"归并排序后的数组为："<

6、共14页2、快速排序快速排序：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。算法实验代码如下：#includeusingnamespacestd;voidquicksort(intnumber[],intleft,intright){inti,j,s;if(left

7、){while(number[++i]s);//向左找第一个小于轴的数第18页共14页if(i>=j)break;swap(number[i],number[j]);}quicksort(number,left,i-1);//对左边进行递归quicksort(number,j+1,right);//对右边进行递归}}intmain(){inta[8]={1,45,48,21,35,48,1421,98};quicksort(a,0,7);cout<<"经快速排序后的数组为："<

8、ndl;inti=0;for(i;i<8;i++){cout<