分治法分治法

分治法是一种算法思想，顾名思义就是分而治之的意思。把一个很难解决的问题划分成许多小问题进行解决然后合并。在计算机算法设计与分析中，分治法的应用离不开递归技术。
递归，是指子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。递归有两个基本要素：
①边界条件，即确定递归到何时终止，也称为递归出口。
②递归模式，即大问题是如何分解为小问题的，也称为递归体。
举个例子，斐波那契数列：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版