常用的內(nèi)部排序方法

1、 常用的內(nèi)部排序方法有：交換排序（冒泡排序、快速排序）、選擇排序（簡單選擇排序、堆排序）、插入排序（直接插入排序、希爾排序）、歸并排序、基數(shù)排序（一關(guān)鍵字、多關(guān)鍵字）。一、冒泡排序： 1.基本思想：兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個數(shù)據(jù)元素的次序相反時即進行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。2.排序過程：設(shè)想被排序的數(shù)組R1.N垂直豎立，將每個數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上漂浮，如此反復進行，直至最后任何兩個氣泡都是輕者在上，重者在下為止。【示例】：49 13 13 13 13 13 13 1338 4

2、9 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97二、快速排序（Quick Sort） 1.基本思想：在 當前無序區(qū)R1.H中任取一個數(shù)據(jù)元素作為比較的基準(不妨記為X)，用此基準將當前無序區(qū)劃分為左右兩個較小的無序區(qū)：R1.I-1和 RI+1.H，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準元

3、素，而基準X則位于最終排序的位置上，即 R1.I-1X.KeyRI+1.H(1IH)，當R1.I-1和RI+1.H均非空時，分別對它們進行上述的劃分過 程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序為止。 2.排序過程： 【示例】： 初始關(guān)鍵字 49 38 65 97 76 13 27 49 第一次交換后 27 38 65 97 76 13 49 49 第二次交換后 27 38 49 97 76 13 65 49 J向左掃描，位置不變，第三次交換后 27 38 13 97 76 49 65 49 I向右掃描，位置不變，第四次交換后 27 38 13 49 76 97 65 49 J向左掃描 27 3

4、8 13 49 76 97 65 49 （一次劃分過程） 初始關(guān)鍵字 49 38 65 97 76 13 27 49 一趟排序之后 27 38 13 49 76 97 65 49 二趟排序之后 13 27 38 49 49 6576 97 三趟排序之后 13 27 38 49 49 6576 97最后的排序結(jié)果 13 27 38 49 49 65 76 97三、簡單選擇排序 1.基本思想：每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。 2.排序過程：【示例】： 初始關(guān)鍵字 49 38 65 97 76 13 27 49 第一

5、趟排序后 13 38 65 97 76 49 27 49 第二趟排序后 13 27 65 97 76 49 38 49 第三趟排序后 13 27 38 97 76 49 65 49 第四趟排序后 13 27 38 49 49 97 65 76 第五趟排序后 13 27 38 49 49 97 97 76 第六趟排序后 13 27 38 49 49 76 76 97 第七趟排序后 13 27 38 49 49 76 76 97最后排序結(jié)果 13 27 38 49 49 76 76 97四、堆排序(Heap Sort) 1.基本思想： 堆排序是一樹形選擇排序，在排序過程中，將R1.N看成是一顆完全

6、二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。 2.堆的定義: N個元素的序列K1,K2,K3,.,Kn.稱為堆，當且僅當該序列滿足特性： KiK2i Ki K2i+1(1 I N/2) 堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點的關(guān)鍵字均大于等于其孩子結(jié)點的關(guān)鍵字。例如序列10,15,56,25,30,70就是一個 堆，它對應(yīng)的完全二叉樹如上圖所示。這種堆中根結(jié)點（稱為堆頂）的關(guān)鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結(jié)點的關(guān)鍵字均大于等 于其孩子的關(guān)鍵字，則稱之為大根堆。 3.排序過程： 堆排序正是利用小根堆（或大根

7、堆）來選取當前無序區(qū)中關(guān)鍵字小（或最大）的記錄實現(xiàn)排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：將當前無 序區(qū)調(diào)整為一個大根堆，選取關(guān)鍵字最大的堆頂記錄，將它和無序區(qū)中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐 步向前擴大到整個記錄區(qū)?！臼纠浚簩﹃P(guān)鍵字序列42，13，91，23，24，16，05，88建堆五、直接插入排序(Insertion Sort)1. 基本思想：每次將一個待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。2. 排序過程：【示例】：初始關(guān)鍵字 49 38 65 9

