計(jì)算機(jī)算法設(shè)計(jì)和分析實(shí)驗(yàn)報(bào)告

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

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

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

4、每一趟歸并，其關(guān)鍵字比較次數(shù)不超過(guò)n, 元素移動(dòng)次數(shù)都是n,因此，歸并排序的時(shí)間復(fù)雜度為O(nlog2n)。空間復(fù)雜度用順序表實(shí)現(xiàn)歸并排序時(shí)，需要和待排序記錄個(gè)數(shù)相等的輔助存儲(chǔ)空間，所以空間復(fù) 雜度為0(n);五、實(shí)驗(yà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)生隨機(jī)數(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è)置隨機(jī)數(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 運(yùn)行了： (e - s) ms endl;clock_t start1 = 0, end1 = 0;start1 = clock();std:sort(&arrays0, & arraysArrayLe n);end1 = clock();cout std:sort 運(yùn)行了： (end1 - start1) ms endl; int flag = 1;while (flag != 0)coutvv輸入