分治法
相似动静布局
- 明确设定一条基线
- 依据这条基线能够不停的将问题合成，直到所有内容合乎基线规范
// 疾速排序const quickSort = fucntion(arr) { if (arr.length <= 1) { return arr } // 1、找到基线，并对基线左右做申明 // 两头值下标 let pivotIndex = Math.floot(arr.length / 2) // 两头值 let pivot = arr.splice(pivotIndex, 1)[0] let left = [] let right = [] // 2、遍历以后的内容，依照基线去划分左右 for (let i = 0; i < arr.length; i++) { if (arr[i] < pivot) { left.push(arr[i]) } else { right.push(arr[i]) } } // 3. 递归解决，一直依据新的基线生成新内容，并进行连贯 return quickSort(left).concat([pivot], quickSort(right))}示例
let arr = [6, 3, 2, 6, 44, 1, 8, 10, 43, 1]let res = quickSort(arr)result:[ 1, 1, 2, 3, 6, 6, 8, 10, 43, 44]贪婪算法
- 利益最大化 始终查找最大的我的项目，尽可能快满足需要
- 何时实用贪心：须要查找最大我的项目等类型，同时满足利益最大化
// 给定一个整数数组inputArr，找到一个具备最大和的间断子数组（子数组必须蕴含一个元素），返回其最大和const maxSubArray = function(inputArr) { // 判断传入值 if (inputArr.length <= 1) return inputArr let rtnArr = inputArr[0] let sum = 0 for (const num of inputArr) { // 最快效率找到的就间接找间断的正整数子集，所以遇到正数就从新开始 if (sum > 0) { sum += num } else { sum = num } rtnArr = Math.max(rtnArr, sum) }}动静布局
动静布局(何时应用动静布局) - 将待求解的问题分解成若干子问题；子问题之间互相有分割
// 斐波那契数列const fib = function(n) { // 传入校验 if (n < 2) return n // 1、确定分界 let pre = 0 let next = 0 let res = 1 // 2、遍历所有内容进行运算执行 for (let i = 2; i <= n; i++) { // 往前移一位 pre = next next = res // 计算出第三位的熟 res = pre + next } return res}