分而治之算法描述

令t (k) 为函数Ti l e B o a r d覆盖一个2k×2k 残缺棋盘所需要的时间。当k= 0时，s i z e等于1，覆盖它将花费常数时间d。当k > 0时，将进行4次递归的函数调用，这些调用需花费的时间为4t (k-1 )。除了这些时间外， if 条件测试和覆盖3个非残缺方格也需要时间，假设用常数c 表示这些额外时间。可以得到以下递归表达式：

程序14-2 覆盖残缺棋盘

void TileBoard(int tr, int tc, int dr, int dc, int size)

{// 覆盖残缺棋盘

if (size == 1) return;

int t = tile++, // 所使用的三格板的数目

s = size/2; // 象限大小

/ /覆盖左上象限

if (dr < tr + s && dc < tc + s)

// 残缺方格位于本象限

Ti l e B o a r d ( t r, tc, dr, dc, s);

else {// 本象限中没有残缺方格

// 把三格板t 放在右下角

Board[tr + s - 1][tc + s - 1] = t;

// 覆盖其余部分

Ti l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);}

/ /覆盖右上象限

if (dr < tr + s && dc >= tc + s)

// 残缺方格位于本象限

Ti l e B o a r d ( t r, tc+s, dr, dc, s);

else {// 本象限中没有残缺方格

// 把三格板t 放在左下角

Board[tr + s - 1][tc + s] = t;

// 覆盖其余部分

Ti l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);}

/ /覆盖左下象限

if (dr >= tr + s && dc < tc + s)

// 残缺方格位于本象限

TileBoard(tr+s, tc, dr, dc, s);

else {// 把三格板t 放在右上角

Board[tr + s][tc + s - 1] = t;

// 覆盖其余部分

TileBoard(tr+s, tc, tr+s, tc+s-1, s);}

// 覆盖右下象限

if (dr >= tr + s && dc >= tc + s)

// 残缺方格位于本象限

TileBoard(tr+s, tc+s, dr, dc, s);

else {// 把三格板t 放在左上角

Board[tr + s][tc + s] = t;

// 覆盖其余部分

TileBoard(tr+s, tc+s, tr+s, tc+s, s);}

}

void OutputBoard(int size)

{

for (int i = 0; i < size; i++) {

for (int j = 0; j < size; j++)

cout << setw (5) << Board[i][j];

cout << endl;

}

}

可以用迭代的方法来计算这个表达式（见例2 - 2 0），可得t (k )= ( 4k )= （所需的三格板的数目）。由于必须花费至少( 1 )的时间来放置每一块三格表，因此不可能得到一个比分而治之算法更快的算法。

2.2.2 归并排序

可以运用分而治之方法来解决排序问题，该问题是将n 个元素排成非递减顺序。分而治之方法通常用以下的步骤来进行排序算法：若n 为1，算法终止；否则，将这一元素集合分割成两个或更多个子集合，对每一个子集合分别排序，然后将排好序的子集合归并为一个集合。

假设仅将n 个元素的集合分成两个子集合。现在需要确定如何进行子集合的划分。一种可能性就是把前面n- 1个元素放到第一个子集中（称为A），最后一个元素放到第二个子集里（称为B）。按照这种方式对A递归地进行排序。由于B仅含一个元素，所以它已经排序完毕，在A排完序后，只需要用程序2 - 1 0中的函数i n s e r t将A和B合并起来。把这种排序算法与I n s e r t i o n S o r t（见程序2 - 1 5）进行比较，可以发现这种排序算法实际上就是插入排序的递归算法。该算法的复杂性为O (n 2 )。把n 个元素划分成两个子集合的另一种方法是将含有最大值的元素放入B，剩下的放入A中。然后A被递归排序。为了合并排序后的A和B，只需要将B添加到A中即可。假如用函数M a x（见程序1 - 3 1）来找出最大元素，这种排序算法实际上就是S e l e c t i o n S o r t（见程序2 - 7）的递归算法。

假如用冒泡过程（见程序2 - 8）来寻找最大元素并把它移到最右边的位置，这种排序算法就是B u b b l e S o r t（见程序2 - 9）的递归算法。这两种递归排序算法的复杂性均为(n2 )。若一旦发现A已经被排好序就终止对A进行递归分割，则算法的复杂性为O(n2 )（见例2 - 1 6和2 - 1 7）。

上述分割方案将n 个元素分成两个极不平衡的集合A和B。A有n- 1个元素，而B仅含一个元素。下面来看一看采用平衡分割法会发生什么情况： A集合中含有n/k 个元素，B中包含其余的元素。递归地使用分而治之方法对A和B进行排序。然后采用一个被称之为归并（ m e rg e）的过程，将已排好序的A和B合并成一个集合。

例2-5 考虑8个元素，值分别为[ 1 0，4，6，3，8，2，5，7 ]。如果选定k = 2，则[ 1 0 , 4 , 6 , 3 ]和[ 8 , 2 , 5 , 7 ]将被分别独立地排序。结果分别为[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。从两个序列的头部开始归并这两个已排序的序列。元素2比3更小，被移到结果序列；3与5进行比较，3被移入结果序列；4与5比较，4被放入结果序列；5和6比较，.。如果选择k= 4，则序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]将被排序。排序结果分别为[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6 , 7 , 8 ]。当这两个排好序的序列被归并后，即可得所需要的排序序列。

