&emsp;&emsp;分治算法（Divide-and-Conquer Algorithm），就是分而治之，把一個復雜問題分成兩個或更多個相同或相似的子問題，直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。 &emsp;&emsp;分治算法比較適合用遞歸來實現，而每一層遞歸都會涉及三個操作： &emsp;&emsp;（1）分解：將原問題分解為若干個規模較小，相對獨立，與原問題形式相同的子問題，縮小問題規模。 &emsp;&emsp;（2）求解：若子問題規模較小且易于解決時（找出基線條件），則直接解。否則，遞歸地解決各子問題。其中基線條件（base case）通常是數組為空或只包含一個元素。 &emsp;&emsp;（3）合并：將各子問題的解合并為原問題的解。 &emsp;&emsp;分治算法是一種處理問題的思想和技巧，是很多高效算法的基礎，例如排序算法（歸并和快排）、最大公因數等。 &emsp;&emsp;LeetCode的[169\. 多數元素](https://leetcode-cn.com/problems/majority-element/)，可將數組一分為二，左邊遞歸最大值（left），右邊也一樣（right），當兩者相同，就是找到了；當不同時，比較誰的計數多。 &emsp;&emsp;與動態規劃不同，分治算法分解的子問題可以獨立求解，并且它們之間沒有相關性。 &emsp;&emsp;在《劍指Offer》一書中曾提到，解決復雜問題的3種方法： &emsp;&emsp;（1）畫圖，涉及鏈表、二叉樹等數據結構時，畫幾張草圖，可將隱藏的規律變得直觀。 &emsp;&emsp;（2）舉例，將抽象問題具體化，模擬運行過程，說不定能發現其中規律。 &emsp;&emsp;（3）分解，如果問題很大，則嘗試把大問題分解成小問題，然后遞歸解決，分治法、動態規劃等方法都是分解復雜問題的思路。 ## 一、歸并排序 &emsp;&emsp;利用遞歸與分治技術將數據序列劃分成越來越小的半子表，再對半子表排序，最后用遞歸方法將排好序的半子表合并成為越來越大的有序序列，[如下所示](https://codepen.io/strick/pen/LYGoWmo)，思路如圖8所示。 ~~~ function mergeSort(arr) { let len = arr.length; //基線條件 if (len < 2) { return arr; } //分解 let middle = Math.floor(len / 2), left = mergeSort(arr.slice(0, middle)), right = mergeSort(arr.slice(middle)); //合并 return merge(left, right); } function merge(left, right) { let result = []; //求解 while (left.length && right.length) { //小的在左，大的在右 if (left[0] <= right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result; } ~~~ :-:  圖 8 &emsp;&emsp;面試題51[數組中的逆序對](https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)。先統計子數組中的逆序對，然后統計兩個相鄰數組之間的逆序對，在統計的過程中還需要對數組進行歸并排序。 ## 二、快速排序 &emsp;&emsp;采用“分而治之”的思想，把大的拆分為小的，小的再拆分為更小的。 &emsp;&emsp;將原序列分為兩部分，其中前一部分的所有記錄均比后一部分的所有記錄小，然后再依次對前后兩部分的記錄進行快速排序，遞歸該過程，直到序列中的所有記錄均有序為止。 &emsp;&emsp;代碼實現[如下所示](https://codepen.io/strick/pen/GRoaWbN)，思路如圖9所示。 ~~~ function quickSort(arr) { var length = arr.length; //基線條件 if (length <= 1) { return arr; } var base = arr[0], left = [], //保存小于基準元素的記錄 right = []; //保存大于基準元素的記錄 //求解 for (let i = 1; i < length; i++) { if (base > arr[i]) { //放入左邊數組 left.push(arr[i]); } else { //放入右邊數組 right.push(arr[i]); } } //分解 left = quickSort(left); right = quickSort(right); //合并 return left.concat([base], right); } ~~~ :-:  圖 9 &emsp;&emsp;面試題39[數組中出現次數超過一半的數字](https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/)。問題轉換為查找中位數，受快速排序的啟發，當基準值的下標剛好是n/2時，那么就是中位數，否則在另外兩部分中查找。 &emsp;&emsp;面試題40[最小的 k 個數](https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/)。采用快速排序思想，基于數組第 k 個數字來調整，比 k 個數小的在左邊，大的在右邊。 ***** > 原文出處： [博客園-數據結構和算法躬行記](https://www.cnblogs.com/strick/category/1809992.html) 已建立一個微信前端交流群，如要進群，請先加微信號freedom20180706或掃描下面的二維碼，請求中需注明“看云加群”，在通過請求后就會把你拉進來。還搜集整理了一套[面試資料](https://github.com/pwstrick/daily)，歡迎閱讀。  推薦一款前端監控腳本：[shin-monitor](https://github.com/pwstrick/shin-monitor)，不僅能監控前端的錯誤、通信、打印等行為，還能計算各類性能參數，包括 FMP、LCP、FP 等。