8、7 76 13 27 49 J=2(38) 38 49 65 97 76 13 27 49 J=3(65) 38 49 65 97 76 13 27 49 J=4(97) 38 49 65 97 76 13 27 49 J=5(76) 38 49 65 76 97 13 27 49 J=6(13) 13 38 49 65 76 97 27 49 J=7(27) 13 27 38 49 65 76 97 49 J=8(49) 13 27 38 49 49 65 76 97六、希爾排序1.排序思想：先 取一個小于n的證書d1作為第一個增量，把文件的全部記錄分成d1組。所有距離為d1的倍數(shù)的記錄放在

9、同一組中。先在各組內(nèi)進行直接插入排序，然后取第二 個增量d2d1重復上述的分組和排序，直到所取的增量dt=1，即所有記錄放在同一組中進行直接插入排序為止。該方法實際上是一種分組插入方法。2.排序過程：初始關(guān)鍵字 72 28 51 17 96 62 87 33 45 24d1=n/2=5 62 28 33 17 24 72 87 51 45 96d2=d1/2=3 17 24 33 62 28 45 87 51 72 96d3=d2/2=1 17 24 28 33 45 51 62 72 87 96七、歸并排序1.排序思想：設(shè)兩個有序的子文件(相當于輸入堆)放在同一向量中相鄰的位置上：Rlow.

10、m，Rm+1.high，先將它們合并到一個局部的暫存向量R1(相當于輸出堆)中，待合并完成后將R1復制回Rlow.high中。 2.排序過程：【示例】：初始關(guān)鍵字 46385630888038第一趟歸并后38 4630 5680 8838第二趟歸并后30 38 46 5638 80 88最終歸并結(jié)果30 38 38 46 56 80 88八、基數(shù)排序1.排序思想：（1）根據(jù)數(shù)據(jù)項個位上的值，把所有的數(shù)據(jù)項分為10組；（2）然后對這10組數(shù)據(jù)重新排列：把所有以0結(jié)尾的數(shù)據(jù)排在最前面，然后是結(jié)尾是1的數(shù)據(jù)項，照此順序直到以9結(jié)尾的數(shù)據(jù)，這個步驟稱為第一趟子排序；（3）在第二趟子排序中，再次把所有的

