7、分治算法

  分治算法（Divide-and-Conquer Algorithm），就是分而治之，把一个复杂问题分成两个或更多个相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。   分治算法比较适合用递归来实现，而每一层递归都会涉及三个操作：   （1）分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题，缩小问题规模。   （2）求解：若子问题规模较小且易于解决时（找出基线条件），则直接解。否则，递归地解决各子问题。其中基线条件（base case）通常是数组为空或只包含一个元素。   （3）合并：将各子问题的解合并为原问题的解。   分治算法是一种处理问题的思想和技巧，是很多高效算法的基础，例如排序算法（归并和快排）、最大公因数等。   LeetCode的[169\. 多数元素](https://leetcode-cn.com/problems/majority-element/)，可将数组一分为二，左边递归最大值（left），右边也一样（right），当两者相同，就是找到了；当不同时，比较谁的计数多。   与动态规划不同，分治算法分解的子问题可以独立求解，并且它们之间没有相关性。   在《剑指Offer》一书中曾提到，解决复杂问题的3种方法：   （1）画图，涉及链表、二叉树等数据结构时，画几张草图，可将隐藏的规律变得直观。   （2）举例，将抽象问题具体化，模拟运行过程，说不定能发现其中规律。   （3）分解，如果问题很大，则尝试把大问题分解成小问题，然后递归解决，分治法、动态规划等方法都是分解复杂问题的思路。 ## 一、归并排序   利用递归与分治技术将数据序列划分成越来越小的半子表，再对半子表排序，最后用递归方法将排好序的半子表合并成为越来越大的有序序列，[如下所示](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   面试题51[数组中的逆序对](https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)。先统计子数组中的逆序对，然后统计两个相邻数组之间的逆序对，在统计的过程中还需要对数组进行归并排序。 ## 二、快速排序   采用“分而治之”的思想，把大的拆分为小的，小的再拆分为更小的。   将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。   代码实现[如下所示](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   面试题39[数组中出现次数超过一半的数字](https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/)。问题转换为查找中位数，受快速排序的启发，当基准值的下标刚好是n/2时，那么就是中位数，否则在另外两部分中查找。   面试题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)，欢迎阅读。