分治算法簡介
在計算機科學(xué)中，分治法是一種很重要的算法。字面上的解釋是“分而治之”鲫趁，簡單來說就是把一個問題分解為很多的子問題，然后再通過子問題的合并來獲得最終的結(jié)果捌锭。如：排序算法（歸并排序，快速排序）罗捎，傅立葉變換都屬于典型的分治算法的案例观谦。
基本思路
將一個個大問題，拆分成小問題桨菜，然后各個擊破豁状，把小問題的答案再合并成最終的答案。
如果一個問題能夠被拆成k個小問題倒得，并且這k個小問題的答案能夠合并成最終的答案泻红，那么就可以用分治算法來解決。
實際案例
案例一（歸并排序）
加入有一個無序的數(shù)組{5,4,3,2,1,6,8,7,10,1},要對他們進行歸并排序：
1.把數(shù)組持續(xù)拆分屎暇，直到只剩下一個元素為止
2.遞歸的合并拆分后的數(shù)組承桥，直到最后得到排序后的結(jié)果
代碼實現(xiàn)：
1.拆分?jǐn)?shù)組：
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.合并數(shù)組：
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;
}
案例二（快速排序）
從數(shù)列中挑出一個元素，稱為 “基準(zhǔn)”（pivot）;
重新排序數(shù)列根悼，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面凶异，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后挤巡，該基準(zhǔn)就處于數(shù)列的中間位置剩彬。這個稱為分區(qū)（partition）操作；
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序矿卑；
遞歸的最底部情形喉恋，是數(shù)列的大小是零或一，也就是永遠都已經(jīng)被排序好了母廷。雖然一直遞歸下去轻黑，但是這個算法總會退出，因為在每次的迭代（iteration）中琴昆，它至少會把一個元素擺到它最后的位置去氓鄙，具體步驟：
1.拆分?jǐn)?shù)組
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.分區(qū)操作
public int partition(int[] arr, int left, int right) { // 分區(qū)操作
int pivot = left, // 設(shè)定基準(zhǔn)值（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 ),這種方式就是分治算法复颈。
假如如下圖，有下列密集點：
假如這些點已經(jīng)按照x軸進行排序诸狭，我們可以畫一條垂直的直線券膀，把點集分成兩半君纫，PL,PR,因此可以得出，整個點擊最近的兩個點一定是PL中最小的兩個點芹彬，和PR中距離最小的兩個點蓄髓，和PL中一個點和PR中一個點組成的一條最小距離的直線。正如下圖所示舒帮，整個點擊最小距離的點一定是dL,dR,和dc中最小的那一條会喝。
具體實現(xiàn)步驟：
1.通過不斷的遞歸從中拆分，直到左右兩邊只剩下兩個點為止玩郊。這樣的話肢执，dL，dR的距離直接通過計算可以得出,因此,可以設(shè)置 s = min(dL,dR);
2.計算dc的最短距離译红，由于我們知道中線的位置预茄，因此只需要計算 (mid-s)和(mid+s)中所有點的距離即可。
3.最后整個區(qū)域的最小值則為min(dL,dR,dC)
具體代碼實現(xiàn)：
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;
}
}
