一、算法介绍

分治算法是用了分治思想的一种算法，什么是分治？

字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

举个栗子：

二、基本原理

分治模式中，我们递归地求解一个问题，在每层递归中应用如下三个步骤：

• 分解（Divide)步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
• 解决(Conquer)步骤递归地求解出子问题。如果子问题规模足够小，则停止递归，直接求解。
• 合并（Combine）步骤将子问题的解合并为原问题的解。

三、应用场景

运用分治策略解决的问题一般来说具有以下特点：

• 原问题可以分解为多个子问题

这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。

• 原问题在分解过程中，递归地求解子问题

由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，应能够直接求解。

• 在求解并得到各个子问题的解后

应能够采用某种方式、方法合并或构造出原问题的解。

不难发现，在分治策略中，由于子问题与原问题在结构和解法上的相似性，用分治方法解决的问题，大都采用了递归的形式。

在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想。

四、时间复杂度

分治算法的时间复杂度分析我们可以用递推公式和递归树。

一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。

设分解阀值n0=1，且ADHOC§解规模为1的问题耗费1个单位时间。

再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。

用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：

T（n）= k T(n/m)+f(n)

通过迭代法求得方程的解：

递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当 mi≤n由此可求得起时间复杂度为 O（nlogn）。

五、经典问题

（1）二分搜索（查找）

（2）大整数乘法

（3）Strassen矩阵乘法

（4）棋盘覆盖

（5）归并排序

（6）快速排序

（7）线性时间选择

（8）最接近点对问题

（9）循环赛日程表

（10）汉诺塔

六、算法实战

二分查询

二分查找是一种在每次比较之后将查找空间一分为二的算法，通过有序的区间可以直接确定结果在哪个区间，所以分的两个区间只需要计算其中一个区间，然后继续进行一直到结束。

public int searchInsert(int[] nums, int target) {
  if(nums[0]>=target)return 0;//剪枝
  if(nums[nums.length-1]==target)return nums.length-1;//剪枝
  if(nums[nums.length-1]<target)return nums.length;
  int left=0,right=nums.length-1;
  while (left<right) {
    int mid=(left+right)/2;
    if(nums[mid]==target)
      return mid;
    else if (nums[mid]>target) {
      right=mid;
    }
    else {
      left=mid+1;
    }
  }
  return left;
}

快速排序

快排每一趟会选定一个数，将比这个数小的放左面，比这个数大的放右面，然后递归分治求解两个子区间，当然快排因为在分的时候就做了很多工作，当全部分到最底层的时候这个序列的值就是排序完的值，这是一种分而治之的体现。

public void quicksort(int [] a,int left,int right)
{
  int low=left;
  int high=right;
  //下面两句的顺序一定不能混，否则会产生数组越界！！！very important！！！
  if(low>high)//作为判断是否截止条件
    return;
  int k=a[low];//额外空间k，取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。
  while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。
  {
    while(low<high&&a[high]>=k)//右侧找到第一个小于k的停止
    {
      high--;
    }
    //这样就找到第一个比它小的了
    a[low]=a[high];//放到low位置
    while(low<high&&a[low]<=k)//在low往右找到第一个大于k的，放到右侧a[high]位置
    {
      low++;
    }
    a[high]=a[low];			
  }
  a[low]=k;//赋值然后左右递归分治求之
  quicksort(a, left, low-1);
  quicksort(a, low+1, right);		
}

归并排序(逆序数)

快排在分的时候做了很多工作，而归并就是相反，归并在分的时候按照数量均匀分，而合并时候已经是两两有序的进行合并的，因为两个有序序列O(n)级别的复杂度即可得到需要的结果。而逆序数在归并排序基础上变形同样也是分治思想求解。

private static void mergesort(int[] array, int left, int right) {
  int mid=(left+right)/2;
  if(left<right)
  {
    mergesort(array, left, mid);
    mergesort(array, mid+1, right);
    merge(array, left,mid, right);
  }
}

