第四章分治算法 §1.算法基本思想 考虑下面折半搜索算法 程序4-1-1折半搜索 template<class T, int BinarySearch(t al, const T& x, int n W/在数组a[0:n-1]中搜索x,数组中的元素满足a[0]<=a[1] ·<≡a[n-1]。如果找到x,则返回所在位置(数组元素的下标) //否则返回-1 int left=0; int right=n-1 while(left(=right)( int middle=(left+right)/2 if(x==amiddle]) return middle if(x)a middled) left=middle+1 else right=middle -1 return-1;//未找到x while的每次循环(最后一次除外)都将以减半的比例缩小搜索范围,所以, 该循环在最坏的情况下需要执行θ(logn)次。由于每次循环需耗时⊙(1),因此在 最坏情况下,总的时间复杂性为e(logn) 折半搜索算法贯彻一个思想,即分治法。当人们要解决一个输入规模,比 如n,很大的问题时,往往会想到将该问题分解。比如将这n个输入分成k个不 同的子集。如果能得到k个不同的可独立求解的子问题,而且在求出这些子问题 的解之后,还可以找到适当的方法把它们的解合并成整个问题的解,那么复杂的 难以解决的问题就可以得到解决。这种将整个问题分解成若干个小问题来处理的 方法称为分治法。一般来说,被分解出来的子问题应与原问题具有相同的类型, 这样便于采用递归算法。如果得到的子问题相对来说还较大,则再用分治法,直 到产生出不用再分解就可求解的子问题为止。人们考虑和使用较多的是k=2的情
第四章 分 治 算 法 §1. 算法基本思想 考虑下面折半搜索算法 程序 4-1-1 折半搜索 template int BinarySearch(T a[], const T& x, int n) {// 在 数 组 a[0:n-1] 中 搜 索 x ， 数 组 中 的 元 素 满 足 a[0]a[middle]) left=middle+1; else right=middle – 1; } return –1; //未找到 x } while 的每次循环（最后一次除外）都将以减半的比例缩小搜索范围，所以， 该循环在最坏的情况下需要执行Θ(log n)次。由于每次循环需耗时Θ(1) ，因此在 最坏情况下，总的时间复杂性为Θ(log n)。 折半搜索算法贯彻一个思想，即分治法。当人们要解决一个输入规模，比 如 n，很大的问题时，往往会想到将该问题分解。比如将这 n 个输入分成 k 个不 同的子集。如果能得到 k 个不同的可独立求解的子问题，而且在求出这些子问题 的解之后，还可以找到适当的方法把它们的解合并成整个问题的解，那么复杂的 难以解决的问题就可以得到解决。这种将整个问题分解成若干个小问题来处理的 方法称为分治法。一般来说，被分解出来的子问题应与原问题具有相同的类型， 这样便于采用递归算法。如果得到的子问题相对来说还较大，则再用分治法，直 到产生出不用再分解就可求解的子问题为止。人们考虑和使用较多的是 k=2 的情
形,即将整个问题二分。以下用A[l:n来表示n个输入,用DanC(p,q)表示处理 输入为A[p:q]情况的问题。 分治法控制流程 DanC(p, g) globa1n,A[l:n]; integer m,p,q;//1sp≤q≤n if Small(p, g) then return G(p, g) else m=Divide(p, g);// p<m<q return Combine(DanC (p, m), DanC (m+1, g)) endif end danC 这里,Smal1l(p,q)是一个布尔值函数,用以判断输入规模为q-p+1的问题 是否小到无需进一步细分即可容易求解。若是,则调用能直接计算此规模下子问 题解的函数G(p,q).而 Divide(p,q)是分割函数,决定分割点, Combine(x,y) 是解的合成函数。如果假定所分成的两个问题的输入规模大致相等,则DanC总 的计算时间可用下面的递归关系来估计: r(0=g)当输入规模n比较小时,直按求解运算G()的用时 4.1.1) 2T(n/2)+f(m)f(m)是 Combine用时 例4.1.1求n元数组中的最大和最小元素 最容易想到的算法是直接比较算法:将数组的第1个元素分别赋给两个临时 变量:f皿ax=A[l];fmin=A[l];然后从数组的第2个元素A[2]开始直到第n个 元素逐个与fmax和 fmin比较,在每次比较中,如果A[i]〉fmax,则用A[i 的值替换fax的值;如果A[i]<fmin,则用A[i]的值替换fmin的值;否则保 持fmax(fmin)的值不变。这样在程序结束时的fmax、fmin的值就分别是数组 的最大值和最小值。这个算法在最坏情况下,元素的比较次数是2(n-1),而平 均比较次数为3(n-1)/2。 如果采用分治的思想,我们可以给出算法,其时间复杂性在最坏和平均用时 均为3n/2-2
形，即将整个问题二分。以下用 A[1:n]来表示 n 个输入，用 DanC(p,q)表示处理 输入为 A[p:q]情况的问题。 分治法控制流程 DanC(p,q) global n，A[1:n]; integer m,p,q; // 1≤p≤q≤n if Small(p,q) then return G(p,q); else m=Divide(p,q); // p≤m fmax，则用 A[i] 的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保 持 fmax（fmin）的值不变。这样在程序结束时的 fmax、fmin 的值就分别是数组 的最大值和最小值。这个算法在最坏情况下，元素的比较次数是 2(n-1)，而平 均比较次数为 3(n-1)/2。 如果采用分治的思想，我们可以给出算法，其时间复杂性在最坏和平均用时 均为 3n/2-2:
程序4-1-2递归求最大最小值算法伪代码 MaxMin(i,j,fmax,fmin)//A[l:n]是n个元素的数组,参数i,j /是整数,1≤i≤j≤n,使用该过程将数组A[i:j中的最大最小元 //分别赋给fmax和fmin。 global n, A[l: n]: integer i, j: fmax=fmin=A[i]:\\子数组A[i:j中只有一个元素 elseif i=j-1then\\子数组A[i:j中只有两个元素 if Ali]<ALj then fmin=A[i]: fmax=ALj else fmin=A[j]: fmax=ALi] endif else mid(i+j)/2」;\\子数组A[i:j中的元素多于两个 MaxMin(i, mid, gmax, gmin) MaxMin(mid+l, j, hmax, hmin); fmax=max(gmax, hmax) fmin=main(gmin, hmin) endif end Maxmin 如果用T(n)来表示 MaxMin所用的元素比较数,则上述递归算法导出一个 递归关系式: T(n)={1 2 4.1.2 2)+T(n/2b 当n是2的方幂时,设n=2,有 2(2T(n/4)+2) =47(n/4)+4+2 2=7(2) 2k-1+2k-2
程序 4-1-2 递归求最大最小值算法伪代码 MaxMin（i,j,fmax,fmin）//A[1:n]是 n 个元素的数组，参数 i，j //是整数，1≤i≤j≤n，使用该过程将数组 A[i:j]中的最大最小元 //分别赋给 fmax 和 fmin。 global n, A[1:n]; integer i, j; if i=j then fmax=fmin=A[i]; \\子数组 A[i:j]中只有一个元素 elseif i=j-1 then \\子数组 A[i:j]中只有两个元素 if A[i] = = = ( / 2 ) ( / 2 ) 2 2 1 2 0 1 ( ) T n T n n n n T n (4.1.2) 当n是2 的方幂时，设 k n = 2 ，有 3 / 2 2 2 2 2 2 (2) 2 4 ( / 4) 4 2 2(2 ( / 4) 2) 2 ( ) 2 ( / 2) 2 1 1 1 1 = − = + − = + = + + = + + = + − ≤ ≤ − − ∑ n T T n T n T n T n k k i k k i L
无论是最好、最坏、还是平均情况, MaxMin所用的比较数都是3n/2-2,比前面 提到的算法(在最坏情况下)节省了25%的时间。实际上,任何一种以元素比较 为基础的找最大最小元素的算法,其元素比较数的下界是「3n/21-2。从这种意 义上来说, MaxMin算法是最优的。然而,由于需要Logn+1级的递归,每次递 归调用需要将i,j, fmax,fmin和返回地址的值保留到栈中,所以需要多占用 了内存空间。而且由于这些值出入栈时也会带来时间开销,特别当A中元素的比 较次数和整数i与j的比较次数相差无几时,递归求最大最小值算法未必比直接 求最大最小值算法效率高。 例4.1.2.搜索算法的时间下界 分析上节提到的折半搜索算法,我们已经知道其时间复杂度是O(logn) 事实上,我们可以用一个二元比较树来分析折半搜索算法的时间复杂性。以下是 n=9的二元比较树 n=9情况下折半搜索的二元比较树 由图可见,当ⅹ在数组A中时,算法在圆形顶点结束;不在A中时,算法 在方形顶点结束。因为23≤9<24,所以比较树的叶顶点都在4或5级上出现。 因而元素比较的最多次数为4。一般地有:当n∈p22)时,一次成功的折半搜 索至多做k次比较,而一次不成功的折半搜索或者做k-1次比较,或者做k次比 现在假设数组A[1:n满足:A[1]A[2]<…A[n。要搜索元素x是否在 A中。如果只允许进行元素间的比较而不允许对它们进行其它的运算,则所设计
无论是最好、最坏、还是平均情况，MaxMin 所用的比较数都是 3n/2-2，比前面 提到的算法(在最坏情况下)节省了 25％的时间。实际上，任何一种以元素比较 为基础的找最大最小元素的算法，其元素比较数的下界是 3n / 2 − 2 。从这种意 义上来说，MaxMin 算法是最优的。然而，由于需要log n +1级的递归，每次递 归调用需要将 i，j，fmax，fmin 和返回地址的值保留到栈中，所以需要多占用 了内存空间。而且由于这些值出入栈时也会带来时间开销，特别当 A 中元素的比 较次数和整数i与j 的比较次数相差无几时，递归求最大最小值算法未必比直接 求最大最小值算法效率高。 例 4.1.2．搜索算法的时间下界 分析上节提到的折半搜索算法，我们已经知道其时间复杂度是O(log n) 。 事实上，我们可以用一个二元比较树来分析折半搜索算法的时间复杂性。以下是 n=9 的二元比较树： n＝9 情况下折半搜索的二元比较树 由图可见，当 x 在数组 A 中时，算法在圆形顶点结束；不在 A 中时，算法 在方形顶点结束。因为 3 4 2 ≤ 9 < 2 ，所以比较树的叶顶点都在4或5 级上出现。 因而元素比较的最多次数为 4。一般地有：当 [ ) k k n 2 ,2 −1 ∈ 时，一次成功的折半搜 索至多做 k 次比较，而一次不成功的折半搜索或者做 k-1 次比较，或者做 k 次比 较。 现在假设数组 A[1:n]满足：A[1]< A[2]< …< A[n]。要搜索元素 x 是否在 A 中。如果只允许进行元素间的比较而不允许对它们进行其它的运算，则所设计 4 9 5 7 1 3 6 8 2
的算法称为以比较为基础的算法。任何以比较为基础的搜索算法的执行过程都可 以用一棵二元比较树来描述。每次可能的比较用一个内顶点表示,对应于不成功 的结果有一个外顶点(叶顶点)与之对应。线性搜索和折半搜索的二元比较树如 下 All 不成功 A[2 不成功 In 图4-1-1模拟线性搜索过程 不成功 不成功 x:AL(n+1)2 A(n+)2 A(n+1)y2 A|x:Ad(+12](x:A(m+/2H1 x: An 不成功不成功不成功 不成功不成功 不成功不成功不成功 图4-1-2模拟折半搜索过程 定理4.1.1设数组A[1:n]的元素满足A[1]<A[2]<…<A[n]。则以比较为 基础,判断x∈A[1:n]的任何算法,在最坏情况下所需的最少比较次数 Find(n) 不小于1og(n+1) 证明通过考察模拟求解搜索问题的各种可能算法的比较树可知,Find(n) 不大于树中由根到一个叶子的最长路径的距离。也就是说,在最坏情况下每种搜 索算法的比较次数都是比较树中由根到叶顶点的最长距离。在所有的树中,这个
的算法称为以比较为基础的算法。任何以比较为基础的搜索算法的执行过程都可 以用一棵二元比较树来描述。每次可能的比较用一个内顶点表示，对应于不成功 的结果有一个外顶点（叶顶点）与之对应。线性搜索和折半搜索的二元比较树如 下： 图 4-1-1 模拟线性搜索过程 . . . . . . 图 4-1-2 模拟折半搜索过程 定理 4.1.1 设数组 A[1:n]的元素满足 A[1]< A[2]< …< A[n]。则以比较为 基础，判断 x ∈ A[1: n]的任何算法，在最坏情况下所需的最少比较次数 Find(n) 不小于log(n+1). 证明 通过考察模拟求解搜索问题的各种可能算法的比较树可知，Find(n) 不大于树中由根到一个叶子的最长路径的距离。也就是说，在最坏情况下每种搜 索算法的比较次数都是比较树中由根到叶顶点的最长距离。在所有的树中，这个 x:A[1] x:A[2] x:A[n] 不成功 不成功 不成功 不成功 x:A[(n+1)/2] x:A[(n+1)/2] x:A[1] x:A[(n+1)/2-1] x:A[(n+1)/2] x:A[(n+1)/2+1] x:A[n] 不成功 不成功 不成功 不成功 不成功 不成功 不成功 不成功
最长距离以完全二叉树的最短。对于每个二叉比较树,必有n个内顶点与x在A 中的n种可能的情况相对应。如果一棵二叉树的所有内顶点所在的级数小于或等 于级数k,则最多有2k-1个内顶点。因此n≤2*-1,即Find(n)=k2log(n+1)1。 证毕 由定理可见,任何一种以比较为基础的算法,其最坏情况下的所用时间不可 能低于(logm)。因此,也就不可能存在其最坏情况下时间比折半搜索数量级 (阶)还低的算法。事实上,折半搜索所产生的比较树的所有外部顶点都在相邻 的两个级上,而且这样的二叉树使得由根到叶顶点的最长路径减至最小,因此 折半搜索是解决搜索问题在最坏情况下的最优算法, §2关于排序算法 问题:已知n个元素的数组A[1:n],将A中元素按不降顺序排列。 归并排序算法 程序4-2-1向有序数组插入元素 程序4-2-2插入排序 template template=0&&x<a[i];i--) Insert(a a[i+1]=a[i] [i+1]=x; n++;//添加了一个元素 将上述两个算法合并在一起,得到下述插入排序算法 程序4-2-3插入排序算法伪代码 Insert Sort(A,n)//将A[l:n]中的元素按非降次序排列,n≥1 A[0]=-∞//生成一个虚拟值 for j from2 to n do//A[1:j1]已经排序
最长距离以完全二叉树的最短。对于每个二叉比较树，必有 n 个内顶点与x在A 中的 n 种可能的情况相对应。如果一棵二叉树的所有内顶点所在的级数小于或等 于级数 k，则最多有2 −1 k 个内顶点。因此 ≤ 2 −1 k n ，即 Find(n)=k≥log(n+1)。 证毕 由定理可见，任何一种以比较为基础的算法，其最坏情况下的所用时间不可 能低于Θ(logn)。因此，也就不可能存在其最坏情况下时间比折半搜索数量级 （阶）还低的算法。事实上，折半搜索所产生的比较树的所有外部顶点都在相邻 的两个级上，而且这样的二叉树使得由根到叶顶点的最长路径减至最小，因此， 折半搜索是解决搜索问题在最坏情况下的最优算法。 §2.关于排序算法 问题：已知 n 个元素的数组 A[1:n]，将 A 中元素按不降顺序排列。 z 归并排序算法 程序 4-2-1 向有序数组插入元素 程序 4-2-2 插入排序 template template void Insert(T a[], int& n, const T& x) void InsertionSort(T a[], int n) {//向数组 a[0:n-1]中插入元素 x {//对 a[0:n-1]进行排序 //假定 a 的大小超过 n for(int i=1; i=0 && x<a[i]; i--) Insert(a, i, t); a[i+1]=a[i]; } a[i+1]=x; } n++; //添加了一个元素 } 将上述两个算法合并在一起，得到下述插入排序算法： 程序 4-2-3 插入排序算法伪代码 InsertSort (A,n) //将 A[1:n]中的元素按非降次序排列，n≥1 A[0]=−∞ //生成一个虚拟值 for j from 2 to n do // A[1:j-1]已经排序
item=A[j]: i=j-1 while item<ALi] do//0si<j A[i+1]=A[i];i=i-1 endwhile end InsertSort while循环中的语句可能执行j次(j=2,…,n),因此最坏情况的时间限界是 j=(n(n+1)/2)-1=6(n2) 在这个算法中,大部分的时间都用在挪动元素上,随着已经排好顺序的数组 的增长,被挪动的元素的个数也在增加,而且在整个过程中,很多元素不止一次 被挪动。以下程序从某种程度上减少了这种浪费。这一算法的基本思想是采用, 分治的方法,将要排序的数组分成两部分,先对每部分进行排序,然后再将两部 分已经排好序的子数组的元素按照从小到大的顺序交替地摆放在一个新的数组 中。这一过程也许需要多次分解和组合,因而是一个递归过程。 程序4-2-4归并排序主程序伪代码 MergeSort(low,high)//A[low:high]是一个全程数组,含有 //high-low+1个待排序的元素 integer low, high if low high the mid=L(low+high)/2」//求当前数组的分割点 MergeSort(low,mid)//将第一子数组排序 MergeSort(mid+1,high)/将第二子数组排序 Merge(loW,mid,high)//归并两个已经排序的子数组 endif end MergeSort 这里我们使用了辅助程序 Merge 程序4-2-5合并过程伪代码 Merge(loW,mid,high)//已知全程数组A[low:high],其由两部分已经排
item=A[j]; i=j−1; while item<A[i] do // 0≤i<j A[i+1]=A[i]; i=i−1; endwhile A[i+1]=item; endfor end InsertSort while 循环中的语句可能执行 j 次（j=2,…,n）,因此最坏情况的时间限界是 ( ( 1)/ 2) 1 ( ) 2 2 j n n n j n ∑ = + − = Θ ≤ ≤ 在这个算法中，大部分的时间都用在挪动元素上，随着已经排好顺序的数组 的增长，被挪动的元素的个数也在增加，而且在整个过程中，很多元素不止一次 被挪动。以下程序从某种程度上减少了这种浪费。这一算法的基本思想是采用， 分治的方法，将要排序的数组分成两部分，先对每部分进行排序，然后再将两部 分已经排好序的子数组的元素按照从小到大的顺序交替地摆放在一个新的数组 中。这一过程也许需要多次分解和组合，因而是一个递归过程。 程序 4－2－4 归并排序主程序伪代码 MergeSort(low, high) // A[low : high]是一个全程数组，含有 // high-low+1 个待排序的元素。 integer low, high; if low < high then mid = (low+high)/2 //求当前数组的分割点 MergeSort(low, mid) //将第一子数组排序 MergeSort(mid+1, high) //将第二子数组排序 Merge(low, mid, high) //归并两个已经排序的子数组 endif end MergeSort 这里我们使用了辅助程序 Merge: 程序 4-2-5 合并过程伪代码 Merge(low, mid, high) //已知全程数组 A[low : high], 其由两部分已经排
好序的子数组构成:A[low:mid]和A[mid+1:high]。本程序的任务 \\是将这两部分子数组合并成一个整体排好序的数组,再存于数组 A\ALlow: high integer h, 1, j, k, low, mid, high; global A[low:high];1 ocal B[low:high];/借用临时数组B h=low;i=low;jmid+1;//h,j是拣取游标,i是存放游标 while hamid&& jshigh do//当两个集合都没有取尽时 if Ath]sALj then bli]=A[h]: h=h+1 else Bli]=ALj]: j=j+1 i=i+1 endwhile if h>mid then\\当第一子组元素被取尽,而第二组元素未被取尽时 for k from j to high do ;i=i+1 endfor else for k from h to mid do 当第二子组元素被取尽,而第一组元素未被取尽时 B[i]=A[k];i=i+1 endo endif for k from low to high do\将临时数组中元素再赋给数组A ALk]=blk] endfor end Merge 可见,归并排序由分解与合并两部分组成,整个过程可用两棵树表示出来(参 见文档“归并排序树”)。 如果用T(n)表示归并排序所用的时间,并假定合并过程所用时间与n成正比
\\好序的子数组构成：A[low : mid]和 A[mid+1 : high]。本程序的任务 \\是将这两部分子数组合并成一个整体排好序的数组， 再存于数组 \\A[low : high]. integer h, i, j, k, low, mid, high; global A[low : high]; local B[low : high]; //借用临时数组 B h=low; i=low; j=mid+1; // h, j 是拣取游标, i 是存放游标 while h≤mid && j≤high do //当两个集合都没有取尽时 if A[h]≤A[j] then B[i]=A[h]; h=h+1; else B[i]=A[j]; j=j+1; endif i＝i+1; endwhile if h>mid then \\ 当第一子组元素被取尽，而第二组元素未被取尽时 for k from j to high do B[i]=A[k]; i=i+1; endfor else for k from h to mid do \\ 当第二子组元素被取尽，而第一组元素未被取尽时 B[i]=A[k]; i=i+1; endfor endif for k from low to high do \\将临时数组中元素再赋给数组 A A[k]=B[k]; endfor end Merge 可见，归并排序由分解与合并两部分组成，整个过程可用两棵树表示出来（参 见文档“归并排序树”）。 如果用 T(n)表示归并排序所用的时间，并假定合并过程所用时间与 n 成正比：
cn,其中c是一个正数,则有 T(n)= (4.2.1) 2T(n/2)+Cnn>1 其中,a是一个常数。若n是2的方幂:n=2,直接推导可得 T(n)=2(27(n/4)+cn/2)+cmn 47(n/4)+2cn 2 T(1)+kcn an +cn log n 对于一般的整数n,我们可以假定24(n/2-1log(n/2)=O(nlog n) 从上式看出,归并排序是时间复杂性级别最低的排序算法(以比较为基础)
cn，其中 c 是一个正数，则有 + > = = 2 ( / 2) 1 1 ( ) T n cn n a n T n (4.2.1) 其中，a 是一个常数。若n是2 的方幂： k n = 2 ，直接推导可得 an cn n T kcn T n cn T n T n cn cn k log 2 (1) 4 ( / 4) 2 ( ) 2(2 ( / 4) / 2) = + = + = + = + + LL 对于一般的整数 n，我们可以假定 1 2 2 + < ≤ k k n ，于是 ( ) (2 ) +1 ≤ k T n T ，得 T(n) = O(n log n) 。 z 以比较为基础的排序时间的下界 类似于估计搜索算法的时间下界，我们也可以用树来模拟排序算法，在此我 们考虑最坏情况下的时间下限，并假定数组中的元素互不相同。在树的内部顶点 上，算法执行一次比较，并根据比较的结果移向它的某一个孩子。由于每两个元 素 A[i]和 A[j]的比较只有两种可能：A[i]<A[j]或 A[j]<A[i]，所以这颗树是二 叉树。当 A[i]<A[j]时进入左分支，当 A[j]<A[i]进入右分支。各个外部顶点（叶 顶点）表示算法终止。从根到外顶点的每一条路径与一种唯一的排列相对应。由 于 n 个不同元素的不同排列共有 n！个，因此比较树至多有 n！个外部顶点（参 看文档“排序比较树”）。直接观察可知，由根到外顶点路径即描述了该外顶点所 代表的排列生成过程，路径的长度即是经历的比较次数。因此，比较树中最长路 径的长度（其是比较树的高）即是算法在最坏情况下所做的比较次数。要求出所 有以比较为基础的排序算法在最坏情况的时间下界，只需求出这些算法所对应的 比较树的最小高度。如果比较树的高是 k，则该二叉树的外顶点至多是 k 2 个。于 是，最坏情况下的最少比较次数 T(n)满足 ( ) ! 2T n n ≤ 。注意到 / 2 1 ! ( 1) ( / 2 ) ( / 2) − ≥ − ≥ n n n n L n n 因而 T(n) ≥ (n / 2 −1)log(n / 2) = Θ(n log n) 从上式看出，归并排序是时间复杂性级别最低的排序算法（以比较为基础）
然而,仔细观察可以发现,归并排序有两个地方值得商榷:一是分解直到只有 个元素。事实上,当元素比较少时,直接进行排序,比如用插入排序算法,比起 进一步分拆、合并排序要快得多。因为,在这种情况下,大量的时间都花在调用 分解、合并函数上。所以,在归并排序算法中,对于归并起点的规模应该有适当 的限制,即加 Small(p,q)判断。二是辅助数组B的借用,虽然不可避免,但应 该采用另一种方式,以避免数组A中的元素的频繁换位。为此,我们可以采用链 表,将数组A中的元素位置变动转化成链表值的变化。 程序4-2-6使用链接表的归并排序算法 MergeSort(1oW,high,p)//Link是全程数组A[low:high]的 //下标表,p指示这个表的开始处。利用Link将A按非 /降顺序排列。 global ALlow: high]: Link [low: high]: if high-low+1<l6then//设定子问题的最小规模 Small InsertSort(A, Link, low, high, p) else mid=(low+high)/2] MergeSort(1oW,mid,q);//返回q表 MergeSort(mid+1,high,r);//返回r表 MergeL(q,r,p);将表q和r合并成表p endif end Merge SortL 其中,合并程序 Mergel是合并函数 Merge的改进 程序4-2-7使用连接表的合并程序 MergeL(q,r,p)//由链接表q和r构造新的连接表p。q、r是全程数组 Link[1:n]中两个表指针,这两个链表指出被划分的两个子组的地址排 \\序,而p指针指出两组归并后的地址排序。实际上都是表的相互顺序 \在变 global n, ALl: n], Link [O: n]: local integer i, j, k i=q;j=r;k=0;//初始化,新表在Link[0]处开始 while i≠0&&j≠0do//当两个表皆非空时
然而，仔细观察可以发现，归并排序有两个地方值得商榷：一是分解直到只有一 个元素。事实上，当元素比较少时，直接进行排序，比如用插入排序算法，比起 进一步分拆、合并排序要快得多。因为，在这种情况下，大量的时间都花在调用 分解、合并函数上。所以，在归并排序算法中，对于归并起点的规模应该有适当 的限制，即加 Small(p,q)判断。二是辅助数组 B 的借用，虽然不可避免，但应 该采用另一种方式，以避免数组 A 中的元素的频繁换位。为此，我们可以采用链 表，将数组 A 中的元素位置变动转化成链表值的变化。 程序 4-2-6 使用链接表的归并排序算法 MergeSortL(low, high, p) // Link 是全程数组 A[low:high]的 //下标表, p 指示这个表的开始处。利用 Link 将 A 按非 //降顺序排列。 global A[low:high]; Link[low:high]; if high-low+1<16 then //设定子问题的最小规模 Small InsertSort(A,Link, low,high,p)； else mid=(low+high)/2； MergeSortL(low,mid,q); //返回 q 表 MergeSortL(mid+1,high,r); //返回 r 表 MergeL(q,r,p); 将表q和r 合并成表 p endif end MergeSortL 其中，合并程序 MergeL 是合并函数 Merge 的改进： 程序 4-2-7 使用连接表的合并程序 MergeL(q,r,p) // 由链接表q和r 构造新的连接表 p。q、r 是全程数组 \\Link[1:n]中两个表指针，这两个链表指出被划分的两个子组的地址排 \\序， 而 p 指针指出两组归并后的地址排序。实际上都是表的相互顺序 \\在变。. global n,A[1：n], Link[0:n]; local integer i, j, k; i=q; j=r; k=0; // 初始化，新表在 Link[0]处开始 while i≠0 && j≠0 do //当两个表皆非空时