分治算法

分治算法简介

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，简单来说就是把一个问题分解为很多的子问题，然后再通过子问题的合并来获得最终的结果。如：排序算法（归并排序，快速排序），傅立叶变换都属于典型的分治算法的案例。

基本思路

将一个个大问题，拆分成小问题，然后各个击破，把小问题的答案再合并成最终的答案。
如果一个问题能够被拆成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 ),这种方式就是分治算法。
假如如下图，有下列密集点：

WX20190412-104120@2x.png

假如这些点已经按照x轴进行排序，我们可以画一条垂直的直线，把点集分成两半，PL,PR,因此可以得出，整个点击最近的两个点一定是PL中最小的两个点，和PR中距离最小的两个点，和PL中一个点和PR中一个点组成的一条最小距离的直线。正如下图所示，整个点击最小距离的点一定是dL,dR,和dc中最小的那一条。

WX20190412-104749@2x.png

具体实现步骤：
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;
        }
    }