1、 常用的內(nèi)部排序方法有：交換排序（冒泡排序、快速排序）、選擇排序（簡(jiǎn)單選擇排序、堆排序）、插入排序（直接插入排序、希爾排序）、歸并排序、基數(shù)排序（一關(guān)鍵字、多關(guān)鍵字）。一、冒泡排序： 1.基本思想：兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)元素的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。2.排序過程：設(shè)想被排序的數(shù)組R1.N垂直豎立，將每個(gè)數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上漂浮，如此反復(fù)進(jìn)行，直至最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。【示例】：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.基本思想：在 當(dāng)前無序區(qū)R1.H中任取一個(gè)數(shù)據(jù)元素作為比較的基準(zhǔn)(不妨記為X)，用此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左右兩個(gè)較小的無序區(qū)：R1.I-1和 RI+1.H，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元

3、素，而基準(zhǔn)X則位于最終排序的位置上，即 R1.I-1X.KeyRI+1.H(1IH)，當(dāng)R1.I-1和RI+1.H均非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過 程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?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三、簡(jiǎn)單選擇排序 1.基本思想：每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，順序放在已排好序的數(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、二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來選擇最小的元素。 2.堆的定義: N個(gè)元素的序列K1,K2,K3,.,Kn.稱為堆，當(dāng)且僅當(dāng)該序列滿足特性： KiK2i Ki K2i+1(1 I N/2) 堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子結(jié)點(diǎn)的關(guān)鍵字。例如序列10,15,56,25,30,70就是一個(gè) 堆，它對(duì)應(yīng)的完全二叉樹如上圖所示。這種堆中根結(jié)點(diǎn)（稱為堆頂）的關(guān)鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等 于其孩子的關(guān)鍵字，則稱之為大根堆。 3.排序過程： 堆排序正是利用小根堆（或大根

7、堆）來選取當(dāng)前無序區(qū)中關(guān)鍵字小（或最大）的記錄實(shí)現(xiàn)排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：將當(dāng)前無 序區(qū)調(diào)整為一個(gè)大根堆，選取關(guān)鍵字最大的堆頂記錄，將它和無序區(qū)中的最后一個(gè)記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐 步向前擴(kuò)大到整個(gè)記錄區(qū)。【示例】：對(duì)關(guān)鍵字序列42，13，91，23，24，16，05，88建堆五、直接插入排序(Insertion Sort)1. 基本思想：每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(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.排序思想：先 取一個(gè)小于n的證書d1作為第一個(gè)增量，把文件的全部記錄分成d1組。所有距離為d1的倍數(shù)的記錄放在

9、同一組中。先在各組內(nèi)進(jìn)行直接插入排序，然后取第二 個(gè)增量d2d1重復(fù)上述的分組和排序，直到所取的增量dt=1，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。該方法?shí)際上是一種分組插入方法。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è)兩個(gè)有序的子文件(相當(dāng)于輸入堆)放在同一向量中相鄰的位置上：Rlow.

10、m，Rm+1.high，先將它們合并到一個(gè)局部的暫存向量R1(相當(dāng)于輸出堆)中，待合并完成后將R1復(fù)制回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ù)項(xiàng)個(gè)位上的值，把所有的數(shù)據(jù)項(xiàng)分為10組；（2）然后對(duì)這10組數(shù)據(jù)重新排列：把所有以0結(jié)尾的數(shù)據(jù)排在最前面，然后是結(jié)尾是1的數(shù)據(jù)項(xiàng)，照此順序直到以9結(jié)尾的數(shù)據(jù)，這個(gè)步驟稱為第一趟子排序；（3）在第二趟子排序中，再次把所有的