11、數(shù)據(jù)項分為10組，但是這一次是根據(jù)數(shù)據(jù)項十位上的值來分組的。這次分組不能改變先前的排序順序。也就是說，第二趟排序之后，從每一組數(shù)據(jù)項的內(nèi)部來看，數(shù)據(jù)項的順序保持不變；（4）然后再把10組數(shù)據(jù)項重新合并，排在最前面的是十位上為0的數(shù)據(jù)項，然后是10位為1的數(shù)據(jù)項，如此排序直到十位上為9的數(shù)據(jù)項。（5）對剩余位重復這個過程，如果某些數(shù)據(jù)項的位數(shù)少于其他數(shù)據(jù)項，那么認為它們的高位為0。2.排序過程【示例】初始關(guān)鍵字 421 240 035 532 305 430 124第一趟排序后240 430 421 532 124 035 305第二趟排序后(305) (421 124) (430 532 03

12、5) (240)最后排序結(jié)果(035) (124) (240) (305) (421 430) (532)時間復雜度排序方法 最好情況 最壞情況 平均情況 穩(wěn)定性 空間復雜度冒泡排序 O(n) O(n2) O(n2) 穩(wěn)定快速排序 O(nlogn) O(n2) O(nlogn) 不穩(wěn)定簡單選擇排序 O(n2) 不穩(wěn)定堆排序 O(nlogn) 不穩(wěn)定直接插入排序 O(n) O(n2) O(n2) 穩(wěn)定希爾排序 O(n1.3) 不穩(wěn)定歸并排序 O(nlogn) O(nlogn) O(nlogn) 穩(wěn)定基數(shù)排序 O(d(r+n) 穩(wěn)定（1）選擇排序最好是 O(n2)（2）快速排序在平均情況下復雜性為

13、O(nlogn)，最壞情況 O(n2)，最好O(nlogn)（3）堆排序和合并排序在最壞情況下復雜性為O(nlogn)。可見，合并排序和堆排序是比較排序算法中時間復雜度最優(yōu)算法?？臻g復雜度空間性能是排序所需輔助空間大小所有簡單排序和堆排序都是0(1)快速排序為0(logn)，要為遞歸程序執(zhí)行過程棧所需的輔助空間歸并排序和基數(shù)排序所需輔助空間最多，為O(n二分搜索技術(shù) 二分搜索算法是運用分治策略的典型例子。 給定已排好序的n個元素a0:n-1，現(xiàn)要在這n個元素中找出一特定元素x。 首先較易想到的是用順序搜索方法，逐個比較a0:n-1中元素，直至找出元素x或搜索遍整個數(shù)組后確定x不在其中。這個方法

14、沒有很好地利用n個元素已排好序這個條件，因此在最壞的情況下，順序搜索方法需要O(n)次比較。 二分搜索方法充分利用了元素間的次序關(guān)系(但也局限于此)，采用分治策略，可在最壞的情況下用O(logn)時間完成搜索任務(wù)。 二分搜索算法的基本思想是將n個元素分成個數(shù)大致相同的兩半，取an/2與x進行比較。如果x=an/2，則找到x，算法終止。如果xan/2，則只要在數(shù)組a的右半部繼續(xù)搜索x。具體算法可描述如下(使用Java語言描述)：public static int binarySearch(int a,int x,int n) /在a0到an-1中搜索，其中a0=an-1 int left=0;

15、int right=n-1; while(leftamiddle) left=middle+1; else right=middle-1; return -1; /表示未找到 容易看出，每執(zhí)行一次算法的while循環(huán)，帶搜索數(shù)組的大小減半。因此，在最壞的情況下，while循環(huán)執(zhí)行了O(logn)次。循環(huán)體內(nèi)運算需要O(1)時間，因此，整個算法在最壞的情況下的計算時間復雜性為O(logn)。大整數(shù)乘法問題分治法球兩個n位大整數(shù)u，v的乘積，將u，v都分割成長度為n/3位的3段，證明用5次n/3位整數(shù)的乘法可以求得uv的值！解題思路：將u分成3段：u1+u2+u3 將V分成3段：v1+v2+v3

16、考慮函數(shù) f(x)=u1*x2+u2*x+u3，g(x)=v1*x2+v2*x+v3 及f(x)*g(x)=w1*x4+w2*x3+w3*x2+w4*x+w5 則問題的本質(zhì)就是用5次n/3位整數(shù)乘法計算出w1,w2,w3,w4,w5 給定5個值：譬如xi=0,1,2,-1,-2可得到5個n/3位整數(shù)乘法： k1=(u1*x12+u2*x1+u3)(v1*x12+v2*x1+v3) k2=(u1*x22+u2*x2+u3)(v1*x22+v2*x2+v3) . 而另一方面，由5個以k1,k2,.,k5作為常數(shù)，w1,w2,.,w5為變元的方程組，可以求出用k1,k2,.,k5表示w1,w2,.,

17、w5的表達式。 而由k1,k2,.,k5計算w1,w2,.,w5僅需要一些加減法及移位運算。1合并排序合并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。 合并排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。 將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。合并排序也叫歸并排序。2復雜度時間O(nlogn)空間O(n)與快速排序類似動態(tài)規(guī)劃

18、矩陣連乘的問題問題的引出看下面一個例子，計算三個矩陣連乘A1，A2，A3；維數(shù)分別為10*100 , 100*5 , 5*50按此順序計算需要的次數(shù)（A1*A2）*A3）:10X100X5+10X5X50=7500次按此順序計算需要的次數(shù)（A1*（A2*A3）:10X5X50+10X100X50=75000次所以問題是：如何確定運算順序，可以使計算量達到最小化。枚舉顯然不可，如果枚舉的話，相當于一個“完全加括號問題”，次數(shù)為卡特蘭數(shù),卡特蘭數(shù)指數(shù)增長，必然不行。建立遞歸關(guān)系子問題狀態(tài)的建模（很關(guān)鍵）：令mij表示第i個矩陣至第j個矩陣這段的最優(yōu)解。顯然如果i=j，則mij這段中就一個矩陣，需要

19、計算的次數(shù)為0；如果ij，則mij=minmik+mk+1j+pi-1XpkXpj,其中k,在i與j之間游蕩，所以i=kj ;代碼實現(xiàn)時需要注意的問題：計算順序！因為你要保證在計算mij查找mik和mk+1j的時候，mik和mk+1j已經(jīng)計算出來了。觀察坐標的關(guān)系如圖：所以計算順序如上右圖：相應(yīng)的計算順序?qū)?yīng)代碼為13-15行m1n即為最終求解，最終的輸出想為（A1（A2 A3）（A4 A5）A6）的形式，不過沒有成功，待思考矩陣連乘問題動態(tài)規(guī)劃矩陣連乘算法問題：給定n個矩陣A1,A2,.,An，使得n個矩陣的連乘A1A2.An的計算量最小。因為矩陣的乘法滿足結(jié)合律，所以問題簡化為怎么加括號。

