[TOC] ## 概述 先分別處理局部，再合并結果 適用場景 1. 該問題的規模縮小到一定的程度就可以容易的解決。 2. 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。 3. 利用該問題分解出的子問題的解可以合并為該問題的解。 4. 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 適用方法 * 快速排序 * 歸并排序 * 二叉樹相關問題 基本步驟 * 分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題 * 解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題 * 合并：將各個子問題的解合并為原問題的解 ## 分封制的模板 ``` void merge_sort(int array[], unsigned int first, unsigned int last) { int mid = 0; if(first<last) { mid = (first+last)/2; merge_sort(array, first, mid); merge_sort(array, mid+1,last); merge(array,first,mid,last); } } ``` 在程序中可以看出分治法的應用：在merge\_sort()中，將原來針對索引first到last的數組排序的問題，分為二份較小的問題 * 先針對索引first到mid的數組排序。 * 再針對索引mid+1到last的數組排序。 最后再進行二個數組的合并。