算法設(shè)計及的分析部分算法偽代碼

1、*第三章蠻力法1. 選擇排序Selectio nSort(A0. n-1)for i=0 to n-2 domin=ifor j=i+1 to n-1 doif Aj<Ami nmi n=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+1<Aj swap Aj a nd Aj+13. 改進(jìn)的冒泡算法ALGORITHM BubbleSortlmproved( A0,r1)-/冒泡排序算法的改進(jìn)/輸入

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

3、0while Ai!=K doiv-i+1if ivn return iElse return -15. 蠻力字符串匹配算法BruteForceStringMatch (T 0n-1,P0m-1)/該算法實現(xiàn)了蠻力字符串匹配/輸入：一個n個字符的數(shù)組T0.n-1 代表一段文本/ 一個m個字符的數(shù)組P0.m-1代表一個模式/輸出：如果查找成功的話，返回文本的第一個匹配字串中第一個字符的位置，/否則返回-1For i<-0 to n-m dojv-0While jvm and Pj=Ti 切dojv-i+1If j=m return ireturn -1合并排序最差O (nlog2n)快速排

4、序最優(yōu)O (nlog2n)最差O (n2)平均 O (1.38nlog2n)選擇排序 O (n2)冒泡排序 O (n2)插入排序最差O (n2)最優(yōu)O (n)平均O (n2)*第四章分治法合并排序算法 MergeSort(A0.n-1)/遞歸調(diào)用 mergesort來對數(shù)組 A0.n-1排序/輸入：一個可排序數(shù)組A0.n-1/輸出：非降序排列的數(shù)組A0.n-1if n > 1copy A0. |ln/2 -1 to B0. |ln/2 -1 copy A |ln/2 .n-1 to C0. |ln/2 -1 MergeSort( B )MergeSort( C )Merge( B,C,A

5、 )兩個數(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=O,j=O,k=O;while i<p and j<q doif Bi w CjAk=Bi, i=i+1elseAk=Cj, j=j+1k=k+1if i=pcopy Cj.q-1 to Ak.p+q-1elsecopy Bi.p-1 to A0.p+q-1快速排序算法QuickSort(Al.r)/使用快速排序法對序列或者子序列排序/輸入：子序列 Al.r或

6、者序列本身 A0.n-1/輸出：非遞減序列 Aif l < rs J 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 j Al i j l; j j r+1repeatrepeat i J i + 1 until Ai > prepeat j J j - 1until Aj < pswap( Ai, Aj)until i > jswap( Ai, Aj)s

7、wap( Al, Aj)return j折半查找Bin arySearch( A0. n-1, k )/輸入：已排序大小為n的序列A，待搜索對象k/輸出：如果搜索成功，則返回k的位置，否則返回-1l=0,r= n-1;While l w rmid= kl+r)/2if k = Amid return midelse if k < Amid r=m-1else l=m+1return -1*Strassen 矩陣Strasse n 方法M仁 A11(B12-B22)M2=(A11+A12)B22M3=(A21+A22)B11M4=A22(B21-B11)M5=(A11+A22)(B11+B

8、22)M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)第五章減治法插入排序ALGORITHM In sertio nSort( A0. n-1)/對給定序列進(jìn)行直接插入排序/輸入：大小為n的無序序列A/輸出：按非遞減排列的序列Afor i j 1 to n-1 dotemp j Aij j i-1while j > 0 and Aj > temp doAj+1 j Ajj j j -Aj+1 j temp深度優(yōu)先查找算法BFS (G)實現(xiàn)給定圖的深度優(yōu)先查找遍歷輸入：圖G=<V,E>V中的輸出：圖G的頂點，按照被 DFS遍歷第一次訪問

9、到的先后次序，用連續(xù)的整數(shù)標(biāo)記，將 每個頂點標(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 + 1mark v with countfor each vertex w adjace nt to v doif w is marked with 0dfs(w

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

11、ot empty doa = front of queuefor each vertex w adjace nt 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拓?fù)渑判虻诹伦冎畏℅auss消去法GaussElimi natio n(A1. .n, b1. n)/輸入：系數(shù)矩陣A及常數(shù)項b/輸出：方程組的增廣矩陣等價的上三角矩陣for i=1 to n doAi n+1 =bifor j=

12、 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)造堆的效率是多少？0(n)2推排序的效率0( nlog n)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 cou nti=0For i=0 to n-2 doFor j=i+1 to n-1 doifAi<AjCou ntj=Cou ntj+1Else Cou nti=Cou nti+1For i=0 to n-1 do SCou nti=AiRetur n SC( 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 = T)for (k=1; i< = n; i+ )m j, k + = m i , k;(4)該算法由鄰