private static void merge(int[] array, int l, int mid, int r) {
  int lindex=l;int rindex=mid+1;
  int team[]=new int[r-l+1];
  int teamindex=0;
  while (lindex<=mid&&rindex<=r) {//先左右比较合并
    if(array[lindex]<=array[rindex])
    {
      team[teamindex++]=array[lindex++];
    }
    else {    
      team[teamindex++]=array[rindex++];
    }
  }
  while(lindex<=mid)//当一个越界后剩余按序列添加即可
  {
    team[teamindex++]=array[lindex++];

  }
  while(rindex<=r)
  {
    team[teamindex++]=array[rindex++];
  } 
  for(int i=0;i<teamindex;i++)
  {
    array[l+i]=team[i];
  }
}

汉诺塔

汉诺塔的传说

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

汉诺塔游戏的演示和思路分析:

考虑最简单情况n=2，三根柱子分别为A、B、C，此时，在A上有2片金片(假设从小到大依次为1,2)。

那么我们的解决步骤可以归结为如下：

1. 先把A上1号金片移至B。
2. 再把A上2号金片移至C。
3. 再把B上1号金片移至C。

考虑n增大的情况：

1. 先把A上从1到n-1号金片移至B。
2. 再把A上N号金片移至C。
3. 再把B上从1到n-1号金片移至C。

可以看到递归的影子，要解决n个，先解决n-1个，可以分治为n=2的最简单情况并加以解决。

package com.qf.math;

public class Hanoitower {
    public static void main(String[] args) {
        hanoitower(4,'A','B','C');
    }

    public static void hanoitower(int num,char a,char b,char c){
        if (num==1){
            //盘数为1，做一次搬迁，从A移动到C柱
            System.out.println("第1个盘从"+a+"移动到"+c+"盘");
        }else{
            //盘数大于1
            //先从a盘最上面的盘值最下面的盘之间的所有盘，移动到b盘，C盘作为中间盘
            hanoitower(num-1,a,c,b);

            //把最底下的那个盘，从a盘移动到c盘
            System.out.println("第"+num+"个盘从"+a+"移动到"+c+"盘");

            //把b盘的所有盘，移动到c盘上
            hanoitower(num-1,b,a,c);
        }

    }
}

最大子序列和

最大子序列和的问题我们可以使用动态规划的解法，但是也可以使用分治算法来解决问题，但是最大子序列和在合并的时候并不是简单的合并，因为子序列和涉及到一个长度的问题，所以正确结果不一定全在最左侧或者最右侧，而可能出现结果的区域为：

• 完全在中间的左侧
• 完全在中间的右侧
• 包含中间左右两个节点的一个序列

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

输出：6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

public int maxSubArray(int[] nums) {
    int max=maxsub(nums,0,nums.length-1);
    return max;
}
int maxsub(int nums[],int left,int right)
{
    if(left==right)
        return  nums[left];
    int mid=(left+right)/2;
    int leftmax=maxsub(nums,left,mid);//左侧最大
    int rightmax=maxsub(nums,mid+1,right);//右侧最大

    int midleft=nums[mid];//中间往左
    int midright=nums[mid+1];//中间往右
    int team=0;
    for(int i=mid;i>=left;i--)
    {
        team+=nums[i];
        if(team>midleft)
            midleft=team;
    }
    team=0;
    for(int i=mid+1;i<=right;i++)
    {
        team+=nums[i];
        if(team>midright)
            midright=team;
    }
    int max=midleft+midright;//中间的最大值
    if(max<leftmax)
        max=leftmax;
    if(max<rightmax)
        max=rightmax;
    return  max;
}

总结

分治法实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。 一定是先找到最小问题规模时的求解方法，然后考虑随着问题规模增大时的求解方法找到求解的递归函数式后（各种规模或因子），设计递归程序即可。