11、數(shù)據(jù)項(xiàng)分為10組，但是這一次是根據(jù)數(shù)據(jù)項(xiàng)十位上的值來分組的。這次分組不能改變先前的排序順序。也就是說，第二趟排序之后，從每一組數(shù)據(jù)項(xiàng)的內(nèi)部來看，數(shù)據(jù)項(xiàng)的順序保持不變；（4）然后再把10組數(shù)據(jù)項(xiàng)重新合并，排在最前面的是十位上為0的數(shù)據(jù)項(xiàng)，然后是10位為1的數(shù)據(jù)項(xiàng)，如此排序直到十位上為9的數(shù)據(jù)項(xiàng)。（5）對(duì)剩余位重復(fù)這個(gè)過程，如果某些數(shù)據(jù)項(xiàng)的位數(shù)少于其他數(shù)據(jù)項(xiàng)，那么認(rèn)為它們的高位為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)時(shí)間復(fù)雜度排序方法 最好情況 最壞情況 平均情況 穩(wěn)定性 空間復(fù)雜度冒泡排序 O(n) O(n2) O(n2) 穩(wěn)定快速排序 O(nlogn) O(n2) O(nlogn) 不穩(wěn)定簡(jiǎ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）快速排序在平均情況下復(fù)雜性為

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

14、沒有很好地利用n個(gè)元素已排好序這個(gè)條件，因此在最壞的情況下，順序搜索方法需要O(n)次比較。 二分搜索方法充分利用了元素間的次序關(guān)系(但也局限于此)，采用分治策略，可在最壞的情況下用O(logn)時(shí)間完成搜索任務(wù)。 二分搜索算法的基本思想是將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取an/2與x進(jìn)行比較。如果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)運(yùn)算需要O(1)時(shí)間，因此，整個(gè)算法在最壞的情況下的計(jì)算時(shí)間復(fù)雜性為O(logn)。大整數(shù)乘法問題分治法球兩個(gè)n位大整數(shù)u，v的乘積，將u，v都分割成長(zhǎng)度為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ù)乘法計(jì)算出w1,w2,w3,w4,w5 給定5個(gè)值：譬如xi=0,1,2,-1,-2可得到5個(gè)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個(gè)以k1,k2,.,k5作為常數(shù)，w1,w2,.,w5為變?cè)姆匠探M，可以求出用k1,k2,.,k5表示w1,w2,.,

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

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

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

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

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;算法首先計(jì)算出mii=0；然后按矩陣的遞增的方式依此計(jì)算mii+1,i=1,2,3,.,n-1;mii+2.其中r就是這個(gè)鏈長(zhǎng)，兩個(gè)for循環(huán)就是填表的過

22、程，這里的二維數(shù)組m就是表格，用來記錄已經(jīng)解決的子問題的答案，不管是不是以后要用到，都記錄下來。4.構(gòu)造最優(yōu)解（根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解）表格s中記錄了最優(yōu)解的斷開點(diǎn)信息。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;動(dòng)態(tài)規(guī)劃解最長(zhǎng)公共子序列問題2009-05-30 21:2848835人閱讀評(píng)論(43)收藏舉報(bào)c算法動(dòng)態(tài)規(guī)劃法經(jīng)常會(huì)遇到復(fù)雜問題不能簡(jiǎn)單地分解成幾

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

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

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

26、j記錄cij是通過哪一個(gè)子問題的值求得的，以決定搜索的方向。我們是自底向上進(jìn)行遞推計(jì)算，那么在計(jì)算ci,j之前，ci-1j-1，ci-1j與cij-1均已計(jì)算出來。此時(shí)我們根據(jù)Xi = Yj還是Xi != Yj，就可以計(jì)算出cij。問題的遞歸式寫成：回溯輸出最長(zhǎng)公共子序列過程：算法分析：由于每次調(diào)用至少向上或向左（或向上向左同時(shí)）移動(dòng)一步，故最多調(diào)用(m + n)次就會(huì)遇到i = 0或j = 0的情況，此時(shí)開始返回。返回時(shí)與遞歸調(diào)用時(shí)方向相反，步數(shù)相同，故算法時(shí)間復(fù)雜度為(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;動(dòng)態(tài)規(guī)劃之最長(zhǎng)公共子序列算法 (2009-10-17 00:22:09)標(biāo)簽：雜談最長(zhǎng)公共子序列問題LCS問題描述參考解答動(dòng)態(tài)規(guī)劃算法可有效地解此問題。下面我們按照動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)的各個(gè)步驟來設(shè)計(jì)一

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

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

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

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

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

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

36、S(b,X,lengthX,lengthY)，便可打印出序列X和Y的最長(zhǎng)公共子序列。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，因此算法的計(jì)算時(shí)間為O(m+n)。例如，設(shè)所給的兩個(gè)序列為X=和Y=。由算法LCS_LENGTH和LCS計(jì)算出的結(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的計(jì)算結(jié)果5.算法的改進(jìn)對(duì)于一個(gè)具體問題，按照一般的算法設(shè)計(jì)策略設(shè)計(jì)出的算法，往往在算法的時(shí)間和空間需求上還可以改進(jìn)。這種改進(jìn)，通常是利用具體問題的一些特殊性。例如，在算法LCS_LENGTH和LCS中，可進(jìn)一步將數(shù)組b省去。事實(shí)上，數(shù)組元素ci,

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

39、共子序列的長(zhǎng)度，則算法的空間需求還可大大減少。事實(shí)上，在計(jì)算ci,j時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，只要用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。更進(jìn)一步的分析還可將空間需求減至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