常用的内部排序方法

1、 常用的内部排序方法有：交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、插入排序（直接插入排序、希尔排序）、归并排序、基数排序（一关键字、多关键字）。一、冒泡排序： 1.基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。2.排序过程：设想被排序的数组R1.N垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组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.基本思想：在 当前无序区R1.H中任取一个数据元素作为比较的基准(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R1.I-1和 RI+1.H，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元

3、素，而基准X则位于最终排序的位置上，即 R1.I-1X.KeyRI+1.H(1IH)，当R1.I-1和RI+1.H均非空时，分别对它们进行上述的划分过 程，直至所有无序子区中的数据元素均已排序为止。 2.排序过程： 【示例】： 初始关键字 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 （一次划分过程） 初始关键字 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最后的排序结果 13 27 38 49 49 65 76 97三、简单选择排序 1.基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2.排序过程：【示例】： 初始关键字 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最后排序结果 13 27 38 49 49 76 76 97四、堆排序(Heap Sort) 1.基本思想： 堆排序是一树形选择排序，在排序过程中，将R1.N看成是一颗完全

6、二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。 2.堆的定义: N个元素的序列K1,K2,K3,.,Kn.称为堆，当且仅当该序列满足特性： KiK2i Ki K2i+1(1 I N/2) 堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个 堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等 于其孩子的关键字，则称之为大根堆。 3.排序过程： 堆排序正是利用小根堆（或大根

7、堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无 序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐 步向前扩大到整个记录区。【示例】：对关键字序列42，13，91，23，24，16，05，88建堆五、直接插入排序(Insertion Sort)1. 基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。2. 排序过程：【示例】：初始关键字 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的倍数的记录放在

9、同一组中。先在各组内进行直接插入排序，然后取第二 个增量d2d1重复上述的分组和排序，直到所取的增量dt=1，即所有记录放在同一组中进行直接插入排序为止。该方法实际上是一种分组插入方法。2.排序过程：初始关键字 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.排序思想：设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：Rlow.

10、m，Rm+1.high，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回Rlow.high中。 2.排序过程：【示例】：初始关键字 46385630888038第一趟归并后38 4630 5680 8838第二趟归并后30 38 46 5638 80 88最终归并结果30 38 38 46 56 80 88八、基数排序1.排序思想：（1）根据数据项个位上的值，把所有的数据项分为10组；（2）然后对这10组数据重新排列：把所有以0结尾的数据排在最前面，然后是结尾是1的数据项，照此顺序直到以9结尾的数据，这个步骤称为第一趟子排序；（3）在第二趟子排序中，再次把所有的

11、数据项分为10组，但是这一次是根据数据项十位上的值来分组的。这次分组不能改变先前的排序顺序。也就是说，第二趟排序之后，从每一组数据项的内部来看，数据项的顺序保持不变；（4）然后再把10组数据项重新合并，排在最前面的是十位上为0的数据项，然后是10位为1的数据项，如此排序直到十位上为9的数据项。（5）对剩余位重复这个过程，如果某些数据项的位数少于其他数据项，那么认为它们的高位为0。2.排序过程【示例】初始关键字 421 240 035 532 305 430 124第一趟排序后240 430 421 532 124 035 305第二趟排序后(305) (421 124) (430 532 03

12、5) (240)最后排序结果(035) (124) (240) (305) (421 430) (532)时间复杂度排序方法 最好情况 最坏情况 平均情况 稳定性 空间复杂度冒泡排序 O(n) O(n2) O(n2) 稳定快速排序 O(nlogn) O(n2) O(nlogn) 不稳定简单选择排序 O(n2) 不稳定堆排序 O(nlogn) 不稳定直接插入排序 O(n) O(n2) O(n2) 稳定希尔排序 O(n1.3) 不稳定归并排序 O(nlogn) O(nlogn) O(nlogn) 稳定基数排序 O(d(r+n) 稳定（1）选择排序最好是 O(n2)（2）快速排序在平均情况下复杂性为

13、O(nlogn)，最坏情况 O(n2)，最好O(nlogn)（3）堆排序和合并排序在最坏情况下复杂性为O(nlogn)。可见，合并排序和堆排序是比较排序算法中时间复杂度最优算法。空间复杂度空间性能是排序所需辅助空间大小所有简单排序和堆排序都是0(1)快速排序为0(logn)，要为递归程序执行过程栈所需的辅助空间归并排序和基数排序所需辅助空间最多，为O(n二分搜索技术 二分搜索算法是运用分治策略的典型例子。 给定已排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。 首先较易想到的是用顺序搜索方法，逐个比较a0:n-1中元素，直至找出元素x或搜索遍整个数组后确定x不在其中。这个方法

14、没有很好地利用n个元素已排好序这个条件，因此在最坏的情况下，顺序搜索方法需要O(n)次比较。 二分搜索方法充分利用了元素间的次序关系(但也局限于此)，采用分治策略，可在最坏的情况下用O(logn)时间完成搜索任务。 二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取an/2与x进行比较。如果x=an/2，则找到x，算法终止。如果xan/2，则只要在数组a的右半部继续搜索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; /表示未找到 容易看出，每执行一次算法的while循环，带搜索数组的大小减半。因此，在最坏的情况下，while循环执行了O(logn)次。循环体内运算需要O(1)时间，因此，整个算法在最坏的情况下的计算时间复杂性为O(logn)。大整数乘法问题分治法球两个n位大整数u，v的乘积，将u，v都分割成长度为n/3位的3段，证明用5次n/3位整数的乘法可以求得uv的值！解题思路：将u分成3段：u1+u2+u3 将V分成3段：v1+v2+v3

16、考虑函数 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 则问题的本质就是用5次n/3位整数乘法计算出w1,w2,w3,w4,w5 给定5个值：譬如xi=0,1,2,-1,-2可得到5个n/3位整数乘法： 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作为常数，w1,w2,.,w5为变元的方程组，可以求出用k1,k2,.,k5表示w1,w2,.,

17、w5的表达式。 而由k1,k2,.,k5计算w1,w2,.,w5仅需要一些加减法及移位运算。1合并排序合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。2复杂度时间O(nlogn)空间O(n)与快速排序类似动态规划

18、矩阵连乘的问题问题的引出看下面一个例子，计算三个矩阵连乘A1，A2，A3；维数分别为10*100 , 100*5 , 5*50按此顺序计算需要的次数（A1*A2）*A3）:10X100X5+10X5X50=7500次按此顺序计算需要的次数（A1*（A2*A3）:10X5X50+10X100X50=75000次所以问题是：如何确定运算顺序，可以使计算量达到最小化。枚举显然不可，如果枚举的话，相当于一个“完全加括号问题”，次数为卡特兰数,卡特兰数指数增长，必然不行。建立递归关系子问题状态的建模（很关键）：令mij表示第i个矩阵至第j个矩阵这段的最优解。显然如果i=j，则mij这段中就一个矩阵，需要

19、计算的次数为0；如果ij，则mij=minmik+mk+1j+pi-1XpkXpj,其中k,在i与j之间游荡，所以i=kj ;代码实现时需要注意的问题：计算顺序！因为你要保证在计算mij查找mik和mk+1j的时候，mik和mk+1j已经计算出来了。观察坐标的关系如图：所以计算顺序如上右图：相应的计算顺序对应代码为13-15行m1n即为最终求解，最终的输出想为（A1（A2 A3）（A4 A5）A6）的形式，不过没有成功，待思考矩阵连乘问题动态规划矩阵连乘算法问题：给定n个矩阵A1,A2,.,An，使得n个矩阵的连乘A1A2.An的计算量最小。因为矩阵的乘法满足结合律，所以问题简化为怎么加括号。

20、使用动态规划解决该问题：1.分析最优解的结构（找出最优解的性质，并刻画其结构特征）记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.建立递归关系(递归定义最优值）设计算Ai,j，1=i=j=n，所需的最少数乘次数为mij，则原问题的最优值为m1n。当i=j，mij=0；当ij，mij=min(i=kj)mik+mk+1j+p(i-1)p(k)p(j)最优次序中断开位置k记为sij。3.计算最优值（以自底向上的方式计

21、算出最优值）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循环就是填表的过

22、程，这里的二维数组m就是表格，用来记录已经解决的子问题的答案，不管是不是以后要用到，都记录下来。4.构造最优解（根据计算最优值时得到的信息，构造最优解）表格s中记录了最优解的断开点信息。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;动态规划解最长公共子序列问题2009-05-30 21:2848835人阅读评论(43)收藏举报c算法动态规划法经常会遇到复杂问题不能简单地分解成几

23、个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。【问题】求两字符序列的最长公共字符子序列问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列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的一个子序列。考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，am-1”，B=“b0，b1，bm-1”，并Z=“z0，z1，zk-1”为它们的最长公共子序列。不难证明有以下性质：（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的最长公共子序列。求解：引进一个二维数组c，用cij记录Xi与Yj 的LCS 的长度，bi

26、j记录cij是通过哪一个子问题的值求得的，以决定搜索的方向。我们是自底向上进行递推计算，那么在计算ci,j之前，ci-1j-1，ci-1j与cij-1均已计算出来。此时我们根据Xi = Yj还是Xi != Yj，就可以计算出cij。问题的递归式写成：回溯输出最长公共子序列过程：算法分析：由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为(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;动态规划之最长公共子序列算法 (2009-10-17 00:22:09)标签：杂谈最长公共子序列问题LCS问题描述参考解答动态规划算法可有效地解此问题。下面我们按照动态规划算法设计的各个步骤来设计一

29、个解此问题的有效算法。1.最长公共子序列的结构解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列1, 2, , m的一个子序列，因此，X共有2m个不同子序列，从而穷举搜索法需要指数时间。事实上，最长公共子序列问题也有最优子结构性质，因为我们有如下定理：定理: LCS的最优子结构性质设序列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加在其尾部将产生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.类似。这个定理告诉我们，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。2.子问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm

32、yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递归关系。用ci,j记录序列Xi和Yj的最长公共子序列的长度。其中Xi=，Yj=。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故ci,j=0。

33、其他情况下，由定理可建立递归关系如下：3.计算最优值直接利用(2.2)式容易写出一个计算ci,j的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=和Y=作为输入。输出两个数组c0.m ,0.n和b1.m ,1.n。其中ci,j存储Xi与Yj的最长公共子序列的长度，bi,j记录指示ci,j的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，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;由于每个数组单元的计算耗费(1)时间，算

35、法LCS_LENGTH耗时(mn)。4.构造最长公共子序列由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=和Y=的最长公共子序列。首先从bm,n开始，沿着其中的箭头所指的方向在数组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)实现根据b的内容打印出Xi与Yj的最长公共子序列。通过算法的调用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中，每一次的递归调用使i或j减1，因此算法的计算时间为O(m+n)。例如，设所给的两个序列为X=和Y=。由算法LCS_LENGTH和LCS计算出的结果如图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的计算结果5.算法的改进对于一个具体问题，按照一般的算法设计策略设计出的算法，往往在算法的时间和空间需求上还可以改进。这种改进，通常是利用具体问题的一些特殊性。例如，在算法LCS_LENGTH和LCS中，可进一步将数组b省去。事实上，数组元素ci,

38、j的值仅由ci-1,j-1，ci-1,j和 ci,j-1三个值之一确定，而数组元素bi,j也只是用来指示ci,j究竟由哪个值确定。因此，在算法LCS中，我们可以不借助于数组b而借助于数组c本身临时判断ci,j的值是由ci-1,j-1，ci-1,j和ci,j-1中哪一个数值元素所确定，代价是(1)时间。既然b对于算法LCS不是必要的，那么算法LCS_LENGTH便不必保存它。这一来，可节省(mn)的空间，而LCS_LENGTH和LCS所需要的时间分别仍然是(mn)和(m+n)。不过，由于数组c仍需要(mn)的空间，因此这里所作的改进，只是在空间复杂性的常数因子上的改进。另外，如果只需要计算最长公

39、共子序列的长度，则算法的空间需求还可大大减少。事实上，在计算ci,j时，只用到数组c的第i行和第i-1行。因此，只要用2行的数组空间就可以计算出最长公共子序列的长度。更进一步的分析还可将空间需求减至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