《实验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）程序输出四、实验总结（心得体会、需要注意的问题等）通过这次实验，我对归并排序和快速排序有了更深入的了解，比之前能更熟悉的使用这两种算法来编程。同时，通过这次实验，我还是发现了我很多的不足之处，有许多需要注意的地方：第一，平常的编程练习太少，导致编程时做不到胸有成竹，经常出现问题，调试时间比较长；第二，编程时输入代码太慢，导致时间不够用。以后我会慢慢的改掉这两个问题。
