算法設(shè)計與分析報告報告材料部分算法偽代碼

1、實用標(biāo)準(zhǔn)文案第三章蠻力法1. 選擇排序SelectionSort(A0.n-1) for i=0 to n-2 domin=ifor j=i+1 to n-1 doif AjAminmin=jswap Ai and Amin2. 冒泡排序BubbleSort(A0.n-1)/ 輸入：數(shù)組 A ，數(shù)組中的元素屬于某偏序集/ 輸出：按升序排列的數(shù)組 Afor i=0 to n-2 dofor j=0 to n-2-i doif Aj+1Aj swap Aj and Aj+13. 改進的冒泡算法ALGORITHM BubbleSortImproved( A0,n 1 )/ 冒泡排序算法的改進/ 輸入

2、：數(shù)組 A ，數(shù)組中的元素屬于某偏序集/ 輸出：按升序排列的數(shù)組 Afor i 0 to n 2 doflag Truefor j 0 to n 2 i doif Aj+1 Ajswap(Aj, Aj+1)flag False/如果在某一輪的比較中沒有交換，則flag 為 True ，算法結(jié)束if flag = Truereturn精彩文檔實用標(biāo)準(zhǔn)文案4. 順序查找算法算法SwquentialSearch2(A0.n,k)/ 順序查找算法的實現(xiàn)，它用了查找鍵來作限位器/ 輸入：一個 n 個元素的數(shù)組 A 和一個查找鍵 K/ 輸出：第一個值等于 K 的元素的位置，如果找不到這樣的元素就返回-1A

3、n-ki-0while Ai!=K doi-i+1if in return iElse return -15. 蠻力字符串匹配算法BruteForceStringMatch(T0.n-1,P0.m-1)/ 該算法實現(xiàn)了蠻力字符串匹配/ 輸入：一個n 個字符的數(shù)組T0.n-1代表一段文本/一個 m 個字符的數(shù)組P0.m-1代表一個模式/ 輸出：如果查找成功的話，返回文本的第一個匹配字串中第一個字符的位置，/否則返回 -1For i-0 to n-m doj-0While jm and Pj=Ti+jdoj 1copy A0.n/2 -1 to B0.n/2-1copy An/2 .n-1 to

4、C0.n/2-1MergeSort( B )MergeSort( C )Merge( B,C,A )兩個數(shù)組合并的算法算法Merge(B0.p-1,C0.q-1,A0.p+q-1)/ 將兩個有序數(shù)組合并成一個有序的數(shù)組/ 輸入：兩個有序數(shù)組B0.p-1 和 C0.q-1/ 輸出： A0.p+q-1中已經(jīng)有序存放了B 和 C 中的元素i=0,j=0,k=0;while ip and jq doif Bi C jAk=Bi, i=i+1else精彩文檔實用標(biāo)準(zhǔn)文案Ak=Cj, j=j+1k=k+1if i=pcopy C j.q-1 to Ak.p+q-1elsecopy Bi.p-1 to A0

5、.p+q-1快速排序算法QuickSort(Al.r)/ 使用快速排序法對序列或者子序列排序/ 輸入：子序列 Al.r 或者序列本身 A0.n-1/ 輸出：非遞減序列 Aif l rs Partition( Al.r ) QuickSort( Al.s-1 )QuickSort( As+1.r )/s 是中軸元素 / 基準(zhǔn)點，是數(shù)組分區(qū)位置的標(biāo)志實現(xiàn)分區(qū)的算法算法Partition( Al.r )/ 輸入：子數(shù)組 Al.r/ 輸出：分裂點 / 基準(zhǔn)點 pivot 的位置p Ali l; j r+1repeatrepeati i + 1until Ai prepeatj j 1until Aj