20、使用動態(tài)規(guī)劃解決該問題：1.分析最優(yōu)解的結(jié)構(gòu)（找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征）記A1A2.An為Ai,j，計算次序在Ak和Ak+1之間斷開，所以，得計算A1,k和Ak+1,n，然后再相乘得到A1,n，依此計算順序總計算量為A1,k的計算量加上Ak+1,n的計算量，再加上A1,k和Ak+1,n相乘的計算量。2.建立遞歸關(guān)系(遞歸定義最優(yōu)值）設(shè)計算Ai,j，1=i=j=n，所需的最少數(shù)乘次數(shù)為mij，則原問題的最優(yōu)值為m1n。當i=j，mij=0；當ij，mij=min(i=kj)mik+mk+1j+p(i-1)p(k)p(j)最優(yōu)次序中斷開位置k記為sij。3.計算最優(yōu)值（以自底向上的方式計

21、算出最優(yōu)值）void MatrixChain(int *p,int n,int *m,int *s)for(int i=1;i=n;i+) mii=0for(int r=2;r=n;r+)for（int i=1;i=n-r+1;i+)int j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;kj;k+)int t=mik+mk+1j+pi-1*pk*pj;if(tmij)mij=t;sij=k;算法首先計算出mii=0；然后按矩陣的遞增的方式依此計算mii+1,i=1,2,3,.,n-1;mii+2.其中r就是這個鏈長，兩個for循環(huán)就是填表的過

22、程，這里的二維數(shù)組m就是表格，用來記錄已經(jīng)解決的子問題的答案，不管是不是以后要用到，都記錄下來。4.構(gòu)造最優(yōu)解（根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解）表格s中記錄了最優(yōu)解的斷開點信息。void Traceback(int i,int j,int *s)if(i=j) return;Traceback(i,sij,s);Traceback(sij+1,j,s);coutMultiply A i,sij;coutand A(sij+1),jendl;動態(tài)規(guī)劃解最長公共子序列問題2009-05-30 21:2848835人閱讀評論(43)收藏舉報c算法動態(tài)規(guī)劃法經(jīng)常會遇到復雜問題不能簡單地分解成幾

