分治
在計(jì)算機(jī)科學(xué)中嚷硫，分治法是一種很重要的算法订雾。字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解眠菇，原問(wèn)題的解即子問(wèn)題的解的合并边败。這個(gè)技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序捎废，歸并排序)笑窜，傅立葉變換(快速傅立葉變換)……
任何一個(gè)可以用計(jì)算機(jī)求解的問(wèn)題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問(wèn)題的規(guī)模越小登疗，越容易直接求解排截，解題所需的計(jì)算時(shí)間也越少。例如辐益，對(duì)于n個(gè)元素的排序問(wèn)題断傲，當(dāng)n=1時(shí)，不需任何計(jì)算智政。n=2時(shí)认罩，只要作一次比較即可排好序。n=3時(shí)只要作3次比較即可续捂，…垦垂。而當(dāng)n較大時(shí)，問(wèn)題就不那么容易處理了牙瓢。要想直接解決一個(gè)規(guī)模較大的問(wèn)題劫拗，有時(shí)是相當(dāng)困難的。
二矾克、基本思想及策略
分治法的設(shè)計(jì)思想是：將一個(gè)難以直接解決的大問(wèn)題页慷，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破胁附，分而治之差购。
分治策略是：對(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è)計(jì)策略叫做分治法弓叛。
如果原問(wèn)題可分割成k個(gè)子問(wèn)題彰居，1<k≤n，且這些子問(wèn)題都可解并可利用這些子問(wèn)題的解求出原問(wèn)題的解撰筷，那么這種分治法就是可行的陈惰。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便毕籽。在這種情況下抬闯，反復(fù)應(yīng)用分治手段井辆，可以使子問(wèn)題與原問(wèn)題類(lèi)型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解溶握。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生杯缺。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中睡榆，并由此產(chǎn)生許多高效算法萍肆。
三、分治法適用的情況
分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：
該問(wèn)題的規(guī)恼陀欤縮小到一定的程度就可以容易地解決
該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題塘揣，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解宿崭；
該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的勿负，即子問(wèn)題之間不包含公共的子子問(wèn)題。
第一條特征是絕大多數(shù)問(wèn)題都可以滿足的劳曹，因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加奴愉；
第二條特征是應(yīng)用分治法的前提它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用铁孵；锭硼、
第三條特征是關(guān)鍵，能否利用分治法完全取決于問(wèn)題是否具有第三條特征蜕劝，如果具備了第一條和第二條特征檀头，而不具備第三條特征，則可以考慮用貪心法或動(dòng)態(tài)規(guī)劃法岖沛。
第四條特征涉及到分治法的效率暑始，如果各子問(wèn)題是不獨(dú)立的則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題婴削，此時(shí)雖然可用分治法廊镜，但一般用動(dòng)態(tài)規(guī)劃法較好。
分治步驟
step1 分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小唉俗，相互獨(dú)立嗤朴，與原問(wèn)題形式相同的子問(wèn)題；
step2 解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解虫溜，否則遞歸地解各個(gè)子問(wèn)題
step3 合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解雹姊。
歸并排序
歸并排序的關(guān)鍵在于歸并兩個(gè)相鄰的子序列，使其變成一個(gè)排序好的新序列衡楞。如果這個(gè)新序列就是原來(lái)需要進(jìn)行排序的數(shù)組吱雏，那么排序完成。所以，我們需要將原序列遞歸地分成若干子序列歧杏，直道最小的子序列只有一個(gè)元素镰惦，然后將子序列依次歸并，就可以得到排序好的原序列得滤。
代碼
package test;
import java.util.Arrays;
/**
* Created by liqiushi on 2017/12/26.
*/
public class MergeSort {
public static void sort(int arr[], int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
//0 1
sort(arr, low, mid);//0 0陨献、
sort(arr, mid + 1, high);//1 1
merge(arr,low,mid,high);
}
}
/**
* 有序地合并兩個(gè)數(shù)組
*
* @param arr
* @param low
* @param mid
* @param high
*/
public static void merge(int arr[], int low, int mid, int high) {
int[] sortArr = new int[high-low+1];
int i = 0;
int j = low;
int k = mid+1;
while (j <= mid && k <= high) {
if (arr[j] <= arr[k]) {
sortArr[i++] = arr[j++];
} else {
sortArr[i++] = arr[k++];
}
}
while (j > mid && k <= high) {
sortArr[i++] = arr[k++];
}
while (k > high && j <= mid) {
sortArr[i++] = arr[j++];
}
for (int l = 0; l < sortArr.length; l++) {
arr[low+l] = sortArr[l];
}
}
public static void main(String[] args) {
int[] arr = {1, 5, 8, 4, 6, 78, 26, 13, 66};
sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
//arr,low,high
//sort(arr,0,arr.length-1);
}
}
