分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。
二、分治策略的基本思想简单来说，分治算法就是“分而治之”，即就是讲一个规模很大很复杂的问题分 成若干份相同或相似的更小的子问题，直到最后可以简单的直接求解，将所有子问题的解合并即得到原问题的解。
此处，需要注意：
- 子问题与原问题的性质相同
- 子问题必须可以独立求解
- 递归停止时，子问题必须能够直接求解
在分治算法中，假设原问题总规模为n，我们假设分解和合并所用时间为C(n)和D(n),假设W(x)为处理一个规模为x的问题所用的时间。每一个子问题是原问题规模的1/a。
如果原问题规模<=最小子问题的规模，既可以直接求解，那么其时间复杂度是一个常数。否则，W(n)=aW(n/a) C(n) D(n);
四、分治精髓分治法的精髓：
- 分--将问题分解为规模更小的子问题；
- 治--将这些规模更小的子问题逐个击破；
- 合--将已解决的子问题合并，最终得出“母”问题的解；
- 二分归并排序
- 汉诺塔
设计思想：
1、将规模为n的原问题划分为规模为n/2的子问题； 2、继续划分，划分至规模为n/4的，继续一直到规模为1，可以直接求解，这块分治就结束了； 3、从规模1到n/2依次陆续归并排好序的子数组，直到原始数组。
伪代（pseudocode）：
算法 MergeSort(A, p, r)
输入： 数组A[p......r]
输出：元素按从小到大排序的数组A
1.if p < r
2.then q <- (p r)/2 问题规模划分
3.MergeSort(A, p, q) 子问题1
4.MergeSort(A, q 1, r) 子问题2
5.Merge(A, p, q, r) 综合解
程序代码实现（Java实现）：
public static void mergeSort(int[] nums, int begin, int end){
int length = end - begin 1;
if(length <= 1){
return;
}
/*分*/
int mid = (begin end) / 2;
mergeSort(nums, begin, mid);
mergeSort(nums, mid 1, end);
/*治*/
merge(nums, begin, mid, end);
}
public static void merge(int[] nums, int begin, int mid, inr end){
if(mid>=end){
return;
}
int length = end - begin 1;
int [] temp = new int[length];
int k = 0;
int i = begin;
int j = mid 1;
while(i<=mid&&j<=end){
if(num[i]<num[j]){
temp[k] = num[i];
i ;
}else{
temp[k] = num[j];
j ;
}
k ;
}
/*传进来前部分已经排完序*/
if(i>mid){
while(j<=end){
temp[k] = nums[j];
j ;
k ;
}
}
if(j>end){
while(i<=mid){
temp[k] = num [i];
i ;
k
}
}
/*重新存进原数组*/
for(int m = 0; m < length; m ){
num[begin m] = temp[m];
}
}
图解：
时间复杂度分析：
假设原问题规模为n，二分归并排序最坏情况： W(n)=2W(n/2) n-1 其中子问题最小规模为1，W(1)=1;
5.2 汉诺塔W(n)=nlogn - n 1 时间复杂度为O(nlogn)
游戏介绍：
在汉诺塔游戏中，有三个塔座：A、B、C。几个大小各不相同，从小到大一次编号的圆盘，每个圆盘中间有一个小孔。最初，所有的圆盘都在A塔座上，其中最大的圆盘在最下面，然后是第二大，以此类推.
汉诺塔示意
该游戏的目的是将所有的圆盘从A塔移到B塔;C塔用来放置临时圆盘,游戏的规则如下:
- 一次只能移动一个圆盘
- 任何时候都不能将一个较大的圆盘压在较小的圆盘上面.
- 除了第二条限制,任何塔座的最上面的圆盘都可以移动到其他塔座上.
设计思想：始终将较小的盘当做是一个整体
游戏完成过程：
在上述图中：我们将盘子由小到大分别记为1，2，3，4，5。
先将1挪到B，2挪到C，再将1从B挪到C，此时A上有3，4，5，B为空，C上有1，2。
再将3挪到B，C上的1也挪到A，C上的2挪到B，A上的1再挪到B，此时A上有45，B上有123，C为空
再将4挪到C，B上的1挪到A，B上的2移到C上，A上的1挪到C上，B上的3挪到A上，C上面的1挪到B上, 有1234
最后将
伪码（pesudocode）：
算法Hanoi(A,C,n) // n个盘子从A到C
1.if n = 1 then move(A, C)
2.else Hanoi(A, B, n-1)
3.move(A, C)
4.Hanoi(B,C,n-1) 设n个盘子的移动次数为T(n)
T(n) = 2T(n-1) 1
T(1) = 1
程序：
public static void solve(int n){
hanoi(n, "A", "B", "C");
}
private static void hanoi(int n ,String a, String b,String c){
if(n==1){
move(n,a,c);
} else {
hanoi(n-1, a, c, b); // 将前n-1个圆盘从a挪到c，借助b
move(n, a, c); // 将第n个直接移到c
hanoi(n-1, b, a, c); // 将前n-1个圆盘从b挪到c，借助啊
}
}
private static void move(int n, String i, String j){
Systtem.out.println("第" n "个盘，从" i "塔移动到" j "塔");
}
时间复杂度分析：
hanoi塔游戏的递推公式为T（n）=2T（n-1) 1，时间复杂度为O(2^n)
六、分治法联系（C语言）6.1 求一组数据中最大的两个数和最小的两个数输入输出实例：
10 代表10个数
1
3
5
7
9
10
8
6
4
2
max1=10 max2=9
min1=1 min2=2
代码实现：
#include <stdio.h>
void maxtwo(int[], int, int, int*, int*);
void mintwo(int[], int, int, int*, int*);
int main()
{
int num,i;
scanf("%d",&num);
int a[num];
for(i=0;i<num;i )
scanf("%d",&a[i]);
/********** Begin **********/
int max1, max2, min1, min2;
maxtwo(a, 0, num-1, &max1, &max2);
printf("max1=%d max2=%d\n",max1,max2);
mintwo(a, 0, num-1, &min1, &min2);
printf("min1=%d min2=%d\n",min1,min2);
/********** End **********/
}
void maxtwo(int a[], int i,int j,int *max1,int *max2){
int lmax1,lmax2,rmax1,rmax2;
int mid;
if(i==j){
*max1=a[i];
*max2=a[i];
}else if (i==j-2){
if (a[i]>=a[i 1]&&a[i 1]>=a[i 2]){
*max1=a[i];
*max2=a[i 1];
}else if (a[i]>=a[i 2]&&a[i 2]>=a[i 1]){
*max1=a[i];
*max2=a[i 2];
}else if (a[i 1]>=a[i]&&a[i]>=a[i 2]){
*max1=a[i 1];
*max2=a[i];
}else if (a[i 1]>=a[i 2]&&a[i 2]>=a[i]){
*max1=a[i 1];
*max2=a[i 2];
}else if (a[i 2]>=a[i]&&a[i]>=a[i 1]){
*max1=a[i 2];
*max2=a[i];
}else{
*max1=a[i 2];
*max2=a[i 1];
}
}else{
mid=(i j)/2;
maxtwo(a, i,mid,&lmax1,&lmax2);
maxtwo(a, mid 1,j,&rmax1,&rmax2);
if(lmax1>=rmax1){
*max1=lmax1;
if (lmax2>=rmax2){
*max2=lmax2;
}else{
*max2=rmax1;
}
}else{
*max1=rmax1;
if (rmax2>=lmax2){
*max2=rmax2;
}else {
*max2=lmax1;
}
}
}
}
void mintwo(int a[], int i, int j, int *min1, int *min2){
int lmin1, lmin2, rmin1, rmin2;
int mid;
if(i == j){
*min1 = a[i];
*min2 = a[i];
}
else if(i == j - 2){
if(a[i]<=a[i 1]&&a[i 1]<=a[i 2]){
*min1 = a[i];
*min2 = a[i 1];
}else if(a[i]<=a[i 2]&&a[i 2]<=a[i 1]){
*min1 = a[i];
*min2 = a[i 2];
}else if(a[i 1]<=a[i]&&a[i]<=a[i 2]){
*min1 = a[i 1];
*min2= a[i];
}else if(a[i 1]<=a[i 2]&&a[i 2]<=a[i]){
*min1 = a[i 1];
*min2 = a[i 2];
}else if(a[i 2]<=a[i]&&a[i]<=a[i 1]){
*min1 = a[i 2];
*min2 =a[i];
}else{
*min1 = a[i 2];
*min2 = a[i 1];
}
}else{
mid = (i j)/2;
mintwo(a, i, mid, &lmin1, &lmin2);
mintwo(a, mid 1, j, &rmin1, &rmin2);
if(lmin1 <= rmin1){
*min1 = lmin1;
if(lmin2 <= rmin2){
*min2 = lmin2;
}else{
*min2 = rmin1;
}
}else{
*min1 = rmin1;
if(rmin2 <= lmin2){
*min2 = rmin2;
}else{
*min2 = lmin1;
}
}
}
}
6.2 分治法求一组数据的和
输入输出示例：
8 代表8个数
18
-38
-16
87
-27
74
31
100
分治法求出数组元素的和为:229
代码实现：
#include "stdio.h"
/********** Begin **********/
int calculate_sum(int[], int, int);
int main()
{
int i, num, sum;
scanf("%d", &num);
int a[num];
for(i = 0; i < num; i ){
scanf("%d", &a[i]);
}
sum = calculate_sum(a, 0, num-1);
printf("分治法求出数组元素的和为:%d",sum);
}
/********** End **********/
int calculate_sum(int a[], int i, int j){
int mid, left_sum, right_sum;
if(i == j){
return a[i];
// }else if(j-1 == 1){
// return a[i] a[j];
}else{
mid = (i j) / 2;
left_sum = calculate_sum(a, i, mid);
right_sum = calculate_sum(a, mid 1, j);
return left_sum right_sum;
}
}
6.3 求一组数据中第k小的数
输入输出示例：
10 5 代表10个数据，求第5个小的元素
-34
95
-50
67
73
81
-38
10
-11
70
第5小的元素是10
代码实现：
#include<stdio.h>
#define ArrLen 20
void mergeSort(int[], int, int);
void merge(int[], int, int, int);
int main()
{
int i, num, k;
scanf("%d %d", &num, &k);
int a[num];
for(i = 0; i < num; i ){
scanf("%d", &a[i]);
}
mergeSort(a, 0, num-1);
printf("第%d小的元素是%d", k, a[k - 1]);
return 0;
}
void merge(int arr[], int start, int mid, int end) {
int result[ArrLen];
int k = 0;
int i = start;
int j = mid 1;
while (i <= mid && j <= end) {
if (arr[i] < arr[j]){
result[k ] = arr[i ];
}
else{
result[k ] = arr[j ];
}
}
if (i == mid 1) {
while(j <= end)
result[k ] = arr[j ];
}
if (j == end 1) {
while (i <= mid)
result[k ] = arr[i ];
}
for (j = 0, i = start ; j < k; i , j ) {
arr[i] = result[j];
}
}
void mergeSort(int arr[], int start, int end) {
if (start >= end)
return;
int mid = ( start end ) / 2;
mergeSort(arr, start, mid);
mergeSort(arr, mid 1, end);
merge(arr, start, mid, end);
}