23、個子問題，而會分解出一系列的子問題。簡單地采用把大問題分解成子問題，并綜合子問題的解導出大問題的解的方法，問題求解耗時會按問題規(guī)模呈冪級數(shù)增加。為了節(jié)約重復求相同子問題的時間，引入一個數(shù)組，不管它們是否對最終解有用，把所有子問題的解存于該數(shù)組中，這就是動態(tài)規(guī)劃法所采用的基本方法。【問題】求兩字符序列的最長公共字符子序列問題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個字符（可能一個也不去掉）后所形成的字符序列。令給定的字符序列X=“x0，x1，xm-1”，序列Y=“y0，y1，yk-1”是X的子序列，存在X的一個嚴格遞增下標序列，使得對所有的j=0，1，k-1，有xi

24、j=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個子序列?？紤]最長公共子序列問題如何分解成子問題，設(shè)A=“a0，a1，am-1”，B=“b0，b1，bm-1”，并Z=“z0，z1，zk-1”為它們的最長公共子序列。不難證明有以下性質(zhì)：（1）如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，zk-2”是“a0，a1，am-2”和“b0，b1，bn-2”的一個最長公共子序列；（2）如果am-1!=bn-1，則若zk-1!=am-1，蘊涵“z0，z1，zk-1”是“a0，a1，am-2”和“b0，b1，bn-1”的一個最長公共子序列；（3）如果am-1!=bn-

25、1，則若zk-1!=bn-1，蘊涵“z0，z1，zk-1”是“a0，a1，am-1”和“b0，b1，bn-2”的一個最長公共子序列。這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進一步解決一個子問題，找“a0，a1，am-2”和“b0，b1，bm-2”的一個最長公共子序列；如果am-1!=bn-1，則要解決兩個子問題，找出“a0，a1，am-2”和“b0，b1，bn-1”的一個最長公共子序列和找出“a0，a1，am-1”和“b0，b1，bn-2”的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。求解：引進一個二維數(shù)組c，用cij記錄Xi與Yj 的LCS 的長度，bi

26、j記錄cij是通過哪一個子問題的值求得的，以決定搜索的方向。我們是自底向上進行遞推計算，那么在計算ci,j之前，ci-1j-1，ci-1j與cij-1均已計算出來。此時我們根據(jù)Xi = Yj還是Xi != Yj，就可以計算出cij。問題的遞歸式寫成：回溯輸出最長公共子序列過程：算法分析：由于每次調(diào)用至少向上或向左（或向上向左同時）移動一步，故最多調(diào)用(m + n)次就會遇到i = 0或j = 0的情況，此時開始返回。返回時與遞歸調(diào)用時方向相反，步數(shù)相同，故算法時間復雜度為(m + n)。代碼： #include#include#defineMAXLEN100voidLCSLength(char

27、*x,char*y,intm,intn,intcMAXLEN,intbMAXLEN)inti,j;for(i=0;i=m;i+)ci0=0;for(j=1;j=n;j+)c0j=0;for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;bij=1;elsecij=cij-1;bij=-1;voidPrintLCS(intbMAXLEN,char*x,inti,intj)if(i=0|j=0)return;if(bij=0)PrintLCS(b,x,i-1,j-1);printf(%c,xi-1);elseif(bij=1)PrintLCS(b,x,i-1,j);el

28、sePrintLCS(b,x,i,j-1);intmain(intargc,char*argv)charxMAXLEN=ABCBDAB;charyMAXLEN=BDCABA;intbMAXLENMAXLEN;intcMAXLENMAXLEN;intm,n;m=strlen(x);n=strlen(y);LCSLength(x,y,m,n,c,b);PrintLCS(b,x,m,n);return0;動態(tài)規(guī)劃之最長公共子序列算法 (2009-10-17 00:22:09)標簽：雜談最長公共子序列問題LCS問題描述參考解答動態(tài)規(guī)劃算法可有效地解此問題。下面我們按照動態(tài)規(guī)劃算法設(shè)計的各個步驟來設(shè)計一

