1 概念
分治算法，根據(jù)字面意思解釋是“分而治之”，就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。
2 算法策略
分治策略：對(duì)于一個(gè)規(guī)模為 n 的問(wèn)題，若該問(wèn)題可以容易地解決（比如說(shuō)規(guī)模 n 較小）則直接解決，否則將其分解為 k 個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同，遞歸地解這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題的解。
在平時(shí)日常生活中，分治思想也是隨處可見(jiàn)的。例如：當(dāng)我們打牌時(shí)，在進(jìn)行洗牌時(shí)，若牌的數(shù)目較多，一個(gè)人洗不過(guò)來(lái)，則會(huì)將牌進(jìn)行分堆，單獨(dú)洗一小堆牌是相對(duì)容易的，每一堆牌都洗完之后再放到一起，則完成洗牌過(guò)程。
3 使用場(chǎng)景
（1）該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決。
（2）該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
（3）利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解。
（4）該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。
4 基本步驟
分治法在每一層遞歸上都有三個(gè)步驟：
（1）分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題。
（2）求解：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題。
（3）合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。
分治思想
5 偽代碼
Divide-and-Conquer(P) if |P| ≤ n0 then return(ADHOC(P)) 將P分解為較小的子問(wèn)題 P1 ,P2 ,...,Pk for i←1 to k do yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi T ← MERGE(y1,y2,...,yk) △ 合并子問(wèn)題 return(T)
其中，|P| 表示問(wèn)題 P 的規(guī)模，n0 為一閾值，表示當(dāng)問(wèn)題 P 的規(guī)模不超過(guò) n0 時(shí)，問(wèn)題已容易直接解出，不必再繼續(xù)分解。ADHOC(P) 是該分治法中的基本子算法，用于直接解小規(guī)模的問(wèn)題 P。因此，當(dāng) P 的規(guī)模不超過(guò)n0 時(shí)直接用算法 ADHOC(P) 求解。算法 MERGE(y1,y2,…,yk) 是該分治法中的合并子算法，用于將 P 的子問(wèn)題 P1 ,P2 ,…,Pk 的相應(yīng)的解 y1 , y2 ,…, yk 合并為 P 的解。
6 典型案例
6.1 二分查找
二分查找是典型的分治算法的應(yīng)用。需要注意的是，二分查找的前提是查找的數(shù)列是有序的。
算法流程：
（1）選擇一個(gè)標(biāo)志 i 將集合分為二個(gè)子集合。
（2）判斷標(biāo)志 L(i) 是否能與要查找的值 des 相等，相等則直接返回。
（3）否則判斷 L(i) 與 des 的大小。
（4）基于判斷的結(jié)果決定下步是向左查找還是向右查找。
（5）遞歸繼續(xù)上面的步驟。
通過(guò)二分查找的流程可以看出，二分查找是將原有序數(shù)列劃分為左右兩個(gè)子序列，然后在對(duì)兩個(gè)子序列中的其中一個(gè)在進(jìn)行劃分，直至查找成功。
代碼實(shí)現(xiàn)：
#include<string.h>
#include<stdio.h>
int k;
int binarysearch(int a[],int x,int low,int high)//a表示需要二分的有序數(shù)組（升序），x表示需要查找的數(shù)字，low，high表示高低位
{
if(low>high)
{
return -1;//沒(méi)有找到
}
int mid=(low+high)/2;
if(x==a[mid])//找到x
{
k=mid;
return x;
}
else if(x>a[mid]) //x在后半部分
{
binarysearch(a,x,mid+1,high);//在后半部分繼續(xù)二分查找
}
else//x在前半部分
{
binarysearch(a,x,low,mid-1);
}
}
int main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
printf("請(qǐng)輸入需要查找的正數(shù)字：
");
int x;
scanf("%d",&x);
int r=binarysearch(a,x,0,9);
if(r==-1)
{
printf("沒(méi)有查到
");
}
else
{
printf("查到了,在數(shù)列的第%d個(gè)位置上
",k+1);
}
return 0;
}
6.2 全排列問(wèn)題
問(wèn)題描述：
有1，2，3，4個(gè)數(shù)，問(wèn)你有多少種排列方法，并輸出排列。
問(wèn)題分析：
若采用分治思想進(jìn)行求解，首先需要把大問(wèn)題分解成很多的子問(wèn)題，大問(wèn)題是所有的排列方法。那么我們分解得到的小問(wèn)題就是以 1 開(kāi)頭的排列，以 2 開(kāi)頭的排列，以 3 開(kāi)頭的排列，以 4 開(kāi)頭的排列。現(xiàn)在這些問(wèn)題有能繼續(xù)分解，比如以 1 開(kāi)頭的排列中，只確定了 1 的位置，沒(méi)有確定 2 ，3 ，4 的位置，把 2，3，4 三個(gè)又看成大問(wèn)題繼續(xù)分解，2 做第二個(gè)，3 做第二個(gè)，或者 4 做第二個(gè)。一直分解下去，直到分解成的子問(wèn)題只有一個(gè)數(shù)字的時(shí)候，不能再分解。只有一個(gè)數(shù)的序列只有一種排列方式，則子問(wèn)題求解容易的多。
代碼實(shí)現(xiàn)：
public class Test {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4 };
fullSort(arr, 0, arr.length - 1);
}
public static void fullSort(int[] arr, int start, int end) {
// 遞歸終止條件
if (start == end) {
for (int i : arr) {
System.out.print(i);
}
System.out.println();
return;
}
for (int i = start; i <= end; i++) {
swap(arr, i, start);
fullSort(arr, start + 1, end);
swap(arr, i, start);
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
6.3 歸并排序
歸并排序：歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。即先劃分為兩個(gè)部分，最后進(jìn)行合并。
歸并排序
偽代碼：
算法 MergeSort(A, p, r) 輸入：數(shù)組A[p...r] 輸出：有序數(shù)組A if(p < r) then q <- (p+r)/2//折半劃分 MergeSort(A, p ,q)//子問(wèn)題1 MergeSort(A, p ,q)//子問(wèn)題2 Merge(A, p ,q, r)//合并求解
代碼實(shí)現(xiàn)：
public class MergeSort {
//兩路歸并算法，兩個(gè)排好序的子序列合并為一個(gè)子序列
public void merge(int []a,int left,int mid,int right){
int []tmp=new int[a.length];//輔助數(shù)組
int p1=left,p2=mid+1,k=left;//p1、p2是檢測(cè)指針，k是存放指針
while(p1<=mid && p2<=right){
if(a[p1]<=a[p2])
tmp[k++]=a[p1++];
else
tmp[k++]=a[p2++];
}
while(p1<=mid) tmp[k++]=a[p1++];//如果第一個(gè)序列未檢測(cè)完，直接將后面所有元素加到合并的序列中
while(p2<=right) tmp[k++]=a[p2++];//同上
//復(fù)制回原素組
for (int i = left; i <=right; i++)
a[i]=tmp[i];
}
public void mergeSort(int [] a,int start,int end){
if(start<end){//當(dāng)子序列中只有一個(gè)元素時(shí)結(jié)束遞歸
int mid=(start+end)/2;//劃分子序列
mergeSort(a, start, mid);//對(duì)左側(cè)子序列進(jìn)行遞歸排序
mergeSort(a, mid+1, end);//對(duì)右側(cè)子序列進(jìn)行遞歸排序
merge(a, start, mid, end);//合并
}
}
}
6.4 快速排序
快速排序的基本思想：當(dāng)前待排序的無(wú)序區(qū)為 A[low..high] ，利用分治法可將快速排序的基本思想描述為：
（1）分解：
在A[low..high]中任選一個(gè)記錄作為基準(zhǔn)(pivot)，以此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左、右兩個(gè)較小的子區(qū)間R[low..pivotpos-1) 和 R[pivotpos+1..high] ，并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為pivot)的關(guān)鍵字 pivot.key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot.key，而基準(zhǔn)記錄pivot則位于正確的位置( pivotpos )上，它無(wú)須參加后續(xù)的排序。
（2）求解：
通過(guò)遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
（3）合并：
因?yàn)楫?dāng)"求解"步驟中的兩個(gè)遞歸調(diào)用結(jié)束時(shí)，其左、右兩個(gè)子區(qū)間已有序。對(duì)快速排序而言，"組合"步驟無(wú)須做什么，可看作是空操作。
快速排序
代碼實(shí)現(xiàn)：
#include <IOStream>
using namespace std;
void QuickSort(int arr[], int low, int high){
if (high <= low) return;
int i = low;
int j = high + 1;
int key = arr[low];
while (true)
{
/*從左向右找比key大的值*/
while (arr[++i] < key)
{
if (i == high){
break;
}
}
/*從右向左找比key小的值*/
while (arr[--j] > key)
{
if (j == low){
break;
}
}
if (i >= j) break;
/*交換i,j對(duì)應(yīng)的值*/
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/*中樞值與j對(duì)應(yīng)值交換*/
int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
QuickSort(arr, low, j - 1);
QuickSort(arr, j + 1, high);
}
6.5 漢諾塔
漢諾塔（Hanoi Tower）問(wèn)題也是一個(gè)經(jīng)典的遞歸問(wèn)題，該問(wèn)題描述如下：
漢諾塔問(wèn)題：古代有一個(gè)梵塔，塔內(nèi)有三個(gè)座A、B、C，A座上有64個(gè)盤(pán)子，盤(pán)子大小不等，大的在下，小的在上。有一個(gè)和尚想把這個(gè)盤(pán)子從A座移到B座，但每次只能允許移動(dòng)一個(gè)盤(pán)子，并且在移動(dòng)過(guò)程中，3個(gè)座上的盤(pán)子始終保持大盤(pán)在下，小盤(pán)在上。
兩個(gè)盤(pán)子
三個(gè)盤(pán)子
- ① 如果只有 1 個(gè)盤(pán)子，則不需要利用 B 塔，直接將盤(pán)子從 A 移動(dòng)到 C 。
- ② 如果有 2 個(gè)盤(pán)子，可以先將盤(pán)子 2 上的盤(pán)子 1 移動(dòng)到 B ；將盤(pán)子 2 移動(dòng)到 C ；將盤(pán)子 1 移動(dòng)到 C 。這說(shuō)明了：可以借助 B 將 2 個(gè)盤(pán)子從 A 移動(dòng)到 C ，當(dāng)然，也可以借助 C 將 2 個(gè)盤(pán)子從 A 移動(dòng)到 B 。
- ③ 如果有 3 個(gè)盤(pán)子，那么根據(jù) 2 個(gè)盤(pán)子的結(jié)論，可以借助 C 將盤(pán)子 3 上的兩個(gè)盤(pán)子從 A 移動(dòng)到 B ；將盤(pán)子 3 從 A 移動(dòng)到 C ，A 變成空座；借助 A 座，將 B 上的兩個(gè)盤(pán)子移動(dòng)到 C 。
- ④ 以此類(lèi)推，上述的思路可以一直擴(kuò)展到 n 個(gè)盤(pán)子的情況，將將較小的 n-1個(gè)盤(pán)子看做一個(gè)整體，也就是我們要求的子問(wèn)題，以借助 B 塔為例，可以借助空塔 B 將盤(pán)子A上面的 n-1 個(gè)盤(pán)子從 A 移動(dòng)到 B ；將A 最大的盤(pán)子移動(dòng)到 C ， A 變成空塔；借助空塔 A ，將 B 塔上的 n-2 個(gè)盤(pán)子移動(dòng)到 A，將 C 最大的盤(pán)子移動(dòng)到 C， B 變成空塔。。。
代碼實(shí)現(xiàn)：
public static void hanoi(int n, String sourceTower, String tempTower, String targetTower) {
if (n == 1) {
//如果只有一個(gè)盤(pán)子1，那么直接將其從sourceTower移動(dòng)到targetTower
move(n, sourceTower, targetTower);
} else {
//將（盤(pán)子n-1~盤(pán)子1）由sourceTower經(jīng)過(guò)targetTower移動(dòng)到tempTower
hanoi(n - 1, sourceTower, targetTower, tempTower);
//移動(dòng)盤(pán)子n由sourceTower移動(dòng)到targetTower
move(n, sourceTower, targetTower);
//把之前移動(dòng)到tempTower的（盤(pán)子n-1~盤(pán)子1），由tempTower經(jīng)過(guò)sourceTower移動(dòng)到targetTower
hanoi(n - 1, tempTower, sourceTower, targetTower);
}
}
//盤(pán)子n的從sourceTower->targetTower的移動(dòng)
private static void move(int n, String sourceTower, String targetTower) {
System.out.println("第" + n + "號(hào)盤(pán)子 move:" + sourceTower + "--->" + targetTower);
}
7 總結(jié)分析
分治法將規(guī)模為 n 的問(wèn)題分成 k 個(gè)規(guī)模為 n／m 的子問(wèn)題去解。設(shè)分解閥值 n0 = 1 ，且 adhoc 解規(guī)模為 1 的問(wèn)題耗費(fèi) 1 個(gè)單位時(shí)間。再設(shè)將原問(wèn)題分解為 k 個(gè)子問(wèn)題以及用 merge 將 k 個(gè)子問(wèn)題的解合并為原問(wèn)題的解需用 f(n) 個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為 |P| = n 的問(wèn)題所需的計(jì)算時(shí)間，則有：
T（n）= k T(n/m) + f(n)
