分治法是一种算法思想，顾名思义就是分而治之的意思。把一个很难解决的问题划分成许多小问题进行解决然后合并。在计算机算法设计与分析中，分治法的应用离不开递归技术。
递归，是指子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。递归有两个基本要素：
①边界条件，即确定递归到何时终止，也称为递归出口。
②递归模式，即大问题是如何分解为小问题的，也称为递归体。
举个例子，斐波那契数列：f(n)=f(n-1)+f(n-2)(n>2) f(0)=1;f(1)=1;
java代码实现如下：
static int Fibonacci(int sequence){
if(sequence <= 0){
return 0;
}else if(sequence == 1){
return 1;
}else if(sequence == 2){
return 2;
}else{
return Fibonacci(sequence-2)+Fibonacci(sequence-1);
}
}
解释完递归再回来讲分治法，分治法在每一层递归上都有3个步骤：
⑴分解。将原问题分解成一系列子问题。
⑵求解。递归地求解各子问题。若子问题足够小，则直接求解。
⑶合并。将子问题的解合并成原问题的解。
那么用分治法来实现两个具体的问题案例。
⒈用分治法实现排序，即归并排序。
首先，分解。将待排序的数组一份为二。
接着，求解。对子数组进行递归排序。
最后，合并。合并两个有序的子数组为一个有序的数组。
java代码：
int[] numMerge = {-101, -12, -13, 45, -23, 33, -41, -1, 13};
mergeSort(numMerge,0,numMerge.length-1);
/**
* 分治法实现排序，即归并排序
* @param Array
*/
static void mergeSort(int[] Array, int left, int right){
if(left < right){
int mid = (left + right)/2;
mergeSort(Array, left, mid);
mergeSort(Array, mid+1, right);
mergeByAsc(Array, left, right);
}
}
/**
* 合并，默认左边右边都是升序的
* @param Array
* @param left
* @param right
*/
static void mergeByAsc(int[] Array, int left, int right){
int mid = (left + right)/2;
//左边的升序数组
int leftTemp[] = new int[mid - left + 1];
for(int i = 0, j = left; i < leftTemp.length; i++,j++){
leftTemp[i] = Array[j];
}
//右边的升序数组
int rightTemp[] = new int[right - mid];
for(int i = 0, j = mid+1; i < rightTemp.length; i++,j++){
rightTemp[i] = Array[j];
}
int i=0,j=0;
//按照升序合并左右两边数组为一个升序数组
for(int k=left; k<=right; k++){
if(i == leftTemp.length){
Array[k] = rightTemp[j];
j++;
}else if(j == rightTemp.length){
Array[k] = leftTemp[i];
i++;
}else if(leftTemp[i] > rightTemp[j]){
Array[k] = rightTemp[j];
j++;
}else{
Array[k] = leftTemp[i];
i++;
}
}
}
其实，在合并的过程就是对其排序的过程。当两个子数组仅有一个元素的时候，就默认是有序的，因为就一个嘛，升序或降序都行。接着将两个子数组合并成一个的时候，就按照升序或降序来合并了。在仿照褚华、霍秋艳主编的《软件设计师教程》第5版中C语言版本来写的时候，发现一个bug，就是左边或右边数组的指针到最后一个元素并赋值后，后面指针变量还是加了1,循环到下一次判断的时候就会引起指针越界错误，所以我在前面就判断指针是否到达最后，以防这种错误发生。
⒉用分治法求解最大子段问题。
问题描述：给定n个整数组成的序列，求其中某连续序列相加的和的最大值。比如1，-1,4,5,6，-3,2，最大子段的和就是15.（4+5+6）
这个问题乍看起来有点棘手，比排序难了一点，因为想复杂了，第1个元素开始加后面的元素，然后第二个元素加后面的元素，循环再比较，啊，越来越复杂了。排序至少可以用最简单的冒泡来代替归并什么的算法。这个就没办法了啊。这时应该谨记分治法思想的核心，就是划分问题再解决、合并。
首先，分解。整数组成的序列分成两个子序列。
接着，求解。求解子序列的最大子段和（聪明的你肯定想到了递归）。
最后，合并。这里的合并与前面的归并排序的合并有稍稍不同，归并排序的合并只要把两个子数组直接合并处理就行，而这里是求最大子段和，最大子段和的情况有3种：
①左子段的和。比如1,2,3，-1，-2，-3的左子段1,2,3的和就是最大子段和。
②右子段的和。比如-1,-2,-3，1，2，3的右子段1,2,3的和就是最大子段和。
③左右中间连接处的和。比如-1，-2,3,4，-2，-1左子段-1，-2,3的3加上右子段的4，-2，-1的4就是最大子段和。
java代码：
int[] nums = {-101, -12, -13, -45, -23, -33, -41, -1};
System.out.println(maxSubSum(nums,0,nums.length-1));
/**
* 用分治法求解最大字段和问题。
* 对一个整型数组，求解数组中子段和最大值
* @param Array
* @param left
* @param right
* @return
*/
static int maxSubSum(int[] Array, int left, int right){
int sum = 0;
int i;
if(left == right){
sum = Array[left];
}else{
/* 从left和right的中间分解数组
* 求得左子段的最大子段和
* 求得右子段的最大子段和
* */
int center = (left + right)/2;
int leftSum = maxSubSum(Array, left, center);
int rightSum = maxSubSum(Array, center + 1, right);
/*求得左右子段中间连接部分的最大字段和*/
int s1 = Integer.MIN_VALUE;
int lefts = 0;
for(i = center; i >= left; i--){
lefts += Array[i];
if(lefts > s1){
s1 = lefts;
}
}
int s2 = Integer.MIN_VALUE;
int rights = 0;
for(i = center + 1; i <= right; i++){
rights += Array[i];
if(rights > s2){
s2 = rights;
}
}
sum = s1 + s2;
if(sum < leftSum){
sum = leftSum;
}
if(sum < rightSum){
sum = rightSum;
}
}
return sum;
}
引用：褚华、霍秋艳主编的《软件设计师教程》第5版