29、個解此問題的有效算法。1.最長公共子序列的結(jié)構(gòu)解最長公共子序列問題時最容易想到的算法是窮舉搜索法，即對X的每一個子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，并且在檢查過程中選出最長的公共子序列。X的所有子序列都檢查過后即可求出X和Y的最長公共子序列。X的一個子序列相應(yīng)于下標序列1, 2, , m的一個子序列，因此，X共有2m個不同子序列，從而窮舉搜索法需要指數(shù)時間。事實上，最長公共子序列問題也有最優(yōu)子結(jié)構(gòu)性質(zhì)，因為我們有如下定理：定理: LCS的最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)序列X=和Y=的一個最長公共子序列Z=，則：1. 若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn

30、-1的最長公共子序列；2. 若xmyn且zkxm ，則Z是Xm-1和Y的最長公共子序列；3. 若xmyn且zkyn ，則Z是X和Yn-1的最長公共子序列。其中Xm-1=，Yn-1=，Zk-1=。證明1. 用反證法。若zkxm，則是X和Y的長度為k十1的公共子序列。這與Z是X和Y的一個最長公共子序列矛盾。因此，必有zk=xm=yn。由此可知Zk-1是Xm-1和Yn-1的一個長度為k-1的公共子序列。若Xm-1和Yn-1有一個長度大于k-1的公共子序列W，則將xm加在其尾部將產(chǎn)生X和Y的一個長度大于k的公共子序列。此為矛盾。故Zk-1是Xm-1和Yn-1的一個最長公共子序列。2. 由于zkxm，Z

31、是Xm-1和Y的一個公共子序列。若Xm-1和Y有一個長度大于k的公共子序列W，則W也是X和Y的一個長度大于k的公共子序列。這與Z是X和Y的一個最長公共子序列矛盾。由此即知Z是Xm-1和Y的一個最長公共子序列。3. 與 2.類似。這個定理告訴我們，兩個序列的最長公共子序列包含了這兩個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2.子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出X=和Y=的最長公共子序列，可按以下方式遞歸地進行：當xm=yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個最長公共子序列。當xm

32、yn時，必須解兩個子問題，即找出Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。由此遞歸結(jié)構(gòu)容易看到最長公共子序列問題具有子問題重疊性質(zhì)。例如，在計算X和Y的最長公共子序列時，可能要計算出X和Yn-1及Xm-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算Xm-1和Yn-1的最長公共子序列。與矩陣連乘積最優(yōu)計算次序問題類似，我們來建立子問題的最優(yōu)值的遞歸關(guān)系。用ci,j記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=，Yj=。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故ci,j=0。

33、其他情況下，由定理可建立遞歸關(guān)系如下：3.計算最優(yōu)值直接利用(2.2)式容易寫出一個計算ci,j的遞歸算法，但其計算時間是隨輸入長度指數(shù)增長的。由于在所考慮的子問題空間中，總共只有(m*n)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。計算最長公共子序列長度的動態(tài)規(guī)劃算法LCS_LENGTH(X,Y)以序列X=和Y=作為輸入。輸出兩個數(shù)組c0.m ,0.n和b1.m ,1.n。其中ci,j存儲Xi與Yj的最長公共子序列的長度，bi,j記錄指示ci,j的值是由哪一個子問題的解達到的，這在構(gòu)造最長公共子序列時要用到。最后，X和Y的最長公共子序列的長度記錄于cm,n中。P

34、rocedure LCS_LENGTH(X,Y);beginm:=lengthX;n:=lengthY;for i:=1 to m do ci,j:=0;for j:=1 to n do c0,j:=0;for i:=1 to m dofor j:=1 to n doif xi=yj thenbeginci,j:=ci-1,j-1+1;bi,j:=;endelse if ci-1,jci,j-1 thenbeginci,j:=ci-1,j;bi,j:=;endelsebeginci,j:=ci,j-1;bi,j:=end;return(c,b);end;由于每個數(shù)組單元的計算耗費(1)時間，算

