实验1分治算法

1、算法设计与分析实验报告实验1分治算法姓名学号班级实验日期2015、1、13实验地点、实验目得1、掌握分治算法得设计思想与分析方法;2、掌握归并排序、快速排序等高效排序算法。二、实验环境1、硬件环境C PU:酷睿i5内存:4 GB硬盘:1TB2、软件环境操作系统:win10编程环境：D ev-C+ +编程语言：C语言 三、实验内容1、编写程序，实现归并排序算法.(1 )归并排序算法归并排序就是建立在归并操作上得一种有效得排序算法，该算法就是采用分治法(Div id e and C o n quer )得一个非常典型得应用。将已有序得子序列合并, 得到完全有序得序列；即先使每个子序列有序，再使子序

2、列段间有序。(2)归并排序算法分析 时间复杂度:O(nl og n )空间复杂度O(nlogn)(3) 编程要求待排序数组长度至少为16,数组中可以有相同元素；按递增排序。4）程序代码 （含注释） / 归并排序算法实现 # inc 1 u d e # in elude #defi ne M A XE 50?/ /线性表中最多元素个数 ty pe d ef i n t K eyType；ty p ede f ch ar I n foTyp e10;t yp edef st r uct? / /记录类型K ey Typ e key; ?/ 关键字项In foTy ped ata；?/ /其她数据项

3、，类型为In f oTy pe Re cTy pe;void Merge ( Rec Type R , i nt low ,i nt mid,in t high) /将两个有序表 R 1 ow、mid与Rmid+1、hig h归并为一个有序表RIo w、high中 ?Re cT ype *R1 ;int i=low, j = mid + 1,k=0; / k就是R1得下标,i、j分别为第1、2段得下标?R1= (ReCType * )ma llo c (h ig h low+ 1 )* sizeof(ReCType);/动态分配空间/在第1段与第2段均未扫whil e (i = mi d &

4、j = high)描完时循环f (Ri、 key=R j、 ke y)?/将第1段中得记录放入R1中?R1k=Ri;?i+ ;k+;?else/将第 2 段中得记录放入R1中? R1k=R Cj ;?j+；k+；whilei=mid)?/将第 1段余下部分复制到 R1?R1C k=Ri；i+;k+;?while (j =high)/将第 2 段余下部分复制到 R1?R 1 C k =Rj;?j+;k+； ?for (k = 0 ,i= low；i =high;k+, i + +)/将 R1 复制回 R中Ri = R1 k;V o id M er geP ass( RecT ype R, i n

5、t 1e ng t h,i nt n )?/ 实现一趟归并? i nt i ；?fo r (i= 0；i +2*le n gth 1 n; i =i+2 * le ng th ) ?/ 归并 len g t h长得两相邻子表?M e r g e (R, i, i +length 1, i+2* 1 ength-1);/余下两个子表，?/ 归并这两个子表i f (i +len gth 1 n )后者长度小于l engt h ?Merg e(R, i,i1 en gth-1, n-1)； void M e r ge Sor t (R ec Typ e R: , i n t n) / 二路归并排序算

6、法?int length, k,i = 1 ;?/i用于累计归并得趟数f or (1 en g t h =1 ；1 engthn ;length=2 衣 length)MergeP a ss (R ,length, n);printf(”第趟归并,i+）;/ 输出每一趟得排序结?fo r (k = 0;kn; k+)?p r intf(” d, Rk、key);?printf (n);in t m a in()?int i，k,n;RecTy pe R MAXE;?pri n t f（请输入元素个数 n：n）;s canf (% d, & n);pr intf（请输入 d个元素：n”，n）;f

7、or (i= 0;i n;i+) ?sc anf (”d”，&R i、key);?p rin t f( n ” ； ?M e rgeSort ( R,n) ; /执行排序函数prin tf （归并排序结果：n）;”);printf(”for (k= 0;k竄归芹3&788901347143645&54789(簌趟归芽01336477B8947EgU564565第丄趟归彳0归并排序结果：133467Sg1126克47es7GSO0133467s3li3645476cS 7R寸2、编写程序,实现快速排序算法。(1)快速排序算法，其中一部分基本思想就是：通过一趟排序将要排序得数据分割成独立得两部分得

8、所有数据都比另外一部分得所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行 ，以此达到整个数据变成有序序(2)快速排序算法分析时间复杂度：0(niogn) 空间复杂度：0( nl o gn )(3)编程要求待排序数组长度至少为16，数组中可以有相同元素;按递增排序。(4) 程序代码(含注释)/ /快速排序算法实现# i nc 1 ude # de f in eMAXE 50?/ /线性表中最多元素个数typedef in tK ey Type；t ype d e fc ha rInfoType 1 0 ;typed ef st r uct/记录类型?KeyT

9、 ype ey ;/ /关键字项?QuickSo rt (R, i+ l,t) ;/对右区间递归排序 Re cType ;void QuickSort(ReCrype R , int s,1 nt t)/对R s至R t得元素进行快速排序int i = s,j= t ,k;?RecType t emp；?if （s 1&Rj、keyte m p、key)?/从右向左扫描，找第1个关键字小于tem p、key 得 R jif (ij)/表示找到这样得R j,R i、Rj 交换? ?Ri=Rj；?i+;?while (ivj & Ri、ke y t emp、key)i+; ?/从左向右扫描，找第1

10、个关键字大于t emp、ke y得记录 R1if (ij)?/表示找到这样得R 1 , Ri、R j交换? ?Rj= R i；?j-;?Ri=t emp；?Qu ic kSor t(R,s, i 1); /对左区间递归排序? in t main()?i n t i, k ,n;R ecType R MAXE;?prin t f（请输入元素个数n:n ”）;s canf ( % d”，&n );?prin tf (请输入 d 个元素:、n, n );f o r (i =0;ivn； i+)sea nf( ” 4&Ri、key);?pr in tf (” n” );Qui C kS ort (R, 0,n 1) ;/?执行排序函数pri n tf （快速排序结果：n”）；)；?pr i nt f (”for (k= 0; kke y);prin tf ( nn )；re tu r n 0;（5）程序输出23IS 请输人1亍元素；1 27 9S 3 4 7 G 9 1G 23 1035 14 30快退排序结果:234567791014 IS四、实验总结（心得体会、需要注意得问题等 ）