图2 - 6给出了分而治之排序算法的伪代码。算法中子集合的数目为2，A中含有n/k个元素。

template<class T>

void sort( T E, int n)

{ / /对E中的n 个元素进行排序， k为全局变量

if (n >= k) {

i = n/k;

j = n-i;

令A 包含E中的前i 个元素

令B 包含E中余下的j 个元素

s o r t ( A , i ) ;

s o r t ( B , j ) ;

m e rge(A,B,E,i,j,); //把A 和B 合并到E

}

else 使用插入排序算法对E 进行排序

}

图14-6 分而治之排序算法的伪代码

 

从对归并过程的简略描述中，可以明显地看出归并n个元素所需要的时间为O (n)。设t (n)为分而治之排序算法（如图1 4 - 6所示）在最坏情况下所需花费的时间，则有以下递推公式：

其中c 和d 为常数。当n / k≈n-n / k 时，t (n) 的值最小。因此当k= 2时，也就是说，当两个子集合所包含的元素个数近似相等时， t (n) 最小，即当所划分的子集合大小接近时，分而治之算法通常具有最佳性能。

可以用迭代方法来计算这一递推方式，结果为t(n)= (nl o gn)。虽然这个结果是在n为2的幂时得到的，但对于所有的n，这一结果也是有效的，因为t(n) 是n 的非递减函数。t(n) =(nl o gn) 给出了归并排序的最好和最坏情况下的复杂性。由于最好和最坏情况下的复杂性是一样的，因此归并排序的平均复杂性为t (n)= (nl o gn)。

图2 - 6中k= 2的排序方法被称为归并排序（ m e rge sort ），或更精确地说是二路归并排序（two-way merge sort）。下面根据图1 4 - 6中k= 2的情况（归并排序）来编写对n 个元素进行排序的C + +函数。一种最简单的方法就是将元素存储在链表中（即作为类c h a i n的成员（程序3 -8））。在这种情况下，通过移到第n/ 2个节点并打断此链，可将E分成两个大致相等的链表。

归并过程应能将两个已排序的链表归并在一起。如果希望把所得到C + +程序与堆排序和插入排序进行性能比较，那么就不能使用链表来实现归并排序，因为后两种排序方法中都没有使用链表。为了能与前面讨论过的排序函数作比较，归并排序函数必须用一个数组a来存储元素集合E，并在a 中返回排序后的元素序列。为此按照下述过程来对图1 4 - 6的伪代码进行细化：当集合E被化分成两个子集合时，可以不必把两个子集合的元素分别复制到A和B中，只需简单地在集合E中保持两个子集合的左右边界即可。接下来对a 中的初始序列进行排序，并将所得到的排序序列归并到一个新数组b中，最后将它们复制到a 中。图1 4 - 6的改进版见图1 4 - 7。

 

template<class T>

M e rgeSort( T a[], int left, int right)

{ / /对a [ l e f t : r i g h t ]中的元素进行排序

if (left < right) {//至少两个元素

int i = (left + right)/2; //中心位置

M e rgeSort(a, left, i);

M e rgeSort(a, i+1, right);

M e rge(a, b, left, i, right); //从a 合并到b

Copy(b, a, left, right); //结果放回a

}

}

图14-7 分而治之排序算法的改进

 

可以从很多方面来改进图1 4 - 7的性能，例如，可以容易地消除递归。如果仔细地检查图1 4 - 7中的程序，就会发现其中的递归只是简单地重复分割元素序列，直到序列的长度变成1为止。当序列的长度变为1时即可进行归并操作，这个过程可以用n 为2的幂来很好地描述。长度为1的序列被归并为长度为2的有序序列；长度为2的序列接着被归并为长度为4的有序序列；这个过程不断地重复直到归并为长度为n 的序列。图1 4 - 8给出n= 8时的归并（和复制）过程，方括号表示一个已排序序列的首和尾。

 

初始序列[8] [4] [5] [6] [2] [1] [7] [3]

归并到b [4 8] [5 6] [1 2] [3 7]

复制到a [4 8] [5 6] [1 2] [3 7]

归并到b [4 5 6 8] [1 2 3 7]

复制到a [4 5 6 8] [1 2 3 7]

归并到b [1 2 3 4 5 6 7 8]

复制到a [1 2 3 4 5 6 7 8]

图14-8 归并排序的例子

 

另一种二路归并排序算法是这样的：首先将每两个相邻的大小为1的子序列归并，然后对上一次归并所得到的大小为2的子序列进行相邻归并，如此反复，直至最后归并到一个序列，归并过程完成。通过轮流地将元素从a 归并到b 并从b 归并到a，可以虚拟地消除复制过程。二路归并排序算法见程序1 4 - 3。

程序14-3 二路归并排序

template<class T>

void MergeSort(T a[], int n)

{// 使用归并排序算法对a[0:n-1] 进行排序

T *b = new T [n];

int s = 1; // 段的大小

while (s < n) {

MergePass(a, b, s, n); // 从a归并到b

s += s;