實驗1 分治算法

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

2、2）歸并排序算法分析時間復(fù)雜度：O(nlogn)空間復(fù)雜度O(nlogn)（3）編程要求l 待排序數(shù)組長度至少為16，數(shù)組中可以有相同元素；l 按遞增排序。（4）程序代碼（含注釋）/歸并排序算法實現(xiàn) #include <stdio.h>#include <malloc.h>#define MAXE 50/線性表中最多元素個數(shù)typedef int KeyType;typedef char InfoType10;typedef struct /記錄類型KeyType key; /關(guān)鍵字項 InfoType data; /其他數(shù)據(jù)項,類型為InfoType RecType;

3、void Merge(RecType R,int low,int 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); /動態(tài)分配空間while (i<=mid && j<=high) /在第1段和第2段均未掃描完時循環(huán)if (Ri.key<=Rj.key) /將第1段中的記錄放入R1

4、中R1k=Ri;i+;k+; else /將第2段中的記錄放入R1中R1k=Rj;j+;k+; while (i<=mid) /將第1段余下部分復(fù)制到R1 R1k=Ri;i+;k+; while (j<=high) /將第2段余下部分復(fù)制到R1R1k=Rj;j+;k+; for (k=0,i=low;i<=high;k+,i+) /將R1復(fù)制回R中 Ri=R1k; void MergePass(RecType R,int length,int n)/實現(xiàn)一趟歸并int i;for (i=0;i+2*length-1<n;i=i+2*length) /歸并length長的

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

6、0;k<n;k+)printf("%4d",Rk.key);printf("n");int main()int i,k,n;RecType RMAXE;printf("請輸入元素個數(shù)n：n");scanf("%d",&n);printf("請輸入%d個元素：n",n);for (i=0;i<n;i+)scanf("%d",&Ri.key);printf("n");MergeSort(R,n);/執(zhí)行排序函數(shù)printf(&quo

7、t;歸并排序結(jié)果：n");printf(" ");for (k=0;k<n;k+)printf("%5d",Rk.key);printf("nn");return 0;（5）程序輸出2、編寫程序，實現(xiàn)快速排序算法。（1）快速排序算法基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。（2）快速排序算法分析時間復(fù)雜度：O(nlogn)空間復(fù)雜度：O(nlogn)（

8、3）編程要求l 待排序數(shù)組長度至少為16，數(shù)組中可以有相同元素；l 按遞增排序。（4）程序代碼（含注釋）/快速排序算法實現(xiàn) #include <stdio.h>#define MAXE 50/線性表中最多元素個數(shù)typedef int KeyType;typedef char InfoType10;typedef struct /記錄類型KeyType key; /關(guān)鍵字項 InfoType data; /其他數(shù)據(jù)項,類型為InfoType RecType;void QuickSort(RecType R,int s,int t) /對Rs至Rt的元素進行快速排序int i=s,j

9、=t,k;RecType temp;if (s<t) /區(qū)間內(nèi)至少存在一個元素的情況temp=Rs; /用區(qū)間的第1個記錄作為基準 while (i!=j) /從區(qū)間兩端交替向中間掃描,直至i=j為止while (j>i && Rj.key>temp.key) j-; /從右向左掃描,找第1個關(guān)鍵字小于temp.key的Rj if (i<j) /表示找到這樣的Rj,Ri、Rj交換Ri=Rj;i+; while (i<j && Ri.key<temp.key) i+;/從左向右掃描,找第1個關(guān)鍵字大于temp.key的記錄Ri

10、if (i<j) /表示找到這樣的Ri,Ri、Rj交換Rj=Ri;j-; Ri=temp; QuickSort(R,s,i-1); /對左區(qū)間遞歸排序QuickSort(R,i+1,t); /對右區(qū)間遞歸排序int main()int i,k,n;RecType RMAXE;printf("請輸入元素個數(shù)n：n");scanf("%d",&n);printf("請輸入%d個元素：n",n);for (i=0;i<n;i+)scanf("%d",&Ri.key);printf("n");QuickSort(R,0,n-1);/執(zhí)行排序函數(shù)printf("快速排序結(jié)果：n");printf(" ");for (k=0;k<n;k+)printf("%5d",Rk.key);printf("nn");return 0;（5）程序輸出四、實驗總結(jié)（心得體會、需要