《算法設計與分析》實驗二分治策略運用練習

學 號 算法設計與分析實驗報告二學生姓名專業(yè)、班級指導教師唐國峰成績電子與信息工程系2013 年 4 月 15 日實驗二：分治策略運用練習一、實驗目的本次實驗是針對分治策略運用的算法設計及應用練習，旨在加深學生對該部分知識點的理解，提高學生運用該部分知識解決問題的能力。二、實驗步驟與要求1實驗前復習課程所學知識以及閱讀和理解指定的課外閱讀材料；2學生獨自完成實驗指定內容；3實驗結束后，用統(tǒng)一的實驗報告模板編寫實驗報告。4提交說明： （1）電子版提交說明：a 需要提交Winrar壓縮包，文件名為“算法設計與分析實驗二_學號_姓名”，如“算法設計與分析實驗二_09290101_張三”。 b 壓縮包內為一個“算法設計與分析實驗二_學號_姓名”命名的頂層文件夾，其下為兩個文件夾，一個文件夾命名為“源程序”，另一個文件夾命名為“實驗報告電子版”。其下分別放置對應實驗成果物。 （2）打印版提交說明：a 不可隨意更改模板樣式。 b 字體：中文為宋體，大小為10號字，英文為Time New Roman，大小為10號字。 c 行間距：單倍行距。（3）提交截止時間：2012年4月29日16:00。三、 實驗項目1對用戶輸入的雜亂無序的數(shù)字序列按照由小到大的順序排序。要求分別運用合并排序和快速排序完成該題目要求。四、實驗過程（一） 題目一：對于用戶隨意輸入的7個無序數(shù)字，用合并排序的方法，按照從小到大的順序進行排序。1. 題目分析：將待排序元素分成大致相同的兩個子集合，分別對兩個子集合進行排序，最終將排好序的子集合合并成所要求的排好序的集合。2. 算法構造：調用三個函數(shù)來實現(xiàn)，MergePass用于合并排好序的相鄰數(shù)組段，具體的合并算法由Merge用來實現(xiàn)，MergeSort函數(shù)為合并算法，調用Merge、MergePass函數(shù)來實現(xiàn)數(shù)的合并排序3. 算法實現(xiàn)#include<stdio.h>template<class Type>void MergeSort(Type a,int n) Type*b=new Type; int s=1;while(s<n)MergePass(a,b,s,n);/將a中的元素合并到數(shù)組bs+=s;MergePass(b,a,s,n);/將b中的元素合并到數(shù)組as+=s;template<class Type>void Merge(Type c,Type d,int l,int m,int r) /合并cl,m和xm+1,r到y(tǒng)l,rint i=l,j=m+1,k=l;while(i<=m)&&(j<=r)if(ci<=cj)dk+=ci+;elsedk+=cj+;if(i>m)for(int q=j;q<=r;q+)dk+=cq;elsefor(int q=i;q<=m;q+)dk+=cq;template<class Type>void MergePass(Type x,Type y,int s,int n)/合并大小為s的相鄰序列子數(shù)組int i=0;while(i<=n-2*s) /合并大小為s的相鄰2字段數(shù)組Merge(x,y,i,i+s-1,i+2*s-1);/合并xi,i+s-1和xi+s,i+2*s-1到y(tǒng)i,i+2*s-1i=i+2*s;if(i+s<n)/處理剩下的元素少于2sMerge(x,y,i,i+s-1,n-1);elsefor(int j=i;j<=n-1;j+)yj=xj;void main() int a7,i;printf("請 輸 入 7 個 數(shù) 字:n");for( i=0;i<7;i+)scanf("%d",&ai); MergeSort(a,7);printf("最 終 排 序 結 果 為:n");for(int e=0;e<7;e+)printf("%dt",ae);printf("n");4. 運行結果5. 經驗歸納：我主要參考書上的程序來做的，我感覺主要是做好合并數(shù)組（二）題目二：對用戶輸入的無序的數(shù)字，按照快速排序方法，由小到大的順序排序。1. 題目分析：通過一趟掃描，就能確保某個數(shù)并以它為基準點的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理，它左右兩邊的數(shù)，直到基準點的左右只有一個元素為止2. 算法構造：定義軸測元素，然后從兩端各個和軸測元素比較后放在相應的位置，相比元素一樣，將軸測元素放到中間。對排好序的兩邊，重復上述操作。3. 算法實現(xiàn)#include<stdio.h>void quickSort(int a,int l,int r) int i,j,t; i=l; j=r; t=al; /軸測元素t為數(shù)組最左側的元素 if(l>r) return; while(i!=j) /掃描完，結束時語句 while(aj>=t && j>i) j-; /如果右側指針元素比軸測元素大，指針元素左移 if(j>i) ai+=aj; while(ai<=t && j>i) i+; /如果左側指針元素比軸測元素小，指針元素右移 if(j>i) aj-=ai; ai=t; quickSort(a,l,i-1); /對左邊進行排序 quickSort(a,i+1,r); /對右邊進行排序void main() int i,f7; printf("請 輸 入 7 個 無 序 的 數(shù) 字：n"); for(i = 0; i <7; i +) scanf("%d",&fi); quickSort(f,0,7);printf("快 速 排 序 后：n"); for(i=0;i<7;i+) printf("%d ",fi);printf("n");4. 運行結果5. 經驗歸納：主要找出軸測元素和兩端元素進行比較，依次進行這樣就行五、實驗總結 通過這次實驗我了解并理解了合并排序和快速排序，以前只是學習了快速排序的思想并沒有編程，合并的編程我參照課本上的程序，馬馬虎虎把它做下來了，快速排序我主要是查看了一些資料，來編寫的，這次實驗讓我在合并和快速排序上面的編程有了更加進一步的理解。