C++做分治法的过程：
程序代码：
#include<iostream>
#include<cmath>
using namespace std;
// ------------------------------------
typedef struct Node{
int x;
int y;
}Node;
typedef struct NList{
Node* data;
int count;
}NList;
typedef struct CloseNode{
Node a;
Node b;
double space;
}CloseNode;
int max;
//===============================================
//归并排序
void Merge(Node SR[],Node TR[],int i,int m,int n){
//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
int j,k;
for(j=m+1,k=i;i<=m&&j<=n;++k)
if(SR[i].x<=SR[j].x) TR[k]=SR[i++];
else TR[k]=SR[j++];
while(i<=m) TR[k++]=SR[i++];
while(j<=n) TR[k++]=SR[j++];
}
void Msort(Node SR[],Node TR1[],int s,int t){
//将SR[s..t]归并排序为TR1[s..t]
if(s==t) TR1[s]=SR[s];
else{
int m = (s+t)/2;
Node *TR2=new Node[max];//new Node[t-s+1];//这个空间挂挂的,从s到t，这里是从0到t-s
Msort(SR,TR2,s,m);
Msort(SR,TR2,m+1,t);
Merge(TR2,TR1,s,m,t);
}
}
void MergeSort(NList L){
Msort(L.data,L.data,0,L.count-1);
}
// ==================================================
// ------------------------------------------------
//输入各点 到数据结构NList中
void create(NList & L){
cout<<"请输入平面上点的数目:\n";
cin>>max;
L.count=max;
L.data = new Node[L.count];//====================动态空间分配！！！！注意
cout<<"输入"<<L.count<<"个点坐标 X,Y,请不要输入过大，超过计算机计算范围,本程序使用int型（@+@）:"<<endl;
for(int i=0;i<L.count;++i)
cin>>L.data[i].x>>L.data[i].y;
}
// --------------------------------------------------
//求距离平方的函数
double Distinguish2(Node a,Node b){
return ((a.x-b.x)*(a.x-b.x))+((a.y-b.y)*(a.y-b.y));
}
// --------------------------------------------------
//蛮力法求最近对
void BruteForce(const NList & L,CloseNode & cnode,int begin,int end){
for(int i=begin;i<=end;++i)
for(int j=i+1;j<=end;++j){
double space = Distinguish2(L.data[i],L.data[j]);
if(space<cnode.space){
cnode.a=L.data[i];
cnode.b=L.data[j];
cnode.space=space;
}
}
}
// =====================================================
//分治法求最近对 中间2d对称区的算法
void Middle(const NList & L,CloseNode & cnode,int mid,int midX){
int i,j;
int d = sqrt(cnode.space);
i=mid;
while(i>=0&&L.data[i].x>=(midX-d)){
j=mid;
while(L.data[++j].x<=(midX+d)&&j<=L.count){//1,j++ 2<=,>=
if(L.data[j].y<(L.data[i].y-d)||L.data[j].y>(L.data[i].y+d))
continue;
double space = Distinguish2(L.data[i],L.data[j]);
if(cnode.space>space){
cnode.a=L.data[i];
cnode.b=L.data[j];
cnode.space=space;
}
}
--i;
}
}
// ----------------------------------------------
//分治法求最近对
void DivideAndConquer(const NList &L,CloseNode & closenode,int begin,int end){
if((end-begin+1)<4) BruteForce(L,closenode,begin,end);
else{
int mid = (begin+end)/2;
int midX = L.data[mid].x;
DivideAndConquer(L,closenode,begin,mid);
DivideAndConquer(L,closenode,mid+1,end);
Middle(L,closenode,mid,midX);
}
}
//==================================================
// ------------------------------------------------
int main(){
NList list;
CloseNode closenode;
closenode.space = 10000;
create(list);
cout<<"各点坐标为:"<<endl;
for(int i=0;i<list.count;++i)
cout<<"X="<<list.data[i].x<<" Y="<<list.data[i].y<<"\n";
BruteForce(list,closenode,0,list.count-1);
cout<<"用蛮力法求最近对:"<<endl;
cout<<"最近对为点 ("<<closenode.a.x<<","<<closenode.a.y<<")和点("<<closenode.b.x<<","<<closenode.b.y<<")\n"<<"最近距离为: "<<closenode.space<<endl;
cout<<"===================================================================="<<endl;
cout<<"===================================================================="<<endl;
cout<<"用分治法求最近对:"<<endl;
MergeSort(list);
cout<<"经过归并排序后的各点:"<<endl;
for(int j=0;j<list.count;++j)
cout<<"X="<<list.data[j].x<<" Y="<<list.data[j].y<<"\n";
DivideAndConquer(list,closenode,0,list.count-1);
cout<<"最近对为点 ("<<closenode.a.x<<","<<closenode.a.y<<")和点("<<closenode.b.x<<","<<closenode.b.y<<")\n"<<"最近距离为: "<<closenode.space<<endl;
return 0;
}
加点注释哦
分治太难，给你个暴力破解法（显然会超时），分治只能请教真正的C语言高手了
分治是什么
一种算法