35、法LCS_LENGTH耗時(mn)。4.構(gòu)造最長公共子序列由算法LCS_LENGTH計算得到的數(shù)組b可用于快速構(gòu)造序列X=和Y=的最長公共子序列。首先從bm,n開始，沿著其中的箭頭所指的方向在數(shù)組b中搜索。當bi,j中遇到時，表示Xi與Yj的最長公共子序列是由Xi-1與Yj-1的最長公共子序列在尾部加上xi得到的子序列；當bi,j中遇到時，表示Xi與Yj的最長公共子序列和Xi-1與Yj的最長公共子序列相同；當bi,j中遇到時，表示Xi與Yj的最長公共子序列和Xi與Yj-1的最長公共子序列相同。下面的算法LCS(b,X,i,j)實現(xiàn)根據(jù)b的內(nèi)容打印出Xi與Yj的最長公共子序列。通過算法的調(diào)用LC

36、S(b,X,lengthX,lengthY)，便可打印出序列X和Y的最長公共子序列。Procedure LCS(b,X,i,j);beginif i=0 or j=0 then return;if bi,j= thenbeginLCS(b,X,i-1,j-1);print(xi); 打印xiendelse if bi,j= then LCS(b,X,i-1,j)else LCS(b,X,i,j-1);end;在算法LCS中，每一次的遞歸調(diào)用使i或j減1，因此算法的計算時間為O(m+n)。例如，設(shè)所給的兩個序列為X=和Y=。由算法LCS_LENGTH和LCS計算出的結(jié)果如圖2所示。j 0 1 2

37、 3 4 5 6 i yj B D C A B A 0 xi 0 0 0 0 0 0 1 A 0 0 0 0 1 1 1 2 B 0 1 1 1 1 2 2 3 C 0 1 1 2 2 2 2 4 B 0 1 1 2 2 3 3 5 D 0 1 2 2 2 3 3 6 A 0 1 2 2 3 3 4 7 B 0 1 2 2 3 4 5 圖2算法LCS的計算結(jié)果5.算法的改進對于一個具體問題，按照一般的算法設(shè)計策略設(shè)計出的算法，往往在算法的時間和空間需求上還可以改進。這種改進，通常是利用具體問題的一些特殊性。例如，在算法LCS_LENGTH和LCS中，可進一步將數(shù)組b省去。事實上，數(shù)組元素ci,

38、j的值僅由ci-1,j-1，ci-1,j和 ci,j-1三個值之一確定，而數(shù)組元素bi,j也只是用來指示ci,j究竟由哪個值確定。因此，在算法LCS中，我們可以不借助于數(shù)組b而借助于數(shù)組c本身臨時判斷ci,j的值是由ci-1,j-1，ci-1,j和ci,j-1中哪一個數(shù)值元素所確定，代價是(1)時間。既然b對于算法LCS不是必要的，那么算法LCS_LENGTH便不必保存它。這一來，可節(jié)省(mn)的空間，而LCS_LENGTH和LCS所需要的時間分別仍然是(mn)和(m+n)。不過，由于數(shù)組c仍需要(mn)的空間，因此這里所作的改進，只是在空間復雜性的常數(shù)因子上的改進。另外，如果只需要計算最長公

39、共子序列的長度，則算法的空間需求還可大大減少。事實上，在計算ci,j時，只用到數(shù)組c的第i行和第i-1行。因此，只要用2行的數(shù)組空間就可以計算出最長公共子序列的長度。更進一步的分析還可將空間需求減至min(m, n)。#include #define MAX 100char xMAX+1,yMAX+1;int bMAX+1MAX+1,cMAX+1MAX+1,m,n;static void Init_XY(void);static void LCS_Length(void);static void LCS(int i,int j);int main (int argc,char *argv)Init_XY();LCS_Length();printf(The lowest common subsequence is :n);LCS(m,n);printf(n);getchar();return 0;static void Init_XY(void)int i;printf(Please input two sequence numbers:);scanf_s(%d%d,&m,&n);getchar();printf(Please input two sequenc