分治算法簡(jiǎn)介
在計(jì)算機(jī)科學(xué)中，分治法是一種很重要的算法。字面上的解釋是“分而治之”，簡(jiǎn)單來(lái)說就是把一個(gè)問題分解為很多的子問題，然后再通過子問題的合并來(lái)獲得最終的結(jié)果。如：排序算法（歸并排序，快速排序），傅立葉變換都屬于典型的分治算法的案例。
基本思路
將一個(gè)個(gè)大問題，拆分成小問題，然后各個(gè)擊破，把小問題的答案再合并成最終的答案。
如果一個(gè)問題能夠被拆成k個(gè)小問題，并且這k個(gè)小問題的答案能夠合并成最終的答案，那么就可以用分治算法來(lái)解決。
實(shí)際案例
案例一（歸并排序）
加入有一個(gè)無(wú)序的數(shù)組{5,4,3,2,1,6,8,7,10,1},要對(duì)他們進(jìn)行歸并排序：
1.把數(shù)組持續(xù)拆分，直到只剩下一個(gè)元素為止
2.遞歸的合并拆分后的數(shù)組，直到最后得到排序后的結(jié)果
代碼實(shí)現(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ù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）;
重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；
遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)退出，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去，具體步驟：
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;
}
案例二（最近點(diǎn)問題）
假如平面上有N個(gè)散列的點(diǎn)，找到距離最短的兩個(gè)點(diǎn)。正常方法是，計(jì)算每任意兩個(gè)點(diǎn)之間的距離，這樣的話，時(shí)間是N(N-1)/2,
也就是O(nn);但是有一種方法，對(duì)于密集的點(diǎn)，能夠把效率提升為O(NlogN ),這種方式就是分治算法。
假如如下圖，有下列密集點(diǎn)：
假如這些點(diǎn)已經(jīng)按照x軸進(jìn)行排序，我們可以畫一條垂直的直線，把點(diǎn)集分成兩半，PL,PR,因此可以得出，整個(gè)點(diǎn)擊最近的兩個(gè)點(diǎn)一定是PL中最小的兩個(gè)點(diǎn)，和PR中距離最小的兩個(gè)點(diǎn)，和PL中一個(gè)點(diǎn)和PR中一個(gè)點(diǎn)組成的一條最小距離的直線。正如下圖所示，整個(gè)點(diǎn)擊最小距離的點(diǎn)一定是dL,dR,和dc中最小的那一條。
具體實(shí)現(xiàn)步驟：
1.通過不斷的遞歸從中拆分，直到左右兩邊只剩下兩個(gè)點(diǎn)為止。這樣的話，dL，dR的距離直接通過計(jì)算可以得出,因此,可以設(shè)置 s = min(dL,dR);
2.計(jì)算dc的最短距離，由于我們知道中線的位置，因此只需要計(jì)算 (mid-s)和(mid+s)中所有點(diǎn)的距離即可。
3.最后整個(gè)區(qū)域的最小值則為min(dL,dR,dC)
具體代碼實(shí)現(xiàn)：
1.定義平面點(diǎn)的屬性：
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.遞歸拆分所有的點(diǎn)
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;
}
}
