通知短信+运营短信,5秒速达,支持群发助手一键发送🚀高效触达和通知客户 广告
&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; } ~~~ :-: ![](https://img.kancloud.cn/ab/2b/ab2ba69d2b3cbb2643b307f8e8a1d853_406x559.png =300x) 图 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); } ~~~ :-: ![](https://img.kancloud.cn/67/0c/670c5fdc164d714968f0e4573c0987ca_749x814.png =400x) 图 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),欢迎阅读。 ![](https://box.kancloud.cn/2e1f8ecf9512ecdd2fcaae8250e7d48a_430x430.jpg =200x200) 推荐一款前端监控脚本:[shin-monitor](https://github.com/pwstrick/shin-monitor),不仅能监控前端的错误、通信、打印等行为,还能计算各类性能参数,包括 FMP、LCP、FP 等。