6、pswap( Ai, Aj )until i jswap( Ai, Aj )swap( Al, Aj )return j精彩文檔實用標(biāo)準(zhǔn)文案折半查找BinarySearch( A0.n-1, k )/輸入：已排序大小為n 的序列 A ，待搜索對象k/輸出：如果搜索成功，則返回k 的位置，否則返回-1l=0,r=n-1;While lrmid=(l+r)/2if k = Amid return midelse if k temp doAj+1 Ajj j 1A j+1 temp精彩文檔實用標(biāo)準(zhǔn)文案深度優(yōu)先查找算法BFS（ G）/ 實現(xiàn)給定圖的深度優(yōu)先查找遍歷/ 輸入：圖 G=/ 輸出：圖G 的頂

7、點，按照被DFS 遍歷第一次訪問到的先后次序，用連續(xù)的整數(shù)標(biāo)記，將V 中的每個頂點標(biāo)記為0 ，表示還“未訪問”count =0/記錄這是第幾個訪問的節(jié)點mark each vertex with 0/標(biāo)記為unvisitedfor each vertex v V doif v is marked with 0dfs(v)dfs( v)/ 遞歸訪問所有和v 相連接的未訪問頂點，然后按照全局變量count的值/ 根據(jù)遇到它們的先后順序，給它們附上相應(yīng)的數(shù)字count = count + 1markv with countfor each vertexw adjacent tov doif w is

8、 marked with 0dfs( w )廣度優(yōu)先BFS(G)/ 實現(xiàn)給定圖的深度優(yōu)先查找遍歷/ 輸入：圖 G=/ 輸出：圖G 的頂點，按照被BFS 遍歷第一次訪問到的先后次序，用連續(xù)的整數(shù)標(biāo)記，將V 中的每個頂點標(biāo)記為0 ，表示還“未訪問”count =0mark each vertex with 0for each vertex v V dobfs(v)bfs(v)/ 遞歸訪問所有和v 相連接的未訪問頂點，然后按照全局變量count的值精彩文檔實用標(biāo)準(zhǔn)文案/ 根據(jù)遇到它們的先后順序，給它們附上相應(yīng)的數(shù)字count = count + 1mark v with countinitializ

9、e queue with vwhile queue is not empty doa = front of queuefor each vertex w adjacent to a doif w is marked with 0count = count + 1mark w with countadd w to the end of the queueremove a from the front of the queue拓撲排序第六章變治法Gauss消去法GaussElimination(A1.n, b1.n)/輸入：系數(shù)矩陣A 及常數(shù)項b/ 輸出：方程組的增廣矩陣等價的上三角矩陣for i

10、=1 to n doAin+1 =bifor j= i+1 to n dofor k = i to n+1 doAjk = Ajk Aik*Aji/Aii堆排序堆排序主要包括兩個步驟：對于給定的數(shù)組構(gòu)造相應(yīng)的堆。對所構(gòu)造的堆執(zhí)行n-1 次刪除堆的根結(jié)點的操作，把刪除得到的結(jié)點保存在給定數(shù)組中。1 構(gòu)造堆的效率是多少？精彩文檔實用標(biāo)準(zhǔn)文案O(n)2 推排序的效率O(nlogn)Horner法則第七章 時空權(quán)衡計數(shù)排序比較計數(shù)算法算法ComparisonCountingSort(A0.n-1)/ 用比較計數(shù)法對數(shù)組排序/ 輸入：可排序數(shù)組 A0.n-1/ 輸出：將A 中的元素按照升序排列的數(shù)組S0.n-1For i=0 to n-1 do counti=0For i=0 to n-2 doFor j=i+1 to n-1 doifAiAjCountj=Countj+1Else Counti=Counti+1For i=0 to n-1 do SCounti=AiReturn S精彩文檔實用標(biāo)準(zhǔn)文案C(n)=n(n-1)/2第八章動態(tài)規(guī)劃WARSHALL算法void WARSHALL（ m ）for (i=1; i n; i+ )for (j 1; j n; j+ )if(m j， i