【算法】递归与分治策略——二分查找、归并排序、快排、最接近点对问题_递归法最接近点对问题

递归

递归：直接或间接的调用自身的算法称为递归算法
实现递归调用的关键是为算法建立递归调用工作栈。通常，在一个算法中调用另一算法时，系统需要在运行被调用算法之前先完成3件事：

1. 将所有实参指针，返回地址等信息传递给被调用算法；
2. 为被调用算法的局部变量分配存储区；
3. 将控制转移到被调用算法的入口；

在从被调用算法返回调用算法时，系统也相应地要完成3件事：

1. 保存被调用算法的计算结果；
2. 释放分配给被调用算法的数据区；
3. 依照被调用算法保存的返回地址将控制转移到调用算法；

原则: 后调用先返回
上述算法之间的信息传递和控制转移必须通过栈来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每调用一个算法，就为它在栈顶分配一个存储区，每退出一个算法，就释放它在栈顶的存储区。当前正在运行的算法的数据一定在栈顶。

由于递归算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便，然而，递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。若在程序中消除算法的递归调用，使其转化为非递归算法。通常，消除递归采用一个用户定义的栈来模拟系统的递归调用工作栈，从而达到将递归算法改为非递归算法的目的。仅仅是机械地模拟还不能达到减少计算时间和存储空间的目的。因此，还需要根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。

分治

分治法：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

二分搜索技术

二分搜索算法时运用分治策略的典型例子。
给定已排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x

二分搜索算法很好的利用了“已排序好”的这个条件，每次查找根据条件缩小范围，递归求解

