分而治之算法描述

Y[i].p = i;

Y[i].x = X[i].x;

Y[i].y = X[i].y;

}

M e r g e S o r t ( Y,n); // 按y坐标排序

// 创建临时数组

Point2 *Z = new Point2 [n];

// 寻找最近点对

c l o s e ( X , Y, Z , 0 , n - 1 , a , b , d ) ;

// 删除数组并返回

delete [] Y;

delete [] Z;

return true;

}

程序1 4 - 11 计算最近点对

void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1& a, Point1& b, float& d)

{//X[l:r] 按x坐标排序

//Y[l:r] 按y坐标排序

if (r-l == 1) {// 两个点

a = X[l];

b = X[r];

d = dist(X[l], X[r]);

r e t u r n ; }

if (r-l == 2) {// 三个点

// 计算所有点对之间的距离

float d1 = dist(X[l], X[l+1]);

float d2 = dist(X[l+1], X[r]);

float d3 = dist(X[l], X[r]);

// 寻找最近点对

if (d1 <= d2 && d1 <= d3) {

a = X[l];

b = X[l+1];

d = d1;

r e t u r n ; }

if (d2 <= d3) {a = X[l+1];

b = X[r];

d = d2;}

else {a = X[l];

b = X[r];

d = d3;}

r e t u r n ; }

/ /多于三个点，划分为两部分

int m = (l+r)/2; // X[l:m] 在A中，余下的在B中

// 在Z[l:m] 和Z [ m + 1 : r ]中创建按y排序的表

int f = l, // Z[l:m]的游标

g = m+1; // Z[m+1:r]的游标

for (int i = l; i <= r; i++)

if (Y[i].p > m) Z[g++] = Y[i];

else Z[f++] = Y[i];

// 对以上两个部分进行求解

c l o s e ( X , Z , Y, l , m , a , b , d ) ;

float dr;

Point1 ar, br;

c l o s e ( X , Z , Y, m + 1 , r, a r, b r, d r ) ;

// (a,b) 是两者中较近的点对

if (dr < d) {a = ar;

b = br;

d = dr;}

M e r g e ( Z , Y,l,m,r);// 重构Y

/ /距离小于d的点放入Z

int k = l; // Z的游标

for (i = l; i <= r; i++)

if (fabs(Y[m].x - Y[i].x) < d) Z[k++] = Y[i];

// 通过检查Z [ l : k - 1 ]中的所有点对，寻找较近的点对

for (i = l; i < k; i++){

for (int j = i+1; j < k && Z[j].y - Z[i].y < d;

j + + ) {

float dp = dist(Z[i], Z[j]);

if (dp < d) {// 较近的点对

d = dp;

a = X[Z[i].p];

b = X[Z[j].p];}

}

}

}

函数c l o s e（见程序1 4 - 11）用来确定X[1:r] 中的最近点对。假定这些点按x 坐标排序。在Y [ 1 : r ]中对这些点按y 坐标排序。Z[ 1 : r ]用来存放中间结果。找到最近点对以后，将在a, b中返回最近点对，在d 中返回距离，数组Y被恢复为输入状态。函数并未修改数组X。

首先考察“小问题”，即少于四个点的点集。因为分割过程不会产生少于两点的数组，因此只需要处理两点和三点的情形。对于这两种情形，可以尝试所有的可能性。当点数超过三个时，通过计算m = ( 1 + r ) / 2把点集分为两组A和B，X [ 1 : m ]属于A，X [ m + 1 : r ]属于B。通过从左至右扫描Y中的点以及确定哪些点属于A，哪些点属于B，可以创建分别与A组和B组对应的，按y 坐标排序的Z [ 1 : m ]和Z [ m + 1 : r ]。此时Y和Z的角色互相交换，依次执行两个递归调用来获取A和B中的最近点对。在两次递归调用返回后，必须保证Z不发生改变，但对Y则无此要求。不过，仅Y [ l : r ]可能会发生改变。通过合并操作（见程序1 4 - 5）可以以Z [ 1 : r ]重构Y [ 1 : r ]。

为实现图1 4 - 1 6的策略，首先扫描Y [ 1 : r ]，并收集距分割线小于的点，将这些点存放在Z [ 1 : k - 1 ]中。可按如下两种方式来把RA中点p 与p 的比较区内的所有点进行配对：1) 与RB 中y 坐标≥p.y 的点配对；2) 与y 坐标≤p.y 的点配对。这可以通过将每个点Z [ i ]（1≤i < k，不管该点是在RA

还是在RB中）与Z[j] 配对来实现，其中i＜j 且Z [ j ] . y - Z [ i ] . y＜ 。对每一个Z [ i ]，在2 × 区域内所检查的点如图1 4 - 1 7所示。由于在每个2 × 子区域内的点至少相距。因此每一个子区域中的点数不会超过四个，所以与Z [ i ]配对的点Z [ j ]最多有七个。

2. 复杂性分析

