第3章
分 治 算 法
学习目标
掌握分治算法的基本思想和求解步骤；
理解分治算法的精髓，即如何分？如何治？才能使得算法效率更高；
通过实例学习，能够运用分治策略设计解决实际问题的算法并编程实现。
凡治众如治寡，分数是也。
——《孙子兵法》
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关： 问题的规模越小，越容易直接求解，所需的计算时间也就越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算； n=2时，只要做一次比较即可排好序； n=3时只要做3次比较即可，当n较大时，问题就不那么容易处理了。可见，要想直接解决一个规模较大的问题，有时是很困难的。为了更好地解决这些规模较大的问题，分治算法应运而生。
在计算机科学中，分治算法是一种很重要的算法。它采取各个击破的技巧解决一个规模较大的问题，该技巧是很多高效算法的基础，如排序算法(快速排序、归并排序)、傅里叶变换(快速傅里叶变换)等。
微课视频
3.1分治算法概述
3.1.1分治算法的基本思想
分治算法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同子问题，再把子问题分成更小的子问题，直到最后各个子问题可以简单地直接求解，对各个子问题的解进行合并即得原问题的解。
可见，分治算法的基本思想是将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各个击破，分而治之。
那么，何时能、何时应该采用分治算法解决问题呢？即分治算法所能解决的问题应该具备哪些特征？从许多可以用分治算法求解的问题中，总结出这些问题一般具有以下几个特征：
（1） 问题的规模缩小到一定程度就可以容易地解决。
（2） 问题可以分解为若干个规模较小的相同子问题。
（3） 问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
（4） 问题分解出的子问题的解可以合并为原问题的解。
上述的第（1）条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般随着问题规模的增大而增加； 第（2）条特征是应用分治算法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用； 第（3）条特征涉及分治算法的效率，如果各个子问题是不独立的，则分治算法要做许多不必要的工作——重复求解公共的子问题； 第（4）条特征是关键，能否利用分治算法完全取决于问题是否具有第（4）条特征。
3.1.2分治算法的解题步骤
通常，分治算法的求解过程都要遵循两大步骤： 分解和治理。
步骤1： 分解。
既然是分治算法，当然要对待求解问题进行分解，即将问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
那么，究竟该如何合理地对问题进行分解呢？应把原问题分解为多少个子问题才较适宜？每个子问题是否规模相同才为适当？这些问题很难给予肯定的回答。人们从大量的实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分为大小相等的k个子问题（通常k=2），这种处理方法行之有效。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。也有k=1的划分，这仍然是把问题划分为两部分，取其中的一部分，而丢弃另一部分，例如二分查找问题在采用分治算法求解时就是这样划分的。
步骤2： 治理。
步骤21： 求解各个子问题。若子问题规模较小而容易被解决则直接求解，否则再继续分解为更小的子问题，直到容易解决为止。
那么，如何对各个子问题进行求解呢？由于采用分治法求解的问题被分解为若干个规模较小的相同子问题，各个子问题的解法与原问题的解法是相同的。因此，很自然想到采取递归技术来对各个子问题进行求解。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而规模不断缩小，最终使子问题缩小到很容易求解的规模，这导致递归过程的产生。分治与递归就像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。有时候，递归处理也可以采用循环来实现。
步骤22： 合并。它是将已求得的各个子问题的解合并为原问题的解。
合并这一步对分治算法的算法性能至关重要，算法的有效性在很大程度上依赖于合并步的实现，因情况的不同合并的代价也有所不同。
下面通过几个实例具体讲述分治算法求解问题的具体过程。
3.2二分查找
1. 问题描述
二分查找又称为折半查找，它要求待查找的数据元素必须是按关键字大小有序排列的。问题描述： 给定已排好序的n个元素s1,s2,…,sn，现要在这n个元素中找出一特定元素x。
首先较容易想到使用顺序查找方法，逐个比较s1,s2,…,sn，直至找出元素x或搜索整个序列后确定x不在其中。显然，该方法没有很好地利用n个元素已排好序这个条件。因此，在最坏情况下，顺序查找方法需要n次比较。
2. 算法思想及设计
该算法的思想是： 假定元素序列已经由小到大排好序，将有序序列分成规模大致相等的两部分，然后取中间元素与特定查找元素x进行比较，如果x等于中间元素，则算法终止； 如果x小于中间元素，则在序列的左半部继续查找，即在序列的左半部重复分解和治理操作； 否则，在序列的右半部继续查找，即在序列的右半部重复分解和治理操作。可见，二分查找算法重复利用了元素间的次序关系。
算法的求解步骤设计如下：
步骤1： 确定合适的数据结构。设置数组s［n］来存放n个已排好序的元素； 变量low和high分别表示查找范围在数组中的下界和上界； middle表示查找范围的中间位置； x为特定元素。
步骤2： 初始化。令low=0，即指示s中第一个元素； high=n-1，即指示s中最后一个元素。
步骤3： middle=(low+high)/2，即指示查找范围的中间元素。
步骤4： 判定low≤high是否成立，如果成立，转步骤5； 否则，算法结束。
步骤5： 判断x与s［middle］的关系。如果x等于s［middle］，算法结束； 如果x>s［middle］，则令low=middle+1； 否则令high=middle-1，转到步骤3。
3. 二分查找算法的构造实例
【例31】用二分查找算法在有序序列［612151822252835465860］中查找元素12。假定该有序序列存放在一维数组s［11］中。
步骤1： 令low=0，high=10。计算middle=(0+10)/2=5，即利用中间位置middle将序列一分为二，如图31所示。
步骤2： 将x与s［middle］进行比较。此时x<s［middle］，说明x可能位于序列的左半部，即查找范围变为s［0： middle-1］。令high=middle-1=4。
步骤3： 计算middle=(0+4)/2=2，利用此时的中间位置middle=2将子序列［612151822］一分为二，如图32所示。
图31第一次划分示意图
图32第二次划分示意图
步骤4： 将x与s［middle］进行比较。此时x<s［middle］，说明x可能位于子序列s［0： middle-1］中。令high=middle-1=1。
步骤5： 重新计算middle=(0+1)/2=0。利用此时的中间位置middle=0将子序列［612］一分为二，如图33所示。
步骤6： 将x与s［middle］进行比较。此时x>s［middle］，说明x可能位于s［middle +1： high］中。令low=middle+1=1。
步骤7： 计算middle=(1+1)/2=1，如图34所示。
图33第三次划分示意图
图34第四次划分示意图
此时x=s［middle］=12，查找成功。
4. 算法描述
二分查找算法的思想易于理解，但要写一个正确的二分查找算法并不是一件简单的事情。Knuth在他的著作The Art of Com
puter Programming:Sorting and Searching中提到，第一个二分查找算法早在1946年就出现了，但直到1962年第一个完全正确的二分查找算法才出现。
本书给出了该算法的两种描述形式。其中，数组s［n］、变量low、high、middle的含义与求解步骤中的含义相同。
（1） 二分查找算法实现的非递归形式。
int NBinarySearch(int n,int s［n］,int x)
{int low=0,high=n-1;
while(low<=high)
{int middle=(low+high)/2;
if(x==s［middle］)return middle;
else if(x>s［middle］) low=middle+1;
else high=middle-1;
}
return -1;
}
（2） 二分查找算法实现的递归形式。
int BinarySearch(int s［n］,int x,int low,int high)
{
if (low>high) return -1;
int middle=(low+high)/2;
if(x==s［middle］)return middle;
else if(x>s［middle］)
return BinarySearch(s, x, middle+1, high);
else
return BinarySearch(s, x, low, middle-1);
}
5. 算法分析
从算法描述可知，每执行一次while循环或递归调用一次BinarySearch算法，待搜索范围的大小就减少一半。在查找的过程中，每次均将下标为middle的元素与给定值x进行比较，如果x<s［middle］，则修改high为middle-1，如果x>s［middle］，则修改low为middle+1，并重新计算middle的值； 以此类推，直到x等于s［middle］，则查找成功； 或者low>high，则查找失败。
设给定的有序序列中具有n个元素。
显然，当n=1时，查找一个元素需要常量时间，因而T(n)=O(1)。
当n>1时，计算序列的中间位置及进行元素的比较，需要常量时间O(1)。递归地求解规模为n/2的子问题，所需时间为T(n/2)。
因此，二分查找算法所需的运行时间T(n)的递归形式如下：
T(n)=O(1)，n=1
T(n/2)+O(1)，n>1
当n>1时，有
T(n)=T(n/2)+O(1)
=T(n/4)+2O(1)
=T(n/8)+3O(1)
=…
=T(n/2x)+xO(1)
简单起见，令n=2x，则x=logn。
由此，T(n)=T(1)+logn=O(1)+O(logn)。因此，二分查找算法的时间复杂性为O(logn)。
采用非递归形式实现的二分查找算法，其空间复杂性为常量级O(1)； 采用递归形式实现的二分查找算法，其空间复杂性为O(logn)。
6. C++实战
相关代码如下。
#include<iostream>
#include<malloc.h>
using namespace std;
int NBinarySearch(int n,int s［］,int x){
int low=0,high=n-1;
while(low<=high){
int middle=(low+high)/2;
if(x==s［middle］)
return middle;
else if(x>s［middle］)
low=middle+1;
else
high=middle-1;
}
return -1;
}
int BinarySearch(int s［］,int x,int low,int high)
{
if (low>high) return -1;
int middle=(low+high)/2;
if(x==s［middle］) return middle;
else if(x>s［middle］)
return BinarySearch(s, x, middle+1, high);
else
return BinarySearch(s, x, low, middle-1);
}
int main(){
int n = 0;
cout<<"请输入元素个数n： ";
cin>>n;
int * s = (int *)malloc(n*sizeof(int));
cout<<"请输入n个有序元素:";
for(int i=0;i<n;i++){
cin>>s［i］;
}
int k;
cout<<"请输入要查找的元素k： ";
cin>>k;
int position = NBinarySearch(n,s,k);
int position_recursion = BinarySearch(s,k,0,n-1);
cout<<"非递归算法——k在s中的位置是： "<<position<<endl;
cout<<"递归算法——k在s中的位置是： "<<position_recursion<<endl;
}
微课视频
3.3循环赛日程表
1. 问题描述
设有n=2k个运动员要进行羽毛球循环赛，现要设计一个满足以下要求的比赛日程表：
（1） 每个选手必须与其他n-1个选手各赛一次。
（2） 每个选手一天只能比赛一次。
（3） 循环赛一共需要进行n-1天。
由于n=2k，显然n为偶数。
2. 分治算法求解的算法思路
（1） 如何分，即如何合理地进行问题的分解？
根据分治算法的思想，将选手一分为二，n个选手的比赛日程表可以通过对n/2=2k-1个选手设计的比赛日程表来实现，而2k-1个选手的比赛日程表可通过对2k-1/2=2k-2个选手设计的比赛日程表来实现，以此类推，22个选手的比赛日程表可通过对两个选手设计的比赛日程表来实现。此时，问题的求解将变得异常简单。
（2） 如何治，即如何进行问题的求解？
根据问题的分解思想可知，在对问题的求解过程中，递归地执行一分为二的分解策略，直至只剩下两个选手时，比赛日程表的制定就变得很简单： 只要让这两个选手直接比赛就可以了。反过来，如果两个选手的比赛日程表已经制定出来，那么2×2=22个选手的比赛日程表可以合并求出，以此类推，直到2k-1个选手的比赛日程表制定出来时，那么2k个选手的比赛日程表的制定就迎刃而解了。可见，2k个选手的比赛日程安排问题是通过依次求解21,22，…，2k个选手的比赛日程问题得出的。
（3） 问题的关键——发现循环赛日程表制定过程中存在的规律性。
下面从简单的实例入手，期望发现循环赛日程表制定过程中存在的规律。
假设n位选手的编号为1,2,3,…,n。按照问题描述和分治算法求解思路，可将比赛日程表设计成一个n行n-1列的二维表，其中，行表示选手编号，列表示选手比赛的天数，第i行第j列表示第i个选手在第j天所遇到的选手。
【例32】n=21个选手的比赛日程表的制定。
根据上述分析，两个选手的比赛日程表非常容易制定，直接进行比赛即可，且需要n-1=21-1=1天完成。21个选手的比赛日程表如表31所示。
表31的意思是： 第一天和1号选手进行比赛的是2号选手，当然，第一天和2号选手进行比赛的是1号选手。仔细研究发现，该表有一定的规律性： 左上角的1和右下角的1对称，左下角的2和右上角的2对称。
【例33】n=22个选手的比赛日程表的制定。
首先，依据分治算法的思想，将问题一分为二，即分别求出1号和2号选手的比赛日程表、3号和4号选手的比赛日程表，如表32所示。
其次，依据例32中发现的规律性，将表32中求得的两个子问题的解进行合并，就可求出22个选手的比赛日程表，具体结果如表33所示。
表3121个选手的比赛日程表
表32子问题的比赛日程表
表3322个选手的比赛日程表
观察表33，其制定完全符合要求，4个选手共比赛3天，每个选手一天只比赛一次，且在3天内与其他选手均进行了比赛。由此可见，例32中的规律性是可取的。
【例34】23个选手的比赛日程表的制定。
首先，根据分治算法的思想将问题一分为二，得到两个子问题： 即问题1（1，2，3，4）和问题2（5，6，7，8），两个子问题继续一分为二，最终得到可直接求解的4个子问题： 问题11（1，2）、问题12（3，4）、问题21（5，6）、问题22（7，8）。
分别求出这4个子问题的解，具体求解结果如表34所示。
其次，根据表制定的规律性，将问题11（1，2）和问题12（3，4）的解进行合并，可得到问题1（1，2，3，4）的解； 同样，将问题21（5，6）和问题22（7，8）的解进行合并，可得到问题2（5，6，7，8）的解，求解结果如表35所示。
表344个子问题的比赛日程表
表35子问题解的合并
最后，将问题1（1，2，3，4）和问题2（5，6，7，8）的解进行合并，可得到23个选手的比赛日程表，求解结果如表36所示。
表3623个选手的比赛日程表
至此，23个选手的比赛日程表制定完毕。
3. 算法描述
算法描述如下：
void Round_Robin_Calendar(int n,int k, int **a)
{//整数k、空的二维数组a用来表示比赛日程安排表
for(i=1;i<=n;i++)a［1］［i］=i; //用一个for循环输出日程表的第一行
int m=1; //m用来控制每一次填充数组时i(i表示行)和j(j表示
//列)的起始填充位置
for(int s=1;s<=k;s++)//将问题划分为k部分，依次处理
{
n/=2;
for(int t=1;t<=n;t++)//对每一部分的问题进行划分，然后根据分治法的思想，
//进行每一个单元格的填充，填充原则是： 对角线填充
for(int i=m+1;i<=2*m;i++)//i控制行
for(int j=m+1;j<=2*m;j++)//j控制列
{
a［i］［j+(t-1)*m*2］=a［i-m］［j+(t-1)*m*2-m］;//右下角的值等
//于左上角的值
a［i］［j+(t-1)*m*2-m］=a［i-m］［j+(t-1)*m*2］; }//左下角的值等
//于右上角的值
m*=2;
}
}
4. C++实战
相关代码如下。
#include<iostream>
using namespace std;
void Round_Robin_Calendar(int n,int k, int **a)
{//整数k、空的二维数组a用来表示比赛日程安排表
int i,j,s;
for(i=1;i<=n;i++) a［1］［i］=i;//用一个for循环输出日程表的第一行
int m=1; //m用来控制每一次填充数组时i(i表示行)和j(j表示
//列)的起始填充位置
for(s=1;s<=k;s++) //将问题划分为k部分，依次处理
{
n/=2;
for(int t=1;t<=n;t++) //对每一部分的问题进行划分，然后根据分治法的思想，
//进行每一个单元格的填充，填充原则是： 对角线填充
for(i=m+1;i<=2*m;i++) //i控制行
for(j=m+1;j<=2*m;j++) //j控制列
{
a［i］［j+(t-1)*m*2］=a［i-m］［j+(t-1)*m*2-m］; //右下角的值等于左上角的值
a［i］［j+(t-1)*m*2-m］=a［i-m］［j+(t-1)*m*2］; //左下角的值等于右上角的值
}
m*=2;
}
}
int main(){
cout<<"请输入运动员数2的k次方： " ;
int k;
cin>>k;
int n=1;
//计算2的k次方，即计算运动员数n
for(int i=1;i<=k;i++) n*=2;
// 动态分配二维数组
int **a = new int*［n+1］;
for(int i=0;i<=n;i++){
a［i］ = new int［n+1］;
}
//比赛日程安排
Round_Robin_Calendar(n,k,a);
//输出循环日程安排
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++){
cout<<a［i］［j］<<" ";
}
cout<<endl;
}
}
for(int i=0;i<=n;i++)
delete ［］ a［i］;
delete ［］ a;
}
微课视频
3.4合并排序
1. 算法思想
合并排序是采用分治策略实现对n个元素进行排序的算法，是分治算法的一个典型应用和完美体现。它是一种平衡、简单的二分分治策略，其计算过程分为三大步：
（1） 分解： 将待排序元素分成大小大致相同的两个子序列。
（2） 求解子问题： 用合并排序法分别对两个子序列递归地进行排序。
（3） 合并： 将排好序的有序子序列进行合并，得到符合要求的有序序列。
那么，该如何更好地理解合并排序算法的思想呢？由于排序问题给定的是一个无序的序列，而合并是合并两个已经排好序的序列。为此，可以把待排序元素分解成两个规模大致相等的子序列，如果不易解决，再将得到的子序列继续分解，直到子序列中包含的元素个数为1。众所周知，单个元素的序列本身是有序的，此时可进行合并，这就是分治策略的巧妙运用。
2. 算法设计及描述
（1） 合并过程。
从算法的思想很容易看出： 合并排序的关键步骤在于如何合并两个已排好序的有序子序列。为了进行合并，引入一个辅助过程Merge(A,low,middle,high)，该过程将排好序的两个子序列A［low:middle］和A［middle+1:high］进行合并。其中，low、high表示待排序范围在数组中的下界和上界，middle表示两个序列的分开位置，满足low≤middle＜high； 由于在合并过程中可能会破坏原来的有序序列，因此，合并最好不要就地进行，本算法采用了辅助数组B［low:high］来存放合并后的有序序列。
合并方法： 设置3个工作指针i，j，k。其中，i和j指示两个待排序序列中当前需比较的元素，k指向辅助数组B中待放置元素的位置。比较A［i］和A［j］的大小关系，如果A［i］小于或等于A［j］，则B［k］=A［i］，同时将指针i和k分别推进一步； 反之，B［k］=A［j］，同时将指针j和k分别推进一步。如此反复，直到其中一个序列为空。最后，将非空序列中的剩余元素按原次序全部放到辅助数组B的尾部。
合并两个有序子序列的算法描述如下：
void Merge(int A［］，int low，int middle，int high)
{
int i,j,k; //参数i, j分别表示两个待合并的有序子序列的当前位置； k
//表示合并后的有序序列的当前位置
int *B=new int［high-low+1］;
i=low; j=middle+1; k=0;
while(i<=middle&&j<=high) //两个子序列非空
if(A［i］<=A［j］)B［k++］=A［i++］;
elseB［k++］=A［j++］;
while (i<=middle) //如果子序列A［low:middle］非空，则进行收尾处理
B［k++］=A［i++］;
while (j<=high)//如果子序列A［middle+1:high］非空，则进行收尾处理
B［k++］=A［j++］;
for(i=low;i<=high;i++) //将合并后的序列复制回数组A
j=0
A［i］=B［j++］;
}
最坏的情况是两个子序列A［low:middle］和A［middle+1:high］的数据是一个交替的序列，例如 (1，3，5，7)和（2，4，6，8)，则需要比较的次数为n-1=7次。
（2） 递归形式的合并排序算法。
递归形式的合并排序算法就是把序列分为两个子序列，然后对子序列进行递归排序，再把两个已排好序的子序列合并成一个有序的序列。
可以将Merge过程作为合并排序算法的一个子程序使用。设置MergeSort(A,low,high)对子序列A［low:high］进行排序，如果low≥high，则该子序列中至多只有一个元素，当然是已排序好的。否则，依据分治算法的思想对问题进行分解，即计算出一个下标middle，将A［low:high］分解成A［low:middle］和A［middle+1:high］，分解原则是使二者的大小大致相等。
合并排序算法描述如下：
void MergeSort(int A［］，int low，int high)
{int middle;
if (low<high)
{
middle=(low+high)/2; //取中点
MergeSort(A,low,middle); //对A［low:middle］中的元素进行排序
MergeSort(A,middle+1,high); //对A［middle+1:high］中的元素进行排序
Merge(A,low,middle,high); //合并
}
}
3. 合并排序算法的构造实例
【例35】设待排序序列A=<8,3,2,9,7,1,5,4>，采用MergeSort算法对序列A进行排序。具体排序过程如图35所示。
图35合并排序过程示意图
其实，通过综合算法的设计思想和上述求解过程展示，很容易看出合并排序算法的求解过程实质上是： 经过迭代分解，待排序序列A最终被分解成8个只含一个元素的序列，然后两两合并，最终合并成一个有序序列。
4. 算法分析
假设待排序序列中元素个数为n。
显然，当n=1时，合并排序一个元素需要常数时间，因而T(n)=O(1)。
当n>1时，将时间T如下分解：
分解： 这一步仅仅是计算出子序列的中间位置，需要常数时间O(1)。
解决子问题： 递归求解两个规模为n/2的子问题，所需时间为2T(n/2)。
合并： 对于一个含有n个元素的序列，Merge算法可在O(n)时间内完成。
将以上阶段所需的时间进行相加，即得到合并排序算法对n个元素进行排序，在最坏情况下所需的运行时间T(n)的递归形式为
T(n)=O(1)，n=1
2T(n/2)+O(n)，n>1
当n>1时，有
T(n)=2T(n/2)+O(n)
=2(2T(n/4)+O(n/2))+O(n)=4T(n/4)+2O(n)
=4(2T(n/8)+O(n/4))+2O(n)=8T(n/8)+3O(n)
=…
=2xT(n/2x)+xO(n)
令n=2x，则x=logn。
由此可得，T(n)=nT(1)+logn O(n)=O(n)+O(nlogn)，即合并排序算法的时间复杂性为O(nlogn)。
合并排序算法所使用的工作空间取决于Merge算法，每调用一次Merge算法，便分配一个适当大小的缓冲区，退出Merge便释放它。在最后一次调用Merge算法时，所分配的缓冲区最大，此时，它把两个子序列合并成一个长度为n的序列，需要O(n)个工作单元。所以，合并排序算法的空间复杂性为O(n)。
5. C++实战
相关代码如下。
#include<iostream>
#include<iterator>
#include<algorithm>
using namespace std;
void Merge(int A［］,int low,int middle,int high)
{
int i,j,k;//参数i, j分别表示两个待合并的有序子序列的当前位
//置； k表示合并后的有序序列的当前位置
int *B=new int［high-low+1］;
i=low;
j=middle+1;
k=0;
while(i<=middle&&j<=high) //两个子序列非空
{
if(A［i］<=A［j］)
B［k++］=A［i++］;
else
B［k++］=A［j++］;
}
while (i<=middle) //如果子序列A［low:middle］非空，则进行收尾处理
B［k++］=A［i++］;
while (j<=high) //如果子序列A［middle+1:high］非空，则进行收尾处理
B［k++］=A［j++］;
j = 0;
for(i=low;i<=high;i++) //将合并后的序列复制回数组A
A［i］=B［j++］;
delete ［］B;
}
void MergeSort (int A［］,int low,int high)
{
int middle;
if (low<high)
{
middle=(low+high)/2; //取中点
MergeSort(A,low,middle); //对A［low:middle］中的元素进行排序
MergeSort(A,middle+1,high); //对A［middle+1:high］中的元素进行排序
Merge(A,low,middle,high); //合并
}
}
int main(){
cout<<"请输入待排序元素个数： ";
int n;
cin>>n;
int *a=new int［n］;
cout<<"请输入待排序元素： ";
for(int i=0 ;i<n;i++)
cin>>a［i］;
MergeSort(a,0,n-1);
copy(a,a+n,ostream_iterator<int>(cout," "));//输出a中的元素
delete ［］a;
}
微课视频
3.5快速排序
1. 算法思想
快速排序是C.A.R.Hoare于1962年提出的划分交换排序方法，其基本思想是： 通过一趟扫描将待排序的元素分割成独立的三个序列，第一个序列中所有元素均不大于基准元素，第二个序列是基准元素，第三个序列中所有元素均不小于基准元素。由于第二个序列已经处于正确位置，因此需要再按此方法对第一个序列和第三个序列分别进行排序，整个排序过程可以递归进行，最终可使整个序列变成有序序列。
（1） 快速排序算法的分治策略体现。
快速排序的基本思想是基于分治策略的，利用分治法可将快速排序的基本思想描述如下： 设当前待排序的序列为R［low:high］，其中low≤high，如果序列的规模足够小则直接进行排序，否则分三步处理。
① 分解。
在R［low:high］中选定一个元素作为基准元素(pivot)，该基准元素的位置(pivotpos)在划分的过程中确定。以此基准元素为标准将待排序序列划分为两个子序列R［low:pivotpos-1］和R［pivotpos+1:high］，并使序列R［low:pivotpos-1］中所有元素的值均小于或等于R［pivotpos］，序列R［pivotpos+1:high］中所有元素的值均大于或等于R［pivotpos］。此时基准元素已位于正确的位置上，它无须参加后面的排序。
注意： 划分序列的关键是要计算出所选定的基准元素所在的位置pivotpos。其中low≤pivotpos≤high。
② 求解子问题。
对两个子序列R［low:pivotpos-1］和R［pivotpos+1:high］，分别通过递归调用快速排序算法来进行排序。
③ 合并。
由于对R［low:pivotpos-1］和R［pivotpos+1:high］的排序是就地进行的，所以在R［low:pivotpos-1］和R［pivotpos+1:high］都已排好序后，合并步骤无须做什么，序列R［low:high］就已排好序了。
（2） 基准元素的选取。
从待排序序列中选取指导划分的基准元素是决定算法性能的关键。基准元素的选取应该遵循平衡子问题的原则，即使得划分后的两个子序列的长度尽量相同。基准元素的选择方法有很多种，常用的有： ①取第一个元素。即以待排序序列的首元素作为基准元素。②取最后一个元素。即以待排序序列的尾元素作为基准元素。③取位于中间位置的元素。即以待排序序列的中间位置的元素作为基准元素。④“三者取中的规则”。即在待排序序列中，将该序列的第一个元素、最后一个元素和中间位置的元素进行比较，取三者之中值作为基准元素。⑤取位于low和high之间的随机数k(low≤k≤high)，用R［k］作为基准元素。即采用随机函数产生一个位于low和high之间的随机数k(low≤k≤high)，用R［k］作为基准，这相当于强迫R［low:high］中的元素是随机分布的。
无论如何，在快速排序算法中选取的基准元素一定要保证算法正常结束。
2. 划分方法
从算法思想容易看出： 实现快速排序的关键在于依据所选的基准元素对序列进行划分，那么，究竟如何来实现划分呢？
（1） 划分方法的过程设计。
假设待排序序列为R［low:high］，该划分过程以第一个元素作为基准元素。
步骤1： 设置两个参数i和j，它们的初值分别为待排序序列的下界和上界，即i=low，j=high。
步骤2： 选取待排序序列的第一个元素R［low］作为基准元素，并将该值赋给变量pivot。
步骤3： 令j自j位置开始向左扫描，如果j位置所对应的元素的值大于或等于pivot，则j前移一个位置(即j--)。重复该过程，直至找到第1个小于pivot的元素R［j］，将R［j］与R［i］进行交换，i++。其实，交换后R［j］所对应的元素就是pivot。
步骤4： 令i自i位置开始向右扫描，如果i位置所对应的元素的值小于或等于pivot，则i后移一个位置(即i++)。重复该过程，直至找到第1个大于pivot的元素R［i］，将R［j］与R［i］进行交换，j--。其实，交换后R［i］所对应的元素就是pivot。
步骤5： 重复步骤3、步骤4，交替改变扫描方向，从两端各自往中间靠拢直至i=j。此时i和j指向同一个位置，即基准元素pivot的最终位置。
（2） 划分方法的算法描述。
int Partition(int R［］,int low,int high)
{
int i=low,j=high,pivot=R［low］; //用序列的第一个元素作为基准元素
while(i<j)//从序列的两端交替向中间扫描，直至i等于j为止
{
while(i<j&&R［j］>=pivot) //pivot相当于在位置i上
j--;//从右向左扫描，查找第1个小于pivot的元素
if(i<j) //表示找到了小于pivot的元素
swap(R［i++］,R［j］); //交换R［i］和R［j］，交换后i执行加1操作
while(i<j&&R［i］<=pivot)
i++; //从左向右扫描，查找第1个大于pivot的元素
if(i<j) //表示找到了大于pivot的元素
swap(R［i］,R［j--］);//交换R［i］和R［j］，交换后j执行减1操作
}
return j;
}
（3） 划分方法的构造实例。
【例36】划分的例子(黑体表示基准元素)，设定第一个元素49作为基准元素。
① 初始序列，如图36所示。
② 向左扫描，由于i<j且27<49，因此，R［i］与R［j］交换且i后移一位。进行1次交换后的状态如图37所示。
49386597761327
↑i↑j
图36划分的初始状态
27386597761349
↑i↑j
图371次交换后的状态
③ 向右扫描，由于i<j且38<49，i后移1位。i和j的位置关系如图38所示。
④ 向右扫描，由于i<j且65>49，因此，R［i］与R［j］交换且j前移一位。进行2次交换后的状态如图39所示。
27386597761349
↑i↑j
图38i后移1位后的状态
27384997761365
↑i↑j
图392次交换后的状态
⑤ 向左扫描，由于i<j且13<49，因此，R［i］与R［j］交换且i后移一位。进行3次交换后状态如图310所示。
⑥ 向右扫描，由于i<j且97>49，因此，R［i］与R［j］交换且j前移一位。进行4次交换后的状态如图311所示。
27381397764965
↑i↑j
图3103次交换后的状态
27381349769765
↑i↑j
图3114次交换后的状态
⑦ 向左扫描，由于i<j且76>49，j前移一位，i和j的位置关系如图312所示。
27381349769765
↑i↑j
图312j前移一位后的状态
⑧ 此时i=j，循环结束，返回j，即基准元素所处的最终位置。至此，划分过程结束。
3. 快速排序算法描述
以基准元素为标准将待排序序列划分为两个子序列后，对每一个子序列分别采用递归技术来进行排序，最终可获得一个有序的序列。至此，快速排序算法描述如下：
void QuickSort(int R［］，int low，int high) //对R［low..high］快速排序
{
int pivotpos； //划分后的基准元素所对应的位置
if(low<high) //仅当区间长度大于1时才须排序
{
pivotpos=Partition(R,low,high)； //对R［low..high］做划分
QuickSort(R,low,pivotpos-1)； //对左区间递归排序
QuickSort(R,pivotpos+1,high)； //对右区间递归排序
}
}
【例37】序列［49386597761327］，经过一次划分后，得到的序列为［273813497697 65］，对两个子序列分别进行递归排序。
接上述划分过程：
① 以27为基准元素。
向左扫描，1次交换之后为［133827］，向右扫描，2次交换之后为［132738］，得到序列 ［132738］。
② 以76为基准元素。
向左扫描，1次交换之后为［659776］，向右扫描，2次交换之后为［657697］，得到序列［657697］。
③ 最终得到的有序序列为［13273849657697］。
4. 算法分析
快速排序算法的时间主要耗费在划分操作上，并与划分是否平衡密切相关。对于长度为n的待排序序列，一次划分算法Partition需要对整个待排序序列扫描一遍，其所需的计算时间显然为O(n)。
下面从三种情况来讨论快速排序算法QuickSort的时间复杂性。
（1） 最坏时间复杂性。
最坏情况是每次划分选取的基准元素都是在当前待排序序列中的最小(或最大)元素，划分的结果是基准元素左边的子序列为空(或右边的子序列为空)，而划分所得的另一个非空的子序列中元素个数，仅仅比划分前的排序序列中元素个数少一个。
在这样的情况下，快速排序算法QuickSort必须做n-1次划分，那么算法的运行时间T(n)的递归形式为
T(n)=O(1)，n=1
T(n-1)+O(n)，n>1
当n>1时，有
T(n)=T(n-1)+O(n)
=T(n-2)+O(n-1)+O(n)
=T(n-3)+O(n-2)+O(n-1)+O(n)
=…
=T(1)+O(2)+…+O(n-1)+O(n)
=O（1+2+…+（n-1）+n）
=O（n（n+1）/2）
因此，快速排序算法QuickSort的最坏时间复杂性为O(n2)。
如果按上面给出的Partition划分算法，每次取当前排序序列的第1个元素为基准，那么当序列中的元素已按递增序(或递减序)排列时，每次划分所取的基准元素就是当前序列中值最小(或最大)的元素，则完成快速排序所需的运行时间反而最多。
（2） 最好时间复杂性。
在最好情况下，每次划分所取的基准元素都是当前待排序序列的“中值”元素，划分的结果是基准元素的左、右两个子序列的长度大致相等，此时，算法的运行时间T(n)的递归形式为
T(n)=O(1)，n=1
2T(n/2)+O(n)，n>1
解此递归式，可得快速排序算法的最好时间复杂性为O(nlogn)。
注意： 用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右两个子序列的长度大致相等，故递归树的高度为O(logn)，而递归树每一层上各个结点所对应的划分过程中所需要的元素的比较次数总和不超过n，故整个排序过程所需要的元素间的比较总次数为O(nlogn)，即时间复杂性为O(nlogn)。
（3） 平均时间复杂性。
在平均情况下，设基准元素的值为第k（1≤k≤n）个，则有
T(n)=1n∑nk=1(T(n-k)+T(k-1))+n
=2n∑nk=1T(k)+n
采用归纳法，最终求得T(n)的数量级也为O(nlogn)。
尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于元素比较的内部排序算法中速度最快者，快速排序也因此而得名。
（4） 空间复杂性。
由于快速排序算法是递归执行的，需要一个栈来存放每一层递归调用的必要信息，其最大容量应与递归调用的深度一致。最好情况下，若每次划分较为均匀，则递归树的高度为O(logn)，故递归所需栈空间为O(logn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。平均情况下，所需栈空间为O(logn)。
5. C++实战
相关代码如下。
#include<iostream>
#include<iterator>
#include<algorithm>
using namespace std;
int Partition(int R［］,int low,int high)
{
int i=low,j=high,pivot=R［low］;//用序列的第一个元素作为基准元素
while(i<j) //从序列的两端交替向中间扫描，直至i等于j
{
while(i<j&&R［j］>=pivot) //pivot相当于在位置i上
j--; //从右向左扫描，查找第1个小于pivot的元素
if(i<j) //表示找到了小于pivot的元素
swap(R［i++］,R［j］); //交换R［i］和R［j］，交换后i执行加1操作
while(i<j&&R［i］<=pivot)
i++; //从左向右扫描，查找第1个大于pivot的元素
if(i<j) //表示找到了大于pivot的元素
swap(R［i］,R［j--］); //交换R［i］和R［j］，交换后j执行减1操作
}
return j;
}
void QuickSort(int R［］,int low,int high) //对R［low..high］快速排序
{
int pivotpos; //划分后的基准元素所对应的位置
if(low<high) //仅当区间长度大于1时才须排序
{
pivotpos=Partition(R,low,high); //对R［low..high］做划分
QuickSort(R,low,pivotpos-1); //对左区间递归排序
QuickSort(R,pivotpos+1,high); //对右区间递归排序
}
}
int main(){
cout<<"请输入待排序元素个数： ";
int n;
cin>>n;
int *a = new int［n］;
cout<<"请输入待排序元素： ";
for(int i=0 ;i<n;i++)
cin>>a［i］;
QuickSort(a,0,n-1);
copy(a,a+n,ostream_iterator<int>(cout," "));//输出a中元素
delete ［］ a;
}
微课视频
3.6最接近点对问题
在计算机应用中，常用诸如点、圆等简单的几何对象描述现实世界的实体，在涉及这些几何对象的问题时，常需要了解其邻域中其他几何对象的信息。例如，一个控制空中或海上交通的系统就需要了解两个最近的交通工具，以预测可能产生的相撞事故。实质上，这就是要找出空间最接近的一对点问题。因此，研究该问题有很大的实用价值。
1. 问题描述
最接近点对问题要求在给定平面上n个点组成的集合S中，找出其中n个点组成的点对中距离最近的一对点。
将所给平面上的n个点的集合S分成规模大致相等的两个子集S1和S2。递归求解S1和S2中的最接近点对。在这里，采用分治算法求解的关键在于合并步骤，即由S1和S2中的最接近点对，如何求得S中的最接近点对？很明显，集合S中的最接近点对或者是子问题S1的解，或者是子问题S2的解，或者是一个点在S1中、一个点在S2中的情况组成的最接近点对。S1和S2中的最接近点对可以用递归求得。但是一个点在S1中、另一个点在S2中的情况组成的最接近点对怎么求得呢？
为了讲明白这个问题，先来考虑一维情形。
2. 一维情形
（1） 算法思想。
令平面上的点的纵坐标全部等于0，S中的n个点退化为X轴上的n个实数 x1,x2,…,xn。最接近点对即为这n个实数中相差最小的两个实数，每个实数对应数轴上的一个点。用xm将x1,x2,…,xn分成两部分S1和S2，这种情况下如何找出S1中的一个点p和S2中的一个点q组成的点对(p,q)呢？令S1中最接近点对的距离为d1，S2中的最接近点对的距离为d2，取d=min{d1,d2}。如果S的最接近点对是(p,q)，则|xp-xq|小于或等于d。由于p∈S1，q∈S2，所以二者与xm的距离不超过d，即m-d<xp≤m，m<xq≤m+d。
在S1中任何两个点的距离均小于或等于d1，同样也小于或等于d。因此，在区域(m-d,m］中至多包含S1中的一个点且是S1中最右边的点，即S1中X坐标的最大点。同理，在区域(m,m+d］中至多包含S2中的一个点且是S2中最左边的点，即S2中X坐标的最小点。可见，线性时间就可以找出S1中的p和S2中的q，因此线性时间就可以完成子问题的解合并成原问题解的过程。
（2） 算法设计。
步骤1： 基于平衡子问题的思想，通过S中各点的X坐标的中位数xm将S划分为两个子集S1={i|xi≤xm}和S2={i|xi>xm}，如图313所示。
图313点集S划分成S1和S2
步骤2： 递归地在S1中找出其最接近点对(pi,pj)，距离为d1。
步骤3： 递归地在S2中找出其最接近点对(qi,qj)，距离为d2。
步骤4: 取d=min{d1,d2}。
步骤5： 求S1中的最大值xp； 求S2中的最小值xq。
步骤6： 计算d3=xq-xp。
步骤7： 取min{d,d3}且记录最接近点对的坐标，即求得S中的最接近点对。
（3） 算法描述。
bool CPAIR1(POINT S［］, double &d,double &p,double &q)
{
double p1,p2,q1,q2,p3,q3;//用来记录3种情况的最接近点对
n=|S|;
if (n2)
{d=∞;return false;}
else if(n==2)
{
d=|x［2］-x［1］|;// x［1..n］存放的是S中n个点的坐标
p=x［2］;q=x［1］;
return true;
}
m=S中各点的横坐标值的中位数;
构造S1和S2;
CPAIR1(S1,d1,p1,p2);
CPAIR1(S2,d2,q1,q2);
p3=max(S1);
q3=min(S2);
double d3=q3-p3;
if(d1=d2 && d1=d3)
{d=d1;p=p1;q=p2;}
if(d1d2)
{d=d2;p=q1;q=q2;}
else
{d=d3;p=p3;q=q3;}
return true;
}
（4） 算法分析。
假设用T(n)表示从n个点中找出最接近点对所耗的时间，则每个子问题所耗的时间为T(n/2)； 找出中位数可以在线性时间O(n)实现； 合并子问题的解所耗时间为线性时间O(n)，故一维情形下时间的递归表达式为
T(n)=O(1),n<32T(n/2)+O(n)，n≥3
解此递归方程可得T(n)=O(nlogn)。
在一维情形下，更容易想到的解决方法是先排序，再线性扫描就可以了。但是这种方法不容易推广到二维情形。上述分治思想的解决方法很容易推广到二维情形。
（5） C++实战。
相关代码如下。
#include<iostream>
#include<cmath>
#include<cfloat>
#include<algorithm>
#define INF DBL_MAX
using namespace std;
bool CPAIR1(double S［］, int left,int right,double &d,double &p,double &q)
{
double p1,p2,q1,q2,p3,q3; //用来记录3种情况的最接近点对
int n=right-left + 1;
if (n<2)
{
d=INF;
return false;
}
else if(n==2)
{
d=abs(S［right］-S［left］); // x［1..n］存放的是S中n个点的坐标
p=S［left］;
q=S［right］;
return true;
}
int m=(left+right)/2;
double d1,d2;
CPAIR1(S,left,m,d1,p1,q1);
CPAIR1(S,m+1,right,d2,p2,q2);
p3=S［m］;
q3=S［m+1］;
double d3=q3-p3;
if(d1<=d2 and d1<=d3)
{
d=d1;
p=p1;
q=q1;
}
else if(d2<d3){
d=d2;
p=p2;
q=q2;
}
else{
d=d3;
p=p3;
q=q3;
}
return true;
}
int main(){
int n = 13;
double points［n］={1,3,-1,7,5,-2,-6,4,15,10,0.6,0,-0.5};
sort(points,points+n);
double d = INF;
double p,q;
CPAIR1(points,0,n-1,d,p,q);
cout<<"最接近点对为： "<<endl;
cout<<p<<","<<q<<endl;
cout<<"最接近点对距离d="<<d<<endl;
}
3. 二维情形
（1） 算法思想。
选取一垂直线l，x=xm作为分割线，其中xm为S中各点X坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d所对应的点对，或者是S1
中的某个点p和S2中的某个点q组成的点对(p,q)。如何找出点对(p,q)呢？如果|p-q|小于d，则p点分布在P1带形区域内(左虚线和分割线l所夹的区域)，q点分布在P2带形区域内(右虚线和分割线l所夹的区域)，如图314所示。
另外，对于P1中任意一点p，与它距离小于d的点分布在以p点为圆心、以d为半径的圆内。因此，与点p构成最接近点对的P2中的点一定落在一个d×2d的矩形R中，如图315所示。
图314距离直线l的距离小于d的所有点
图315包含点q的d×2d矩形区R
图316矩形R中点的
稀疏性
在矩形R中，有多少个点可能与P1中的点p构成最接近点对呢？由d的意义可知，矩形R中任何两个S中的点的距离都大于或等于d。由此可知，至少可以将d×2d的矩形R分割成如图316所示的6部分，其中任何一部分包含P2中的点最多有一个，如果包含P2中的两个点，则这两个点的距离最大为(d/2)2+(2d/3)2=5d/6<d。这与P2中任何两个S中的点的距离都大于或等于d矛盾。因此，在矩形R中最多只有6个P2中的点与p构成最接近点对。故在分治法的合并步骤中最多只需要检查6×n/2=3n个候选者。
针对P1中的任意一点p，检查P2中的哪6个点，从而可以找出最接近点对呢？为了确切地知道要检查哪6个点，可以将p和P2中所有点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的P2中的点一定在矩形R中，所以它们在直线l上的投影点与p在l上的投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中的点按其Y坐标排好序，则对P1中所有点，对排好序的点做一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。
（2） 算法描述。
首先定义POINT结构体，除X坐标和Y坐标外，重载了操作符<，定义排序操作按照X坐标升序排序，X坐标相同时，按照Y坐标升序排序。POINT定义如下：
typedef struct POINT
{
double x; //点的横坐标
double y; //点的纵坐标
bool operator <(const POINT &a)const{
if(a.x==x)
return y<a.y;
else
return x<a.x;
}
};
在最接近点对问题的求解中，需要用到两个点之间的欧几里得距离。求解两点间距离的算法描述如下：
double Distance(POINT u, const POINT v)//计算平面上任意两点u和v之间的距离
{
double dx=u.x-v.x, dy=u.y-v.y;
return sqrt(dx*dx+dy*dy);
}
求解最接近点对问题的算法描述如下：
bool CPAIR1(POINT S［］, int left,int right,double &d,POINT &p,POINT &q)
{
POINT p1,p2,q1,q2,p3,q3; //用来记录3种情况的最接近点对
int n=right-left+1;
if (n<2)
{
d=INF;
return false;
}
else if(n==2)
{
d=Distance(S［0］,S［1］);
p=S［left］;
q=S［right］;
return true;
}
int m = (left+right)/2;
double d1,d2;
CPAIR1(S,left,m,d1,p1,q1);
CPAIR1(S,m+1,right,d2,p2,q2);
d = min(d1,d2);
double d3 = INF;
for(int i=left;i<=m;i++)
if((S［m］.x-S［i］.x) < d)
for(int j=m+1;j<=right;j++)
if(((S［j］.x-S［i］.x)<d)&&((S［j］.y-S［i］.y)<d))
{
double dd = Distance(S［i］,S［j］);
if (dd<d3){
d3 = dd;
p3 = S［i］;
q3 = S［j］;
}
}
if(d1<=d2 and d1<=d3)
{
d=d1;
p=p1;
q=q1;
}
else if(d2<d3){
d=d2;
p=p2;
q=q2;
}
else{
d=d3;
p=p3;
q=q3;
}
return true;
}
（3） 算法分析。
假设用T(n)表示从n个点中找出最接近点对所耗的时间，则每个子问题所耗的时间为T(n/2)。找出中位数可以用线性时间选择算法来实现，耗时O(n)。合并子问题的解所耗时间为线性时间O(n)。故二维情形下的时间的递归表达式为：
T(n)=O(1),n<32T(n/2)+O(n)，n≥3
由此可得T(n)=O(nlogn)。
（4） C++实战。
相关代码如下。
#include<iostream>
#include<cmath>
#include<cfloat>
#include<algorithm>
#define INF DBL_MAX
using namespace std;
typedef struct POINT
{
double x; //点的横坐标
double y; //点的纵坐标
bool operator <(const POINT &a)const{
if(a.x==x)
return y<a.y;
else
return x<a.x;
}
} POINT;
double Distance(POINT u,POINT v){//计算平面上任意两点u和v之间的距离,u,v为元组(x,y)
double dx = u.x - v.x;
double dy = u.y - v.y;
return sqrt(dx*dx+dy*dy);
}
bool CPAIR1(POINT S［］, int left,int right,double &d,POINT &p,POINT &q)
{
POINT p1,p2,q1,q2,p3,q3; //用来记录3种情况的最接近点对
int n=right-left+1;
if (n<2)
{
d=INF;
return false;
}
else if(n==2)
{
d=Distance(S［0］,S［1］);
p=S［left］;
q=S［right］;
return true;
}
int m = (left+right)/2;
double d1,d2;
CPAIR1(S,left,m,d1,p1,q1);
CPAIR1(S,m+1,right,d2,p2,q2);
d = min(d1,d2);
double d3 = INF;
for(int i=left;i<=m;i++)
if((S［m］.x -S［i］.x) < d)
for(int j=m+1;j<=right;j++)
if(((S［j］.x-S［i］.x)<d)&&((S［j］.y-S［i］.y)<d))
{
double dd = Distance(S［i］,S［j］);
if (dd<d3){
d3 = dd;
p3 = S［i］;
q3 = S［j］;
}
}
if(d1<=d2 and d1<=d3)
{
d=d1;
p=p1;
q=q1;
}
else if(d2<d3){
d=d2;
p=p2;
q=q2;
}
else{
d=d3;
p=p3;
q=q3;
}
return true;
}
int main(){
int n = 12;
POINT points［12］={{0,1},{3,2},{4,3},{5,1},{1,2},{2,1},{6,2},{7,2},{8,3},{4,5},{9,0},{6,4}};
sort(points,points+n);
double d = INF;
POINT p,q;
CPAIR1(points,0,n-1,d,p,q);
cout<<"最接近点对为： "<<endl;
cout<<"("<<p.x<<","<<p.y<<")"<<"----"<<"("<<q.x<<","<<q.y<<")"<<endl;
cout<<"最接近点对距离d="<<d<<endl;
}
拓展知识： 禁忌搜索算法
禁忌搜索（Tabu Search或Taboo Search，TS）的思想最早由Fred Glover(美国工程院院士，科罗拉多大学教授)于1986年提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。
禁忌Tabu一词来源于汤加语，是波利尼西亚的一种语言，其含义是保护措施或者危险禁止，这正符合禁忌搜索算法的主题： 一方面，当沿着产生相反结果的道路走下去时，也不会陷入一个圈套而导致无处可逃； 另一方面，在必要情况下，保护措施允许被淘汰，也就是说，某种措施被强制运用时，禁忌条件就宣布无效。
与模拟退火和遗传算法相比，TS是又一种搜索特点不同的 metaheuristic算法。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。
1. 禁忌搜索算法的基本思想
给定一个当前解（初始解）和它的邻域，然后在当前解的邻域中确定若干个候选解； 若最佳候选解所对应的目标值优于“Best so far”状态，则忽视其禁忌特性，用其替代当前解和“Best so far”状态，并将相应的对象加入禁忌表，同时修改禁忌表； 若不存在上述候选解，则在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表； 如此重复上述迭代搜索过程，直至满足停止准则。
2. 禁忌搜索算法的构成
从禁忌搜索算法的思想中，容易看出该算法涉及的概念包括邻域、禁忌表、禁忌长度、候选解、藐视准则等。它们构成了算法，对整个禁忌搜索起着关键的作用。
（1） 邻域移动。
禁忌搜索算法采用了邻域选优的搜索策略，即通过对当前解的“移动”产生其邻域解，选择优秀的邻域解作为当前解，再进行邻域搜索。可见，邻域移动是保证产生好的解和算法搜索速度的最重要因素之一。因此，如何设计有效合理的“移动”方法来产生邻域解是算法的核心。
通常，邻域移动定义的方法很多，对于不同的问题应采用不同的定义方法。通过移动，目标函数值将产生变化，移动前后的目标函数值之差，称为移动值。如果移动值是非负的，则称此移动为改进移动； 否则称作非改进移动。最好的移动不一定是改进移动，也可能是非改进移动，这一点就保证搜索陷入局部最优时，禁忌搜索算法能自动跳出局部最优。
（2） 禁忌表。
禁忌表是防止在搜索过程中出现循环，避免陷入局部最优，它通常记录最近接受的若干次移动，在一定次数内禁止再次被访问，超过了一定次数之后，这些移动从禁忌表中退出，又可以重新被访问。禁忌表是禁忌搜索算法的核心，它的功能和人类的短期记忆功能十分相似。
禁忌表包含两个很重要的概念。一是禁忌对象，就是放入禁忌表中的那些元素，而禁忌的目的就是避免迂回搜索，尽量搜索一些有效的途径。禁忌对象的选择十分灵活，可以是最近访问过的点、状态、状态的变化以及目标函数值等。二是禁忌长度（Tabu size），就是禁忌表的大小。一个禁忌对象进入禁忌表后，只有经过一个确定的迭代次数或者满足一定的条件，才能从禁忌表中退出。也就是说，在当前迭代之后的确定次迭代中或者未达到一定的条件时，这个发生不久的相同操作是被禁止的。容易知道，禁忌表长度越小，计算时间和存储空间越少，这是任何一个算法都希望的。但是，如果禁忌表过小，会造成搜索的循环，这又是要避免的。禁忌长度不但影响了搜索的时间，还直接关系着搜索的两个关键策略： 局部搜索策略和广域搜索策略。如果禁忌表比较长，便于在更广阔的区域搜索，广域搜索能力比较好； 而禁忌表比较短，则使得搜索在小的范围进行，局部搜索性能比较好。禁忌长度的设定要依据问题的规模、邻域的大小来确定，从而达到平衡这两种搜索策略的目的。
（3） 候选解选择策略。
候选解选择策略即择优规则，是对当前的邻域移动选择一个移动而采用的准则。择优规则可以采用多种策略，不同的策略对算法的性能影响不同。一个好的选择策略应该是既保证解的质量又保证计算速度。当前采用最广泛的两类策略是最好改进解优先策略和第一个改进解优先策略。最好改进解优先策略就是对当前邻域中选择移动值最好的移动产生的解，作为下一次迭代的开始，而第一个改进解优先策略是搜索邻域移动时选择第一改进当前解的邻域移动产生的解作为下一次迭代的开始。最好改进解优先策略相当于寻找最陡的下降，这种择优规则效果比较好，但是它需要更多的计算时间； 而最快的下降对应寻找第一个改进解的移动，由于它无须搜索整个一次邻域移动，所以它所花费的计算时间较少，对于比较大的邻域，往往比较适合。
（4） 藐视准则。
在某些特定的条件下，不管某个移动是否在禁忌表中，都接受这个移动，并更新当前解和历史最优解。这个移动满足的这个特定条件，称为渴望水平（aspiration level），或称为破禁水平、特赦准则、藐视准则等。
藐视准则的设定有多种形式，通常选取当前迭代之前所获得的最好解的目标值或此移动禁忌时的目标值作为藐视准则函数。
（5） 算法停止准则。
算法的停止准则一般有以下三类： 一是给定外循环的最大次数，达到该次数时，算法终止； 二是如果当前最优解连续K次相同，则算法终止，K是一个给定的正整数，表示算法已经收敛，无须再继续； 三是目标值控制规则，给定优化问题（目标最小化）的一个下界和一个误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。
另外，短期记忆能够用来避免最近所做的一些移动被重复，但是在很多的情况下短期记忆并不足以把算法搜索带到能够改进解的区域。因此在实际应用中常常短期记忆与长期记忆相结合使用，以保持局部的强化和全局多样化之间的平衡，即在加强搜索到较优解的同时还能把搜索带到未搜索过的区域。
3. 禁忌搜索算法的求解过程
步骤1： 给定算法参数，选定一个初始解x，置禁忌表H为空。
步骤2： 若满足停止规则，停止计算，输出优化结果； 否则继续以下步骤。
步骤3： 利用当前解x的邻域函数产生其所有邻域解，并从中确定若干候选解。
步骤4： 判断候选解是否满足藐视准则？若是，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换Best so far状态，然后转到步骤2； 否则，继续以下步骤。
步骤5： 判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。转到步骤2。
在步骤3中，x的邻域中满足禁忌要求的元素包含两类： 一类是那些没有被禁忌的元素； 另一类是可以被解除禁忌的元素。此时应用藐视准则使某些状态解禁，就是对优良状态的奖励，对禁忌策略的放松，以实现更高效的优化性能。
4. 禁忌搜索算法性能的简单分析
禁忌搜索算法通过对当前解进行“移动”操作来产生当前解邻域中可行的邻域解，取其最好的邻域解作为新的当前解来完成解空间的局部搜索。但该算法的局部搜索能力与其每次“移动”操作所产生的邻域解的数目密切相关。邻域解数目太少，对当前解邻域空间的搜索也就太少，这将影响该算法的局部优化性能； 邻域解数目太多，则将增加算法的执行时间。
用于求解具体的组合优化问题时，禁忌搜索算法中当前解的邻域解是通过在当前解中随机选择两个交换的位置产生的，这样做容易导致局部搜索具有分散性。
该局部搜索的分散性如图317所示。
局部搜索的分散性似乎有利于对局部空间进行全方位搜索，但当邻域解数目一定及邻域解中的优秀解较为集中时，这种分散性反而影响了局部优化的性能。通常采用的解决方案是： 邻域解的产生不是随机的，而是以某种机制来确定其产生，在“移动”过程中以某种概率为依据来找出进行“移动”操作的点，由此产生的禁忌搜索算法的当前解的邻域解大部分集中在邻域空间的特定区域内，而小部分分散在邻域空间的其他区域，这种现象称为禁忌搜索算法的集中性。
该局部搜索的集中性如图318所示。
图317局部搜索的分散性
图318局部搜索的集中性
局部搜索的集中性显著增加了发现局部最优解的可能性，提高了局部搜索的性能。
禁忌搜索算法在搜索过程中允许接受劣解，使得该算法具有很强的“爬山”能力，可以跳出局部最优解。此外，为了避免搜索路径的往返重复，该算法使用“Tab表”来记录搜索过程的历史信息，这可在一定程度上避开局部极值点，开辟新的搜索区域。因此，虽然禁忌搜索算法并不能从理论上保证一定能找到全局最优解，但却能在较短的时间内找到非常优秀的近似最优解。
该算法的一大亮点为： 允许在搜索过程中接受劣解，这样可使算法跳出局部最优解，扩大搜索空间。
本章习题
31简述分治算法的基本思想和求解步骤。
32在一个划分成网格的操场上，n名士兵散乱地站在网格点上。网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个纵队，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x和y的值才能使士兵们以最少的总移动步数排成一列。
33某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路径(或南或北)与主管道相连。如果给定n口油井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，从而使得各油井到主管道的输油管道长度总和最小？证明可在线性时间内确定主管道的最优位置。
34若二分查找变为三分查找，即从a1<a2<…＜an序列中寻找元素x。方法如下： 先与an3比较，若x>an3，则与a2n3比较，总之，使余下的序列约有n/3个元素。试讨论其复杂性。
35设a［0： n］是一个已排好序的数组。请改写二分查找算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置j和大于x的最小元素位置i。当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。
36设n个不同的排好序的整数存于数组T［0:n-1］中。若存在一个下标i，0≤i<n，使得T［i］等于i，设计一个有效算法找到这个下标i； 要求算法在最坏情况下的计算时间为O(logn)。
37设n个元素存于数组T［0:n-1］。对任一元素x，设s(x)={i|T［i］=x}； 当|s(x)|>n/2时，称x为T的主元素，设计一个线性时间算法，确定T中是否存在主元素。
38用快速排序算法对如下数据进行排序： 45,23,65,57,18,2,90,84,12,76。说明划分方法的具体过程。
39应用分治算法完成下面的整数乘法计算： 2348×3825。
310在一个由元素组成的表中，出现次数最多的元素称为众数。试写一个寻找众数的算法，并分析其计算复杂性。
311设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表。
（1） 每个选手必须与其他n-1个选手各赛一次。
（2） 每个选手一天只能赛一次。
（3） 当n是偶数时，循环赛进行n-1天。当n是奇数时，循环赛进行n天。