分治算法简介
在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，简单来说就是把一个问题分解为很多的子问题，然后再通过子问题的合并来获得最终的结果。如：排序算法（归并排序，快速排序），傅立叶变换都属于典型的分治算法的案例。
基本思路
将一个个大问题，拆分成小问题，然后各个击破，把小问题的答案再合并成最终的答案。
如果一个问题能够被拆成k个小问题，并且这k个小问题的答案能够合并成最终的答案，那么就可以用分治算法来解决。
实际案例
案例一（归并排序）
加入有一个无序的数组{5,4,3,2,1,6,8,7,10,1},要对他们进行归并排序：
1.把数组持续拆分，直到只剩下一个元素为止
2.递归的合并拆分后的数组，直到最后得到排序后的结果
代码实现：
1.拆分数组：
public static int[] sort(int[] arr,int left,int right){
int index = left + (right - left)/2;
if(left == right){
int[] temp = new int[1];
temp[0] = arr[left];
return temp;
} else{
return compareSort(sort(arr,left,index),sort(arr,index+1,right));
}
}
2.合并数组：
public static int[] compareSort(int[] arr1,int[] arr2){
int length = arr1.length + arr2.length;
int index1 = 0, index2 = 0;
int[] temp = new int[length];
int index = 0;
while(index1 < arr1.length && index2 < arr2.length){
if(arr1[index1] < arr2[index2]){
temp[index++] = arr1[index1++];
}else{
temp[index++] = arr2[index2++];
}
}
while(index1 < arr1.length){
temp[index++] = arr1[index1++];
}
while(index2 < arr2.length){
temp[index++] = arr2[index2++];
}
return temp;
}
案例二（快速排序）
从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去，具体步骤：
1.拆分数组
public int[] quickSort(int[] arr, int left, int right) {
int partitionIndex;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
2.分区操作
public int partition(int[] arr, int left, int right) { // 分区操作
int pivot = left, // 设定基准值（pivot）
index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
案例二（最近点问题）
假如平面上有N个散列的点，找到距离最短的两个点。正常方法是，计算每任意两个点之间的距离，这样的话，时间是N(N-1)/2,
也就是O(nn);但是有一种方法，对于密集的点，能够把效率提升为O(NlogN ),这种方式就是分治算法。
假如如下图，有下列密集点：
假如这些点已经按照x轴进行排序，我们可以画一条垂直的直线，把点集分成两半，PL,PR,因此可以得出，整个点击最近的两个点一定是PL中最小的两个点，和PR中距离最小的两个点，和PL中一个点和PR中一个点组成的一条最小距离的直线。正如下图所示，整个点击最小距离的点一定是dL,dR,和dc中最小的那一条。
具体实现步骤：
1.通过不断的递归从中拆分，直到左右两边只剩下两个点为止。这样的话，dL，dR的距离直接通过计算可以得出,因此,可以设置 s = min(dL,dR);
2.计算dc的最短距离，由于我们知道中线的位置，因此只需要计算 (mid-s)和(mid+s)中所有点的距离即可。
3.最后整个区域的最小值则为min(dL,dR,dC)
具体代码实现：
1.定义平面点的属性：
public class Points{
private double x,y;
public void setX(double x) {
this.x = x;
}
public double getX() {
return x;
}
public void setY(double y) {
this.y = y;
}
public double getY() {
return y;
}
}
2.递归拆分所有的点
public static double divPoints(Points[] points, int left, int right){
if(right - left == 1){
return distance(points[left],points[right]);
}else if(right - left == 2){
return distance(points[left],points[left+1],points[left+2]);
}else{
int mid = left + (right - left)/2;
double leftP = divPoints(points,left,mid);
double rightP = divPoints(points,mid,right);
double minLR = Math.min(leftP,rightP);
ArrayList<Points> dLeft = new ArrayList();
ArrayList<Points> dRight = new ArrayList();
for(int i = left; i <= right; i++){
if(i != mid){
if(points[i].getX() < points[mid].getX() && (points[mid].getX() - points[i].getX()) < minLR ){
dLeft.add(points[i]);
}else if(points[i].getX() >= points[mid].getX() && (points[i].getX() - points[mid].getX()) < minLR){
dRight.add(points[i]);
}
}
}
for(int i = 0;i<dLeft.size();i++){
for(int j = 0;j<dRight.size();j++){
double mLR = distance(dLeft.get(i),dRight.get(j));
if(mLR < minLR){
minLR = mLR;
}
}
}
return minLR;
}
}
