分冶算法的基本思想是將原問題分解為幾個規(guī)模較小的但類似原問題的子問題帐萎，遞歸地求解這些了問題比伏，然后再合并這些子問題的解來建立原問題的解
分冶算法在每層遞歸時都有三個步驟：
- 分解，原問題分為若干子問題疆导，這些子問題都是原問題的規(guī)模較小的實例
- 解決赁项，遞歸解決這些子問題，如果子問題的規(guī)模足夠小，則直接求解
- 合并悠菜， 合并子問題的解成原問題的解
分治算法中需要使用遞歸舰攒，在使用遞歸時，一定要確定問題邊界悔醋，即問題規(guī)模較小的條件摩窃。常見的歸并排序以及求解數(shù)組中連續(xù)子數(shù)組和的最大值，都可以使用分治法解決
歸并排序
歸并排序的基本思想是芬骄，將數(shù)組分成兩個子數(shù)組猾愿，使用遞歸對兩個子數(shù)組進行排序，合并兩個已正確排序的子數(shù)組账阻。
注意蒂秘，遞歸的邊界條件即是，子數(shù)組中只有一個元素淘太。假定數(shù)組中只有兩個元素姻僧，分解成兩個子數(shù)組，每個子數(shù)組中只有一個元素琴儿，子數(shù)組中的元素此時當然就是已經(jīng)“排序正確”的段化，合并子數(shù)組，則整個數(shù)組已正確排序造成。
數(shù)組合并是整個過程中最復(fù)雜的地方显熏。可以想象手邊有兩堆撲克牌晒屎，每堆撲克牌都是從小到大排序完畢喘蟆，比較每堆撲克牌最上邊的牌的大小，取最小的放到手上鼓鲁，直到有一堆撲克牌已經(jīng)被取完蕴轨，此時再將剩下的那一堆撲克牌全部放到手上，則手中的所有牌都是按從小到大順序排列好骇吭。
為了界定每堆撲克牌是否已經(jīng)取完橙弱，本文中向每堆撲克牌最后放入一張哨兵牌。以便于節(jié)省大量的判斷燥狰，牌堆是否已經(jīng)取完棘脐。
//p是數(shù)組中合并的起始index，p是中間位置龙致，r是末位
public static void merge(int[] array, int p, int q, int r){
int n1 = q - p + 1;
int n2 = r - (q + 1) + 1;
int[] left = new int[n1 + 1];
int[] right = new int[n2 + 1];
int i = 0;
int j = 0;
for (i = 0; i < n1; i++) {
left[i] = array[p + i];
}
left[n1] = Integer.MAX_VALUE;
for (j = 0; j < n2; j++) {
right[j] = array[q + 1 + j];
}
right[n2] = Integer.MAX_VALUE;
i = 0;
j = 0;
//哨兵牌為正整數(shù)最大值蛀缝，所以子數(shù)組中不可能有大于它的數(shù)，假設(shè)left子數(shù)組已經(jīng)被取完目代，只剩下哨兵牌
//right子數(shù)組剩下的元素則必然全都小于哨兵牌屈梁，則可全取right子數(shù)組嗤练，而不用判定子數(shù)組是否已經(jīng)取完
for (int k = p; k <= r; k++) {
if (left[i] < right[j]) {
array[k] = left[i];
i ++;
}else {
array[k] = right[j];
j++;
}
}
}
最復(fù)雜的合并工作已經(jīng)完成，則分解子問題和求解子問題則很簡單了在讶。
public static void sort(int[] array, int p, int r){
if (p < r) {
int q = (r + p)/2;
sort(array, p, q);
sort(array, q + 1, r);
merge(array, p, q, r);
}
}
連續(xù)子數(shù)組和最大值
如果在一個數(shù)組中煞抬，找出一個連續(xù)子數(shù)組和的最大值。此問題必須是在有負數(shù)的數(shù)組中才有意義构哺，如果數(shù)組中全為正數(shù)此疹，那么此問題的解即為數(shù)組所有元素之和
此問題也可以用分治算法解決，將數(shù)組分解為兩個子數(shù)組遮婶，那么問題的解必然為以下三個之一：
- 左子數(shù)組中的連續(xù)子數(shù)組和最大值
- 右子數(shù)組中的連續(xù)子數(shù)組和最大值
- 包含跨越分隔左右子數(shù)組的中間值的連續(xù)子數(shù)組的和的最大值。
分治算法有三步湖笨，分解子問題旗扑、解決子問題、全并子問題慈省。本問題中臀防，合并子問題非常簡單，如果以上三個值已經(jīng)求出來边败，通過比較大小即可得知袱衷，時間復(fù)雜度為1，分解子問題和解決子問題中只有一步較為復(fù)雜笑窜，即是上文中的第三步致燥，求 包含中間值的連續(xù)子數(shù)組和的最大值，不過將此問題單獨提出來也是比較簡單的排截，因為此連續(xù)子數(shù)組必然包含中間值嫌蚤。
根據(jù)中間值將數(shù)組分成兩半，分別求取左右兩邊的連續(xù)子數(shù)組和的最大值断傲，再相加即可脱吱。時間復(fù)雜度為n。
private static int[] getMaxSumSubArrayCorssMidel(int[] array, int low, int middle, int high){
int left_sum = Integer.MIN_VALUE;
int sum = 0;
int maxLeftIndex = 0;
for (int i = middle; i >= low; i--) {
sum = sum + array[i];
if (sum > left_sum) {
left_sum = sum;
maxLeftIndex = i;
}
}
sum = 0;
int right_sum = Integer.MIN_VALUE;
int maxRightIndex = 0;
for (int i = middle + 1; i <= high; i++) {
sum = sum + array[i];
if (sum > right_sum) {
right_sum = sum;
maxRightIndex = i;
}
}
return new int[]{maxLeftIndex, maxRightIndex, left_sum + right_sum};
}
遞歸求解子問題的邊界點是什么呢认罩？數(shù)組只有一個元素箱蝠，則連續(xù)子數(shù)組和的最大值則為數(shù)組唯一元素。確定了邊界垦垂，則剩余代碼非常容易寫了
private static int[] getMaxSumSubArray(int[] array, int low, int high){
if (low == high) {
return new int[]{low, high ,array[low]};
}else {
int middle = (low + high)/2;
int[] left = getMaxSumSubArray(array, low, middle);
int[] right = getMaxSumSubArray(array, middle + 1, high);
int[] corss = getMaxSumSubArrayCorssMidel(array, low, middle, high);
if (left[2] >= right[2] && left[2] >= corss[2]) {
return left;
}else if (right[2] >= left[2] && right[2] >= corss[2]) {
return right;
}else{
return corss;
}
}
}
求取數(shù)組中元素的最大值
求取數(shù)組中元素的最大值也可以使用分治法解決宦搬，通常人們都使用二分法查找，后續(xù)將討論分治算法的時間復(fù)雜度乔外，可計算得出床三，二分法和分治算法的時間復(fù)雜度是一樣的。不過遞歸本身效率不高杨幼，執(zhí)行一次函數(shù)需要入棧出棧多次撇簿，分治算法的最終效率肯定是不及二分查找的聂渊。不過此文中只為展示分治算法的使用。
同理四瘫，將數(shù)組分成兩個子數(shù)組汉嗽，分別求取兩個子數(shù)組中的最大值，再將兩個子數(shù)組的最大值比較找蜜，取其大者饼暑，則可求得此問題的解。
本例中合并子問題非常簡單洗做，只需要比較子問題的解大小即可弓叛，取其大者就ok了，時間復(fù)雜度為1
private static int findMax(int[] array, int p, int q){
if (p == q) {
return array[q];
}else {
int middle = (p + q)/2;
int left = findMax(array, p, middle);
int right = findMax(array, middle + 1, q);
return (left > right) ? left : right;
}
}
未完待續(xù)诚纸，關(guān)于分治算法的時間復(fù)雜度撰筷。