令t (n) 代表处理n 个点时，函数close 所需要的时间。当n＜4时，t (n) 等于某个常数d。当n≥4时，需花费(n) 时间来完成以下工作：将点集划分为两个部分，两次递归调用后重构Y，淘汰距分割线很远的点，寻找更好的第三类点对。两次递归调用需分别耗时t (「n /2ù」和t (?n /2?).

这个递归式与归并排序的递归式完全一样，其结果为t (n) = (nl o gn)。另外，函数c l o s e s t还需耗时(nl o gn)来完成如下额外工作：对X进行排序，创建Y和Z，对Y进行排序。因此分而治之最近点对求解算法的时间复杂性为(nl o gn)。

练习

8. 编写一个完整的残缺棋盘问题的求解程序，提供以下模块：欢迎用户使用本程序、输入棋盘大小和残缺方格的位置、输出覆盖后的棋盘。输出棋盘时要着色，共享同一边界的覆盖应着不同的颜色。由于棋盘是平面图，所以最多只需用四种颜色便可为整个棋盘着色。在本练习中，应尽量使用较少的颜色。

9. 用迭代方法求解公式（1 4 - 7）的递归式。

10. 编写一个归并排序程序，要求用链表来存储元素。输出结果为排序后的链表。把函数做为C h a i n类（见程序3 - 8）的一个成员函数。

11. 编写函数N a t u r a l M e rgeSort 来实现自然归并排序。其中输入和输出的规定与程序1 4 - 3相同。

12. 编写一个自然归并排序函数，用来对链表元素进行排序。把函数设计为C h a i n类的一个成员(见程序3 - 8 )。

13. 用一个w h i l e循环来替换程序1 4 - 6中的最后一个递归调用q u i c k S o r t。比较修改后的函数与程序1 4 - 6的平均运行时间。

14. 重写程序1 4 - 6，使用堆栈来模拟递归。堆栈中只需保存l e f t和r i g h t中较小者的边界。

1) 证明所需要的栈空间大小为O ( l o gn)。

2) 比较程序1 4 - 6和新代码的平均运行时间。

15. 证明在最坏情况下Q u i c k S o r t的运行时间为( n2)。

16. 假定在划分l e f t、middle 和right 时按照如下方式来进行：若n为奇数，则l e f t与r i g h t的大小相同；若n为偶数，则l e f t比r i g h t多一个元素。证明在这种假设条件下，程序1 4 - 6的时间复杂性为(nl o gn)。

17. 证明，并利用该结果证明。

18. 试比较使用“中间的中间”规则与不使用该规则时，程序1 4 - 6的最坏复杂性和平均复杂性。取n=10, 20, ., 100, 200, 300, 400, 500, 1000及适当的测试数据来进行比较。

19. 采用随机产生的数作为支点元素完成练习1 8。

20. 在1 4 . 2 . 3节快速排序结束时，我们曾建议将快速排序与插入排序进行结合，结合后的算法实质上仍是快速排序，只是当排序部分小于等于C h a n g e O v e r = n B r e a k时执行插入排序。能否通过改变C h a n g e O v e r而得到更快的算法?为什么?试试不同的C h a n g e O v e r。确定能提供最佳平均性能的C h a n g e O v e r。

21. 设计一个在最差情况下性能最好的排序算法。

1) 比较插入排序、冒泡排序、选择排序、堆排序、归并排序和快速排序在最坏情况下的运行时间。导致插入排序、冒泡排序、选择排序和快速排序出现最坏复杂性的输入数据很容易产生。试编写一个程序，用来产生导致归并排序出现最坏复杂性的输入数据。这个程序本质上是将n 个排好序的元素“反归并”。对于堆排序，用随机产生的输入序列来估算最坏情况下的时间复杂性。

2) 利用1) 中的结果设计一个混合排序函数，使其在最坏情况下具有最佳性能。比如混合函数可以只包含归并排序和插入排序。

3) 测试混合排序函数在最坏情况下的运行时间，并与原排序函数进行比较。

4) 用一个简单的图表来列出七种排序函数在最差情况下的运行时间。

22. 当n 是2幂时，用迭代方法求解公式1 4 - 8。

*23. 证明定理1 4 - 2。

*24. 用归纳法证明，对于公式（1 4 - 11），当n≥1时有t (n)≤7 2c n。

25. 程序1 4 - 7所需要的递归栈空间为O ( n )。当用一个w h i l e或f o r循环来代替递归调用时，可以完全消除这种递归栈空间。根据这种思想重写程序1 4 - 7。比较这两种选择排序函数的运行时间。

26. 重写程序1 4 - 7，用随机数产生器来选择支点元素。试比较这两种代码的平均性能。

27. 重写程序1 4 - 7，使用“中间的中间”规则，其中r = 9。

28. 为了加快程序1 4 - 11的执行速度，可以不执行距离计算公式中的开方运算，而直接用距离的平方来代替距离，所得结果是一样的。为此，程序1 4 - 11必须做哪些改变? 试通过实验来比较这两种版本的性能。

29. 重写程序1 4 - 11，把P o i n t 1作为模板类，其中I D域的类型由用户来决定。

30. 当所有点都在一条直线上时，编写一个更快的算法来寻找最近的点对。例如，假设所有点都在一条水平线上。如果这些点根据x 坐标排序，则最近点对中的两个点必相邻。虽然使用M e rg e S o r t（见程序1 4 - 3）来实现这种策略时，算法的复杂性仍然是O(nl o gn)，但这种算法的额外开销要比程序1 4 - 1 0小得多，因此会运行得更快。

31. 考察最近点对问题。假设初始时不是根据x 坐标来排序，而是使用Selcet (见程序1 4 - 7 )来寻找中点xi ，以便将点集划分为A组和B组。

1) 给出按这种思想实现的最近点