/**
     * 给定已排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x
     * @param arr
     * @param x
     * @param n
     * @return
     */
    public static int binarySearch(int []arr,int x,int n){
        int left=0;
        int right=n-1;
        while (left <=right ){
            int middle=(right -left +1 )/2+left ;
            if(x==arr[middle ]) return middle ;
            if(x>arr[middle ])  left =middle +1;
            else
                right =middle -1;
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

可以看出，每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O（logn）次，循环体内运算需要O（1）时间，因此，整个算法在最坏情况下的计算时间复杂性为O（logn）

归并排序

归并排序很好的利用了递归，将待排序集合一分为二，直至待排序集合只剩下1个元素为止。然后不断合并2个排好序的数组段。

 /**
     * 归并排序
     * 平均时间复杂度：O（nlog2 n） 最坏时间复杂度：O（nlog2 n）
     * 空间复杂度：0（n）
     * @param <T>
     */
    private static <T extends Comparable <T>> void merge(T []arr,int gap) {
        int left1 = 0;
        int right1 = left1 + gap;
        int left2 = right1 + 1;
        int right2 = left2 + gap - 1 > arr.length - 1 ? arr.length - 1 : left2 + gap - 1;
        T[] brr = (T[]) new Comparable[arr.length];
        int j = 0;//控制新数组的下标
        //有两个归并段
        while (left2 < arr.length) {
            while (left1 <= right1 && left2 <= right2) {
                if (arr[left1].compareTo(arr[left2]) < 0) {
                    brr[j++] = arr[left1++];
                } else {
                    brr[j++] = arr[left2++];
                }
            }
            if (left1 > right1) {
                while (left2 <= right2) {
                   brr[j++] = arr[left2++];
                }
            }
            if (left2 > right2) {
                while (left1 <= right1) {
                   brr[j++] = arr[left1++];
               }
            }
            left1 = right2 + 1;
            right1 = left1 + gap - 1;
            left2 = right1 + 1;
            right2 = left2 + gap - 1 > arr.length - 1 ? arr.length - 1 : left2 + gap - 1;
        }
        //只有一个归并段
        while (left1 <=arr .length -1){
            brr [j++]=arr [left1 ++];
        }
        System .arraycopy(brr ,0,arr ,0,arr .length );
    }
    public static<T extends Comparable <T>> void mergeSort(T []arr){
        for(int i=1;i<arr .length ;i*=2){
            merge(arr ,i);
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

上周在java算法与分析中看到另一种解法；

递归排序法

MergeSort

这是调用函数递归口，复制出一个和ar一样的br，然后开始调用函数

public static void MergeSort(int []ar)
    {
        int []br = new int[ar.length];
        MergePass(ar,br,0,ar.length-1);
    }
1
2
3
4
5

MergePass

并归函数的递归调用函数：
找到中位数，然后将原数组划分成两部分，左边先进行递归，右边再递归，然后调用Merge函数，然后拷贝到原数组就好了。

乍一看似乎很简单的实现了，仔细一想为什么
MergePass(ar,br,left,mid); // left
MergePass(ar,br,mid+1,right); // right;
这样简单的两句函数就可以实现递归排序，递归思想一直是我觉得比较难理解的思想；再进行调试时，我终于理解了是如何递归再排序的。

整个函数中只有Merge函数进行了大小比较排序，所以MergePass只是起到了划分区域的作用，每个区域的个数为1时，停止划分，递归结束，开始进行归并，然后再进行下一次的递归调用。先调用的后递归。

  public static void MergePass(int []ar,int []br,int left,int right)
    {
        if(left < right)// left = 1  , right = 1
        {
            int mid = (right - left)/2 + left;
            MergePass(ar,br,left,mid); // left
            MergePass(ar,br,mid+1,right); // right;
            Merge(br,ar,left,mid,right);
            Copy_Ar(ar,br,left,right);
        }
    }
1
2
3
4
5
6
7
8
9
10
11

Merge

Merge函数做的事情可以理解为合并，将左半部分和右半部分合并；
合并的规则就是比较大小，按照大小顺序进行排序，
然后将没排到的元素顺次放进去

第一个循环退出的条件就是i>m或者j>right
如果是i>m退出，就说明左边先遍历完；则将右边没遍历完的再放到dsi数组
如果是j>right退出，就说明右边先遍历完；则将左边没遍历完的放到dsi数组

 public static void Merge(int []dsi,int []src,int left ,int m, int right)
    {
        int i = left, j = m+1;
        int k = left;
        while(i<=m && j<=right)
        {
            dsi[k++] = src[i] < src[j]? src[i++]:src[j++];
        }
        while(i<=m)
        {
            dsi[k++] = src[i++];
        }
        while(j<=right)
        {
            dsi[k++] = src[j++];
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

非递归法

非递归法可以说是上下来回倒：
创建一个br数组，和ar来回倒，
具体怎么个倒法？
可以从递归法来获取灵感：递归法后调用的先递归，所以当划分成规模只有一个个数时，开始执行；所以非递归法我们可以由小到大来划区域排序。

第一次将元素个数设为1（s）；
这个元素个数指的是半区域，比如左（右）半部分区域为1；
然后进行NiceMergePass，将排序好的元素复制到br中。

第二次将元素个数设为2；
这次是从br复制到ar；

（4、8、16……）是2的幂
……

NiceMergePass具体是怎么排序的呢？

一个数组的个数不是奇数就是偶数，所以可能在第一次两两划分时剩下一个或者没有剩下；
当划分完后，两两组队就可以直接进行Merge排序，剩下的元素则需要复制到新数组里。

问题又来了，怎么复制，最后的一直复制吗？
1，2，3,4，5,6 假如有六个元素，是2的幂，在第二次s=2时，【1,2 3,4】这两组拼成一组，余下的另一组直接复制；
这就是我第一次没想通的问题，我觉得数不是奇数就是偶数，而肯定最后剩下的是一个元素，只需要复制一个就好了，而有可能有一组数组剩下，所以这里的复制要用for循环。

我们可以看到下一次合并时，【1,2，3,4】【5,6】是这两个数组合并，因为数据不够所以不是四个四个合并了，所以当n（最后一个元素的下标）》=i+s时，就是要剩下的数组一起合并。

 public static void NiceMergeSort(int []arr){
        int []br=new int[arr .length ];
        int n=arr .length -1;
        int s=1;
        while (s<n){
            NiceMergePass(br,arr,s,n);
            s+=s;
            NiceMergePass(arr ,br ,s,n);
            s+=s;
        }
    }

    public static void NiceMergePass(int []dis,int []src,int s,int n){
        System.out.printf("s=%d\n",s);
        int i=0;
        for(i=0;i+2*s-1<=n;i=i+2*s){//是二次幂
            Merge(dis ,src ,i,i+s-1,i+2*s-1);
        }
        if(n>=i+s){//当剩下的集合要和后面的一起合并
            Merge(dis ,src ,i,i+s-1,n);
        }else {//
            for(int j=i;j<=n;j++){
                dis [j]=src [j];
            }
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

快排

排序的基本思想是：

1. 分解：以ar[0]为基准元素，将数组化为三个部分，{a[0,p-1],a[p],a[p+1,ar.length-1]},其中p为ar[0]元素的下标
   特点：

• 使得第一部分的任何元素小于等于a[0]；
  第三部分的任何元素大于a[0]；
• a[0]的位置确定，再进行后续的递归排序位置不会变动。

2. 递归求解：通过递归调用快速排序算法，分别第一部分 盒第三部分排序
3. 合并：将三个部分合并

递归法

分解函数

让第一个元素a0先和最右边的比较，直到有小于等于a0的元素ar，把ar的值赋给al，也就是把它放到左边，然后比较左边直到有大于a0的元素，把它放到右边。最后left下标和right下标都指向a0元素的下标。
**两头开花，**左右两边都进行比较。

   public static int Partition(int []ar,int left,int right){
        int tmp=ar[left ];
        while (left <right ) {
            while (left < right && ar[right] > tmp) --right;
           // if (left < right) {
                ar[left] = ar[right];
            //}
            while(left <right && ar [left ]<=tmp ) ++left ;
           // if(left <right ){
                ar [right  ]=ar [left ];
           // }
        }
        ar[left ]=tmp ;
        return left ;//right
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

合并

public static void QuickSort(int ar[],int left,int right){
        if(left <right ){
            int pos=Partition(ar ,left ,right );
            QuickSort(ar ,left ,pos-1);
            QuickSort(ar, pos+1, right);
        }
    }
1
2
3
4
5
6
7

非递归法

在设计非递归法时，要记得可以借助一些栈，队列等帮助我们实现

在递归算法时，发现每次的递归调用只是改变左右坐标的值，所以在非递归的算法时要着重关注坐标的变化。

下面算法将借助队列来实现，将左右坐标分辨入栈，然后在循环中出栈，队列的性质先进先出刚好符合我们左右坐标的顺序，然后调用分解函数，继续将两个部分的坐标入栈

public static void NiceQuickSort(int []ar,int left,int right){
        Queue <Integer > qu=new LinkedList<Integer>();
        qu.offer(left );
        qu.offer(right );
        while (!qu.isEmpty() ){
            left =((LinkedList<Integer>) qu).pollFirst() ;
            right =((LinkedList<Integer>) qu).pollFirst() ;
            int pos=Partition(ar, left, right);
            if(left <pos-1){
                qu.offer(left );
                qu.offer(pos-1);
            }
            if(pos+1<right ){
                qu.offer(pos+1);
                qu.offer(right );
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

递归找第k小

找出数组中的第一小和第二小想必是简单的，遍历可得

 /**
     * 找数组中的第一小和第二小
     * @param ar
     */
    public static void SelectMin(int []ar){
        if(ar .length <2)return ;
        int min1=ar[0]<ar[1]?ar [0]:ar [1];
        int min2=ar[0]>ar[1]?ar [0]:ar[1];
        for(int i=2;i<ar .length ;i++){
            if(ar [i]<min1 ){
                min2 =min1 ;
                min1 =ar [i];
            }else if(ar [i]<min2 ){
                min2 =ar [i];
            }
        }
        System.out.println(min1 );
        System.out.println(min2 );
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

那么如何找到第k小

第一个想到的方法应该是找第几小就遍历几次，而这样的时间复杂度挺大，效率不高

下面我们根据上面分解算法的实现，来实现递归求解
分解算法可以将数组按照大小分为两部分，然后当k>pos时只需要在后半部分查找；小于等于时在前半部分查找。
而要实现这种算法我们需要关注k，因为在后半部分时控制台传入的k值和我们右半部分实际的k值不等了，这个k是逻辑下标，比如在原本的大数组是第七小，在后半段数组中就是第二小
当数组个数为1且k==1时返回

 public static int Select_KMin(int []ar,int left,int right,int k){

        return Select_K(ar ,0,ar .length -1,k);
    }
    //k是逻辑下标，index是物理坐标
    //这个方法的时间复杂度很小《O（n）
    //因为化区域查找
    public static int Select_K(int []ar,int left,int right,int k){
        if(left ==right && k==1)return ar [left ];
        int index=Partition(ar ,left ,right ) ;
        int pos=index -left +1;
        if(k<=pos){
            return Select_K(ar ,left ,index ,k);
        }else {
            return Select_K(ar ,index +1,right ,k-pos);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第二种分解函数

和上面的i，j控制的分解函数不一样，这个是只用i控制，所以不同于上一个两头开花，这个是单向遍历
为什么要写这个方法呢？数组可以从i++，j–就是每个元素有前驱和后继，而只有i++控制后继，什么结构有这个性质呢？单链表，所以可以用到单链表排序

 public static int OnePartition(int []ar,int left,int right){
        int temp=ar[left ];
        int i=left ,j=i+1;
        while (j<=right ){
            if(ar [j]<=temp ){
                i++;
                if(i!=j){
                    swap_ar(ar,i,j);
                }
            }
            j++;
        }
        swap_ar(ar, left, i);
        return i;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

链表中实现

public static ListNode ListPartition(ListNode left, ListNode right) {
        int tmp = left.Value;
        ListNode low = left, h = low.Next;
        while (h != right) {
            if (h.Value <= tmp) {
                low = low.Next;
                if (low != h) {
                    swap_list(low, h);
                }
            }
            h = h.Next;
        }
        swap_list(left, low);
        reutrn low;
    }

    public static void ListQuickSort(ListNode left, ListNode right) {
        if (left != right) {
            ListNode pos = ListPartition(left, right);
            ListQuickSort(left, pos);
            ListQuickSort(pos.Next, right);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

随机数分解函数

 public static int RandPartition(int[] ar, int left, int right) {
        Random rad = new Random();
        int index = rad.nextInt(right - left + 1) + left;
        int tmp = ar[left];
        ar[left] = ar[index];
        ar[index] = tmp;
        return Partition(ar, left, right);
    }

1
2
3
4
5
6
7
8
9

最接近点对问题

给定平面n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间距离最小。
用遍历求出每两个点之间的距离的时间复杂度是O（n^2）
分治思想求解的时间复杂度是O（nlogn）

一维的情况下：可以由之前的分解函数继续想
算出中位数，把空间分成三个区域：中位数之前，中位数，中位数之后
把第一个和第三个区域的最小值算出，然后将第一个区域的最大值与第二个区域的最小值相减，比较这三个之间的差哪个更小。

 static final int maxint = 0x7fffffff;
    public static int Cpair(int []ar,int left,int right){
        if(right -left <1)return maxint ;//当只有一个或者没有元素时直接返回
        int k=(right -left +1)/2+left ;
        Select_K(ar ,left ,right ,k);
        int index=left +k-1;

        int d1=Cpair(ar ,left ,index );
        int d2=Cpair(ar ,index +1,right );
        int maxs1=MaxS1(ar ,left ,index );
        int mins2=MinS2(ar,index +1,right );
        return Min3C(d1,d2,mins2 -maxs1 );
    }
    private static int MaxS1(int[] ar, int left, int index) {
        return ar[index ];
    }

    private static int MinS2(int[] ar, int index, int right) {
        int temp=ar [index ];
        for(int i=index +1;i<right ;i++){
            if(ar[i]<temp ){
                temp =ar[i];
            }
        }
        return temp ;
    }
    private static int Min2C(int a,int b){
        return a<b?a:b;
    }

    private static int Min3C(int d1, int d2, int c) {
        return Min2C(Min2C(d1,d2),c );

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35