算法思想
分治，分而治之，将原问题划分成 n 个规模较小而结构与原问题相似的子问题，这些规模小的问题与原问题是同质的，本质上还是同一个问题，递归解决这些子问题，然后合并其结果，就能得到原问题的解。（PS：当然，递归不是必须的）
空间换时间，来实现算法时间复杂度的优化
【分治算法】是很多高效算法的基础，诸如快速排序、归并排序、傅立叶变换、二分搜索
特征
- 原问题的规模缩小到一定的程度就很容易解决
--绝大多数问题都可以满足，因为问题的计算复杂性通常都是随着问题规模的增加而增加 - 原问题可以分解为若干个规模较小的相同问题，即该问题具有【最优子结构性质】
--应用分治法的前提，大多数问题也可以满足，它反映了递归思想的应用 - 分解出的子问题的解可以合并为该问题的解
--能否利用分治法的关键特征。如果只具备第一、第二特征，而不具备第三特征，则可以考虑动态规划或贪心算法 - 分解出的各个子问题相互独立，即【子问题之间不包括公共的子问题】
--涉及分治算法的效率，如果各个子问题不是相互独立的，分治算法要做很多不必需要的工作，重复地解决公共子问题，此时采用动态规划会比较好
前三个特征是使用分治法的关键，而特征4 涉及到分治法的效率问题。如果不符合3、4特征，可以尝试使用动态规划或胎心算法来解决。
【动态规划】是一种特殊的分治，贪心算法是一种特殊的动态规划
适用范围：
- 分治算法：最优子结构
- 动态规划：最优子结构、重叠子问题
- 贪心算法：最优子结构、重叠子问题、贪心选择性质
分支模式在每一层上都有三个步骤：
- 分解，将原问题分解成一系列与原问题同质的子问题
- 解决，递归解决各个子问题，若子问题足够小，则直接求解
- 合并，将子问题的结果合并成原问题的解
举个例子
有一个很经典的问题：有100枚硬币，其中有1枚略轻一些的假币，如果用天平秤，请问至少称几次一定能找到这枚假币？
如果用传统的逐枚比较法，显然至少需要比较50次
比较第i个与第i+1个的重量，若相等，则i++，继续比较，直到重量不相等，并输出较轻的硬币编号。-
采用分治算法
- 将
100枚硬币分成3份：33、33、34 - 称重
1、2份，若天枰平衡，则假币必在另外34枚中；若不平衡，则在较轻的那份33枚中 - 再将
34枚分成3份：11、11、12（或将33枚分成11、11、11） - 称重两组
11枚的硬币，若平衡，则假币在12枚里（或第三份11枚）；若不平衡，则在较轻的那份11枚中 - 将
12枚分成3份：4、4、4（或将11枚分成4、4、3），称重方法同上 - 将
4枚分成3份：1、1、2，称重1/1，若平衡，则称重剩下的2枚，较轻的1枚是假币；若不平衡，较轻的1枚是假币。（或将3枚分成1、1、1，称重1/1，若平衡，则剩下的1枚是假币；若不平衡，则较轻的1枚是假币）
综上所述，最多只需要
5次就能解决这个问题！ - 将
通过观察 1-2、3-4、5-6 发现，除了硬币数量变化了其他步骤完全一样，即 这是一个子问题的分解过程，100-33-11-3，将一个大问题分解成了容易解决的小问题，且 这些小问题相互独立，每一个 33 枚硬币和其他硬币互不影响。
实际上类似于数学归纳法，先找到最小问题规模的求解方程，然后考虑随着问题规模增大时的求解方程，然后根据方程式设计递归程序（当然，递归不是必须的），自顶而下的解决问题。
归并排序
归并排序是【分治算法】的典型应用：多次分解数列，直至子数列中只有一个元素（【分】）。然后对子数列排序，合并相邻的有序子数列，最终形成一个完整的有序数列（【治】）。
-
【分】阶段：递归拆分子序列的过程，递归深度为
log2n
-
【合】阶段：将两个已经有序的、相邻的子序列合并成一个有序的序列，效率可以达到
O(n)
以最后一次合并为例：[4,5,7,8]、[1,2,3,6]
-
JavaScript版的实现function sort(arr, i, j) { // 直到拆分成只有一个元素的子序列 if(i >= j) return // 取中间值，分区 let mid = Math.floor((i + j) / 2) // 1. 拆分左侧一半 sort(arr, i, mid) // 2. 拆分右侧一半 sort(arr, mid+1, j) // 比较, 合并左侧和右侧的结果 merge(arr, i, mid, j) } function merge(arr, left, mid, last) { // 一个临时数组 及其角标指针, 存储排序后的元素。即：归并排序 需要申请额外的空间 let temp = [], k = 0 // 左侧的起始角标 i, 右侧的起始角标 j let i = left, j = mid + 1 while(i <= mid && j <= last) { // 左侧和右侧都是有序的, 一次比较，把较小的先放进临时数组 // 即：相等的元素不会交换顺序，故归并排序是稳定的 if(arr[i] < arr[j]) { temp[k++] = arr[i++] } else { temp[k++] = arr[j++] } } // 左侧子序列 和 右侧子序列 的长度不一定是相等的，但都是有序的， // 所以多出来的可以直接放进临时数组中 while(i <= mid) { temp[k++] = arr[i++] } while(j <= last) { temp[k++] = arr[j++] } // 把排好序的数组temp, 添加进原数组中 for(let n = 0; n < k; n++) { arr[left+n] = temp[n] } } let arr = [53, 16, 88, 79, 93, 19, 47, 20] // 0 1 2 3 4 5 6 7 let i = 0, j = arr.length - 1 sort(arr, i, j) // [16, 19, 20, 47, 53, 79, 88, 93]
【归并排序】的效率是比较高的，设数列长为N，将数列分开成小数列一共要 logN 步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为 O(N*logN)。
因为【归并排序】每次都是在 相邻 的数据中进行操作，所以【归并排序】在 O(N*logN) 的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。
快速排序
【快速排序】也是采用【分治算法】实现的，是对【冒泡算法】的改进。与【归并排序】不同的是，它需要从数列中挑出一个元素作为 基准。
- 【分区】操作： 所有元素比 基准 小的摆放在 基准 前面，比 基准值 大的摆在 基准 的后面（相同的数可以到任一边）。在这个分区退出之后，基准值 就处于数列的中间位置。
- 递归地重复【分区操作】，直到分区内只有一个元素。
【快速排序】的难点在于 如何选取【基准点】，并按照【基准点】排序?
为了简单起见，以第一个元素作为 基准值
-
填坑法
思路：-
i=begin, j=last，将基准挖出，形成第一个坑arr[i] - 从右向左（
j--）找比基准值小的数，填入arr[i]的坑中，并把基准值填入arr[j] - 从左向右（
i++）找比基准值大的数，填入arr[j]的坑中，并把基准值填入arr[i] - 重复步骤
2-3，直至i >= j，则第一个分区完成，基准值左侧是比基准小的数，基准值右侧是比基准大的数，分别对左分区和有分区进行排序。
function sort(arr, begin, last) { if(begin >= last) { return } let i = begin, j = last, mid let base = arr[i] while(true) { // j 从后向前找比 base 小的数, 并放到基准值左侧 while(i !== j) { if(arr[j] < base) { // 找到了, 与基准值交换位置 arr[i] = arr[j] arr[j] = base // j 指向基准值 break } else { // 没找到, 则向后移动角标, 继续查找 j-- } } if(i >= j) { // 结束了, 记录基准值的角标 j mid = j break } // i 从前向后找比 base 大的数, 并放到基准值右侧 while(i !== j) { if(arr[i] > base) { // 找到了, 与基准值交换位置 arr[j] = arr[i] arr[i] = base // i 总是指向基准值 break } else { // 没找到, 则向后移动角标, 继续查找 i++ } } if(i >= j) { // 结束了, 记录基准值的角标 i mid = i break } } // 左分区 sort(arr, begin, mid-1) // 右分区 sort(arr, mid + 1, last) } let arr = [53, 16, 88, 79, 93, 19, 47, 20] // 0 1 2 3 4 5 6 7 let i = 0, j = arr.length - 1 sort(arr, i, j) -
-
交换法
思路：- 分别设置左右两个指针：
i=begin, j=last - 以左侧第一个元素为基准时，先移动右侧指针
j（稍后解释为什么） - 当
j遇到比基准小的数时，停止扫描；开始扫描左侧指针i - 当
i遇到比基准大的数时，停止扫描，并交换i和j处的值，此时i处的元素值一定比基准小 - 继续移动指针
j，重复步骤3-4，直到j与i相遇，则交换基准与i/j处的元素值； - 至此，第一个分区完成。基准值左侧一定是比基准小的数，基准值右侧是比基准大的数，然后分别对左分区和有分区进行排序。
注：为什么先移动右指针
j？当然，这不是绝对的，这取决于基准的位置，因为当两个指针相遇时，需要与基准交换元素值。当基准值在左边时，必须确保指针相遇的值一定比基准小，而左指针i始终指向小于基准值的元素，所以让右指针j先移动，让j向i靠拢，最终相遇。function sort(arr, begin, last) { if(begin >= last) { // 结束 return } let base = arr[begin] let i = begin, j = last while(i < j) { // 先移动右侧指针j, 找比基准值小的数 while(i < j && arr[j] >= base) { j-- } // 再移动左侧指针i, 找比基准值大的数 while(i < j && arr[i] <= base) { i++ } if(i < j) { // i 记录比基准值大的值, j 记录比基准值小的值, 交换元素值 let temp = arr[i] arr[i] = arr[j] arr[j] = temp } } // 此时 i === j, 且 i 处的元素一定比基准值小, 交换元素值 arr[begin] = arr[i] arr[i] = base // 第一次分区结束, 以基准值的位置i 为分区线, 递归分区比较 // 1. 左侧分区 sort(arr, begin, i - 1) // 2. 右侧分区 sort(arr, i + 1, last) } - 分别设置左右两个指针：
【快速排序】是不稳定的，它的速度与【基准点】有关，【基准点】的好坏大大影响速度。
- 最差情况下，划分由
n个元素构成的数组需要进行n次比较和n次移动，因此划分所需时间为O(n)。最差时间复杂度(n-1)+(n-2)+…+2+1= O(n^2) - 在最佳情况下，每次将数组划分为规模大致相等的两部分。和【归并排序】的分析相似，快速排序的
T(n) = O(nlogn)
求数组中第K个最大（小）元素
思路：这也是分治思想的应用，与【快速排序】类似。但不同的是，【快速排序】每次都要处理基准两侧的分区，而【求第K个最大（小）元素】只需要处理一侧分区即可。
求最接近原点的 K 个点
找出最大子序列
求 x 的 n 次幂
棋盘覆盖问题
整数划分问题
全排列问题
汉诺塔问题
大整数乘法
快速傅里叶变换
