《算法设计与分析》实验二.doc

《算法设计与分析》实验二————————————————————————————————作者:————————————————————————————————日期: 学号1421050102《算法设计与分析》实验报告二学生姓名Cherish专业、班级地理指导教师唐国峰成绩计算机与信息工程学院软件工程系2017年3月28日实验二:分治策略运用练****一、实验目的本次实验是针对分治策略运用的算法设计及应用练****旨在加深学生对该部分知识点的理解,提高学生运用该部分知识解决问题的能力。二、;;,用统一的实验报告模板编写实验报告。:(1)电子版提交说明:a需要提交Winrar压缩包,文件名为“《算法设计与分析》实验二_学号_姓名”,如“《算法设计与分析》实验二_09290101_张三”。b压缩包内为一个“《算法设计与分析》实验二_学号_姓名”命名的顶层文件夹,其下为两个文件夹,一个文件夹命名为“源程序”,另一个文件夹命名为“实验报告电子版”。其下分别放置对应实验成果物。(2)打印版提交说明:a不可随意更改模板样式。b字体:中文为宋体,大小为10号字,英文为TimeNewRoman,大小为10号字。c行间距:单倍行距。(3)提交截止时间:2017年4月11日16:00。。要求分别运用合并排序和快速排序完成该题目要求。。(要求N可由用户输入)四、实验过程题目一:对用户输入的杂乱无序的数字序列按照由小到大的顺序排序:快速排序题目分析快速排序是冒泡排序的改进,以一组杂乱无序的数字最左边为枢轴记录的关键字,最右侧指针若比关键字大,则右侧指针左移,若出现比它小的交换两指针指向数的排序完成。算法实现#include<>#include<>voidquickSort(inta[],intl,intr){inti,j,t;i=l;j=r;t=a[l];//枢轴元素t为数组最左侧的元素if(l>r)return;while(i!=j)//i往右移动j往左移动当指向同一位置时扫描完成{while(a[j]>=t&&j>i)j--;//如果右侧指针元素比轴测元素大,指针元素左移if(j>i)//确保i在j左边a[i++]=a[j];//当右侧指针元素比轴测元素小时,交换两指针指向数的位置while(a[i]<=t&&j>i)i++;//如果左侧指针元素比轴测元素小,指针元素右移if(j>i)//确保i在j左边a[j--]=a[i];//当左侧指针元素比轴测元素大时,交换两指针指向数的位置}a[i]=t;quickSort(a,l,i-1);//对左边进行排序quickSort(a,i+1,r);//对右边进行排序}voidmain(){inti,n,f[100]; printf("请输入要比较数字的个数:\n"); scanf_s("%d",&n);for(i=0;i<n;i++){ printf("请输入第%d个数字:\n",i+1); scanf_s("%d",&f[i]);}quickSort(f,0,n-1); printf("快速排序的结果是:\n");for(i=0;i<n;i++)printf("%d",f[i]); printf("\n"); system("pause"); getchar();}运行结果经验归纳结合以前学的数据结构及应用算法,较容易理解。题目二:对用户输入的杂乱无序的数字序列按照由小到大的顺序排序:合并排序题目分析合并排序的基本思想是:将待排序的元素分成大小大相同的两个子集合,分别对两个子集合进行排序,最终将排序好的子集合合并成所要求的拍好序的集合。算法构造核心代码来自书上:MergePass(Typex[],Typey[],ints,intn)//合并大小为s的相邻序列子数组Merge(Typec[],Typed[],intl,intm,intr)//合并c[l,m]和x[m+1,r]到y[l,r]算法实现#include<>#include<>template<classType>voidMergeSort(Typea[],intn){Type*b=newType[n]; ints=1; while(s<n) { MergePass(a,b,s,n);//将a中的元素合并到数组b s+=s; MergePass(b,a,s,n);//将b中的元素合并到数组a s+=s; }}template<classType>voidMerge(Typec[],Typed[],