1、算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)1分治算法學(xué)號(hào)班級(jí)實(shí)驗(yàn)日期實(shí)驗(yàn)地點(diǎn)一、實(shí)驗(yàn)?zāi)康?、掌握分治算法的設(shè)計(jì)思想與分析方法；2、掌握歸并排序、快速排序等高效排序算法。二、實(shí)驗(yàn)環(huán)境1、硬件環(huán)境CPU酷睿i5存：4GB硬盤：仃B2、軟件環(huán)境操作系統(tǒng)：win10編程環(huán)境：Dev-C+編程語(yǔ)言：C語(yǔ)言三、實(shí)驗(yàn)容1、編寫程序，實(shí)現(xiàn)歸并排序算法(1)歸并排序算法歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法(Divide and Conque)的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完 全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。(2歸并排序算法分析時(shí)間復(fù)雜度：O(nlogn)空

2、間復(fù)雜度O(nlogn)(3) 編程要求待排序數(shù)組長(zhǎng)度至少為16,數(shù)組中可以有相同元素; 按遞增排序。(4) 程序代碼(含注釋)/歸并排序算法實(shí)現(xiàn)#i nclude <stdio.h>#i nclude <malloc.h>#defi ne MAXE 50/線性表中最多元素個(gè)數(shù)typedef int KeyType;/記錄類型typedef char In foType10;typedef structInfoType data; / 其他數(shù)據(jù)項(xiàng) ,類型為 InfoType RecType;void Merge(RecType R,int low,int mid,int

3、 high)/將兩個(gè)有序表 Rlow.mid和Rmid+1.high歸并為一個(gè)有序表 Rlow.high中 RecType *R1;int i=low,j=mid+1,k=0; k是R1的下標(biāo),i、j分別為第1、2段的下標(biāo)R1=(RecType *)malloc(high-low+1)*sizeof(RecType); /動(dòng)態(tài)分配空間while (i<=mid && j<=high)/在第 1 段和第 2 段均未掃描完時(shí)循環(huán)if (Ri.key<=Rj.key)/將第 1 段中的記錄放入 R1 中R1k=Ri;i+;k+;else/將第2段中的記錄放入R1中R

4、1k=Rj;j+;k+;while (i<=mid)/將第 1 段余下部分復(fù)制到 R1R1k=Ri;i+;k+;while (j<=high) / 將第 2 段余下部分復(fù)制到 R1R1k=Rj;j+;k+;for (k=0,i=low;iv=high;k+,i+)/將 R1 復(fù)制回 R 中Ri=R1k;void MergePass(RecType R,int length,int n) /實(shí)現(xiàn)一趟歸并int i;for (i=0;i+2*length-1<n;i=i+2*length) / 歸并 length 長(zhǎng)的兩相鄰子表Merge(R,i,i+length-1,i+2*l

5、ength-1);if (i+length-1<n)/ 余下兩個(gè)子 表, 后者長(zhǎng)度小于/歸并這兩個(gè)子表lengthMerge(R,i,i+length-1,n-1);void MergeSort(RecType R,int n) / 二路歸并排序算法int length,k,i=1; /i 用于累計(jì)歸并的趟數(shù) for (length=1;length<n;length=2*length)MergePass(R,length,n);printf(" 第%d趟歸并",i+);/輸出每一趟的排序結(jié)果for (k=0;k<n;k+)printf("%4d

6、",Rk.key);printf("n");int main()int i,k,n;RecType RMAXE;printf(" 請(qǐng)輸入元素個(gè)數(shù) n：n");scanf("%d",&n);printf("請(qǐng)輸入d個(gè)元素：n",n);for (i=0;i<n;i+)scanf("%d",&Ri.key);prin tf("n");MergeSort(R, n); / 執(zhí)行排序函數(shù) prin tf("歸并排序結(jié)果:n"); pr

7、intf("");for (k=0;k< n;k+)prin tf("%5d",Rk.key);prin tf("nn");return 0;(5) 程序輸出請(qǐng)輸人7E素個(gè)數(shù)口：16請(qǐng)輸人16個(gè)兀素；7S 6 a? 1 n 斗?498945 657S 99473G4514&578143645654747S91426914364S4TE5S 91436454747&9j7373U 7 a94891389012 S473 46344E肪砸7866 781 21 21 2 CUs eAd mi n istrat&

8、;r'.Desktc p'' 曰幷排序疋畑匚 X33ooMs第coTttt# 彳果 歸歸歸歸結(jié) 趟趙趟趟百 1 2 2 A2、編寫程序，實(shí)現(xiàn)快速排序算法（1）快速排序算法基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的 所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。（2）快速排序算法分析時(shí)間復(fù)雜度：O（nlogn）空間復(fù)雜度：O（nlogn）（3）編程要求待排序數(shù)組長(zhǎng)度至少為16,數(shù)組中可以有相同元素；按遞增排序。（4）程序代碼（含注釋）/快速排序算法實(shí)

9、現(xiàn)#i nclude <stdio.h>#defi ne MAXE 50/線性表中最多元素個(gè)數(shù)typedef int KeyType;/記錄類型typedef char In foType10;typedef structKeyType key;/ 關(guān)鍵字項(xiàng)InfoType data;/ 其他數(shù)據(jù)項(xiàng) ,類型為 InfoType RecType;void QuickSort(RecType R,int s,int t) /對(duì) Rs至 Rt的元素進(jìn)行快速排序int i=s,j=t,k;RecType temp;if (s<t)/區(qū)間至少存在一個(gè)元素的情況temp=Rs;/用區(qū)間的

10、第 1 個(gè)記錄作為基準(zhǔn)while (i!=j)/從區(qū)間兩端交替向中間掃描,直至i=j為止while (j>i && Rj.key>temp.key)j-;/ 從右向左掃描 ,找第 1 個(gè)關(guān)鍵字小于 temp.key的 Rjif (i<j)/表示找到這樣的Rj,Ri、Rj交換Ri=Rj;while (i<j && Ri.key<temp.key)i+;/ 從左向右掃描 ,找第 1 個(gè)關(guān)鍵字大于 temp.key的記錄 Riif (i<j)/表示找到這樣的Ri,Ri、Rj交換Rj=Ri;j-; Ri=temp;QuickSort(

11、R,s,i-1); /對(duì)左區(qū)間遞歸排序QuickSort(R,i+1,t); /對(duì)右區(qū)間遞歸排序int main()int i,k,n;RecType RMAXE;printf(" 請(qǐng)輸入元素個(gè)數(shù) n：n");scanf("%d",&n);printf("請(qǐng)輸入d個(gè)元素：n",n);for (i=0;i<n;i+)scanf("%d",&Ri.key);prin tf("n");QuickSort(R,0,n-1); / 執(zhí)行排序函數(shù) prin tf("快速排序結(jié)果:n");prin tf("");for (k=0;k< n;k+)prin tf("%5d",Rk.key);prin tf("nn");return 0;(5) 程序輸出四、實(shí)