計算機算法設(shè)計和分析實驗報告

1、華北電力大學實驗報告|實驗名稱算法設(shè)計實驗課程名稱算法設(shè)計與分析|專業(yè)班級：信安1301專業(yè)班級：信安1301學 號：指導教師：胡朝舉學生：成 績：實驗日期：2015年11月實驗一、歸并排序(實驗一、歸并排序(Merging Sort)分治策略一、實驗容歸并排序是一個非常優(yōu)秀的排序方法，也是典型的分治策略的典型應(yīng)用。實驗要求：編寫一個模板函數(shù)：template MergeSort(T *a, int n);以及相應(yīng)的一系列函數(shù)，采用分治策略，對任意具有：bool operator(c onst T& x,c onst T&y);比較運算符的類型進行排序。 與STL庫中的函數(shù)std:sort(.

2、)進行運行時間上的比較，給出比較結(jié)果，如：動態(tài)生成 100萬個隨機生成的附點數(shù)序列的排序列問題，給出所用的時間比較。歸并排序就是將兩個或兩個以上的有序表合并成一個有序表的過程。將兩個有序表合并成一個有序表的過程稱為2-路歸并。二、主要思想假設(shè)初始序列含有 n個記錄，則可看成 n個有序的子序列，每個字序列的長度為 1，然后兩兩歸并， 得到n/2個長度為2或1的有序子序列；再兩兩歸并， ，如此重復(fù)，直到一個長度為 n的有序序列 為止。例已知待排序記錄的關(guān)鍵字序列為49,38,65,97,76,13,27，給出2-路歸并排序法進行排序的過程初始關(guān)鍵字49 t138 |651 ,97 |176113|

3、27一趟片并之后3849|L,16597)113?6|2 I!7二越歸并之后卩84965L.97B27|狗三趟歸并之后1327384965761丁7|厶路歸并排序過程2-路歸并排序中的核心操作是，將待排序序列中前后相鄰的兩個有序序列歸并為一個有序序列。相鄰兩個有序子序列的歸并設(shè)兩個有序表存放在同一數(shù)組中相鄰的位置上：Rlow.mid禾口 Rmid+1.high，每次分被從兩個表中取出一個記錄進行關(guān)鍵字的比較，將較小者放入Tlow.high中，重復(fù)此過程，直至其中一個表為空，最后將另一非空表中余下的部分直接復(fù)制到T中。三、實驗結(jié)果四、算法分析時間復(fù)雜度當有n個記錄時，需進行l(wèi)og2n趟歸并排序，

4、每一趟歸并，其關(guān)鍵字比較次數(shù)不超過n, 元素移動次數(shù)都是n,因此，歸并排序的時間復(fù)雜度為O(nlog2n)?？臻g復(fù)雜度用順序表實現(xiàn)歸并排序時，需要和待排序記錄個數(shù)相等的輔助存儲空間，所以空間復(fù) 雜度為0(n);五、實驗代碼#in clude#i nclude#in clude#i nclude#i ncludeusing n amespace std;templatevclass Typevoid MergSort(Type a, int n)Type *b = new Type n;int s = 1;while (s void MergPass(Type x, Type y, int s,

5、 int n)int i = 0;while (i = n - 2 * s)Merg(x, y, i, i + s - 1, i + 2 * s - 1);i = i + 2 * s;if (i + s n)Merg(x, y, i, i + s - 1, n - 1);else/如果剩下的不夠i+s,則把剩下的放入y中for (i nt j = i; j void Merg(Type c, Type d, int l, i nt m, int r)int i = l, j = m + 1, k = l;while (i = m) & (j = r)if (ci m)for (int q =

6、j; q = r; q+)dk+ = cq;elsefor (int q = i; q = m; q+)dk+ = cq;float ran df(float base, float up)return (ran d() % (in t)(up - base) * RAND_MAX) / (float)RAND_MAX ; /產(chǎn)生隨機數(shù)void prin tArray(float *a,i nt N)for(i nt i=0;i=N;i+)coutaie ndl;void mai n()int ArrayLe n = 5;float *array = new floatArrayLe n;fl

7、oat *arrays = new floatArrayLe n;float mn, ene;printf(數(shù)組已建立：n);srand(unsigned)time(NULL); /設(shè)置隨機數(shù)的 seedfor (int i = 0; i fflag;switch (fflag)case 0:break;case 1:MergSort(array, ArrayLe n);prin tArray(array, ArrayLe n); break;prin tf(=n);prin tf(n);clock_t s = 0, e = 0;s = clock();MergSort(array, ArrayLe n);e = clock();cout MergSort 運行了： (e - s) ms endl;clock_t start1 = 0, end1 = 0;start1 = clock();std:sort(&arrays0, & arraysArrayLe n);end1 = clock();cout std:sort 運行了： (end1 - start1) ms endl; int flag = 1;while (flag != 0)coutvv輸入