《实验1 分治算法》由会员分享,可在线阅读,更多相关《实验1 分治算法(8页珍藏版)》请在金锄头文库上搜索。
1、算法设计与分析实验报告实验1 分治算法姓名 学号 班级 实验日期 2015.1.13 实验地点 一、实验目的1、掌握分治算法的设计思想与分析方法;2、掌握归并排序、快速排序等高效排序算法。二、实验环境1、硬件环境CPU:酷睿i5内存:4GB硬盘:1TB2、软件环境操作系统:win10编程环境:Dev-C+编程语言:C语言三、实验内容1、编写程序,实现归并排序算法。(1)归并排序算法归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。(2
2、)归并排序算法分析时间复杂度:O(nlogn)空间复杂度O(nlogn)(3)编程要求l 待排序数组长度至少为16,数组中可以有相同元素;l 按递增排序。(4)程序代码(含注释)/归并排序算法实现 #include #include #define MAXE 50/线性表中最多元素个数typedef int KeyType;typedef char InfoType10;typedef struct /记录类型KeyType key; /关键字项 InfoType data; /其他数据项,类型为InfoType RecType;void Merge(RecType R,int low,int
3、 mid,int high) /将两个有序表Rlow.mid和Rmid+1.high归并为一个有序表Rlow.high中RecType *R1;int i=low,j=mid+1,k=0; /k是R1的下标,i、j分别为第1、2段的下标R1=(RecType *)malloc(high-low+1)*sizeof(RecType); /动态分配空间while (i=mid & j=high) /在第1段和第2段均未扫描完时循环if (Ri.key=Rj.key) /将第1段中的记录放入R1中R1k=Ri;i+;k+; else /将第2段中的记录放入R1中R1k=Rj;j+;k+; while
4、 (i=mid) /将第1段余下部分复制到R1 R1k=Ri;i+;k+; while (j=high) /将第2段余下部分复制到R1R1k=Rj;j+;k+; for (k=0,i=low;i=high;k+,i+) /将R1复制回R中 Ri=R1k; void MergePass(RecType R,int length,int n)/实现一趟归并int i;for (i=0;i+2*length-1n;i=i+2*length) /归并length长的两相邻子表Merge(R,i,i+length-1,i+2*length-1); if (i+length-1n) /余下两个子表,后者长
5、度小于lengthMerge(R,i,i+length-1,n-1); /归并这两个子表void MergeSort(RecType R,int n) /二路归并排序算法int length,k,i=1;/i用于累计归并的趟数for (length=1;lengthn;length=2*length)MergePass(R,length,n);printf( 第%d趟归并 ,i+);/输出每一趟的排序结果for (k=0;kn;k+)printf(%4d,Rk.key);printf(n);int main()int i,k,n;RecType RMAXE;printf(请输入元素个数n:n)
6、;scanf(%d,&n);printf(请输入%d个元素:n,n);for (i=0;in;i+)scanf(%d,&Ri.key);printf(n);MergeSort(R,n);/执行排序函数printf(归并排序结果:n);printf( );for (k=0;kn;k+)printf(%5d,Rk.key);printf(nn);return 0;(5)程序输出2、编写程序,实现快速排序算法。(1)快速排序算法基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递
7、归进行,以此达到整个数据变成有序序列。(2)快速排序算法分析时间复杂度:O(nlogn)空间复杂度:O(nlogn)(3)编程要求l 待排序数组长度至少为16,数组中可以有相同元素;l 按递增排序。(4)程序代码(含注释)/快速排序算法实现 #include #define MAXE 50/线性表中最多元素个数typedef int KeyType;typedef char InfoType10;typedef struct /记录类型KeyType key; /关键字项 InfoType data; /其他数据项,类型为InfoType RecType;void QuickSort(RecT
8、ype R,int s,int t) /对Rs至Rt的元素进行快速排序int i=s,j=t,k;RecType temp;if (si & Rj.keytemp.key) j-; /从右向左扫描,找第1个关键字小于temp.key的Rj if (ij) /表示找到这样的Rj,Ri、Rj交换Ri=Rj;i+; while (ij & Ri.keytemp.key) i+;/从左向右扫描,找第1个关键字大于temp.key的记录Ri if (ij) /表示找到这样的Ri,Ri、Rj交换Rj=Ri;j-; Ri=temp; QuickSort(R,s,i-1); /对左区间递归排序QuickSor
9、t(R,i+1,t); /对右区间递归排序int main()int i,k,n;RecType RMAXE;printf(请输入元素个数n:n);scanf(%d,&n);printf(请输入%d个元素:n,n);for (i=0;in;i+)scanf(%d,&Ri.key);printf(n);QuickSort(R,0,n-1);/执行排序函数printf(快速排序结果:n);printf( );for (k=0;kn;k+)printf(%5d,Rk.key);printf(nn);return 0;(5)程序输出四、实验总结(心得体会、需要注意的问题等)通过这次实验,我对归并排序和快速排序有了更深入的了解,比之前能更熟悉的使用这两种算法来编程。同时,通过这次实验,我还是发现了我很多的不足之处,有许多需要注意的地方:第一,平常的编程练习太少,导致编程时做不到胸有成竹,经常出现问题,调试时间比较长;第二,编程时输入代码太慢,导致时间不够用。以后我会慢慢的改掉这两个问题。