算法思想
分治，分而治之，將原問題劃分成 n 個規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題，這些規(guī)模小的問題與原問題是同質(zhì)的，本質(zhì)上還是同一個問題，遞歸解決這些子問題，然后合并其結(jié)果，就能得到原問題的解。（PS：當然，遞歸不是必須的）
空間換時間，來實現(xiàn)算法時間復(fù)雜度的優(yōu)化
【分治算法】是很多高效算法的基礎(chǔ)，諸如快速排序、歸并排序、傅立葉變換、二分搜索
特征
- 原問題的規(guī)?？s小到一定的程度就很容易解決
--絕大多數(shù)問題都可以滿足，因為問題的計算復(fù)雜性通常都是隨著問題規(guī)模的增加而增加 - 原問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有【最優(yōu)子結(jié)構(gòu)性質(zhì)】
--應(yīng)用分治法的前提，大多數(shù)問題也可以滿足，它反映了遞歸思想的應(yīng)用 - 分解出的子問題的解可以合并為該問題的解
--能否利用分治法的關(guān)鍵特征。如果只具備第一、第二特征，而不具備第三特征，則可以考慮動態(tài)規(guī)劃或貪心算法 - 分解出的各個子問題相互獨立，即【子問題之間不包括公共的子問題】
--涉及分治算法的效率，如果各個子問題不是相互獨立的，分治算法要做很多不必需要的工作，重復(fù)地解決公共子問題，此時采用動態(tài)規(guī)劃會比較好
前三個特征是使用分治法的關(guān)鍵，而特征4 涉及到分治法的效率問題。如果不符合3、4特征，可以嘗試使用動態(tài)規(guī)劃或胎心算法來解決。
【動態(tài)規(guī)劃】是一種特殊的分治，貪心算法是一種特殊的動態(tài)規(guī)劃
適用范圍：
- 分治算法：最優(yōu)子結(jié)構(gòu)
- 動態(tài)規(guī)劃：最優(yōu)子結(jié)構(gòu)、重疊子問題
- 貪心算法：最優(yōu)子結(jié)構(gòu)、重疊子問題、貪心選擇性質(zhì)
分支模式在每一層上都有三個步驟：
- 分解，將原問題分解成一系列與原問題同質(zhì)的子問題
- 解決，遞歸解決各個子問題，若子問題足夠小，則直接求解
- 合并，將子問題的結(jié)果合并成原問題的解
舉個例子
有一個很經(jīng)典的問題：有100枚硬幣，其中有1枚略輕一些的假幣，如果用天平秤，請問至少稱幾次一定能找到這枚假幣？
如果用傳統(tǒng)的逐枚比較法，顯然至少需要比較50次
比較第i個與第i+1個的重量，若相等，則i++，繼續(xù)比較，直到重量不相等，并輸出較輕的硬幣編號。-
采用分治算法
- 將
100枚硬幣分成3份：33、33、34 - 稱重
1、2份，若天枰平衡，則假幣必在另外34枚中；若不平衡，則在較輕的那份33枚中 - 再將
34枚分成3份：11、11、12（或?qū)?33枚分成11、11、11） - 稱重兩組
11枚的硬幣，若平衡，則假幣在12枚里（或第三份11枚）；若不平衡，則在較輕的那份11枚中 - 將
12枚分成3份：4、4、4（或?qū)?11枚分成4、4、3），稱重方法同上 - 將
4枚分成3份：1、1、2，稱重1/1，若平衡，則稱重剩下的2枚，較輕的1枚是假幣；若不平衡，較輕的1枚是假幣。（或?qū)?3枚分成1、1、1，稱重1/1，若平衡，則剩下的1枚是假幣；若不平衡，則較輕的1枚是假幣）
綜上所述，最多只需要
5次就能解決這個問題！ - 將
通過觀察 1-2、3-4、5-6 發(fā)現(xiàn)，除了硬幣數(shù)量變化了其他步驟完全一樣，即 這是一個子問題的分解過程，100-33-11-3，將一個大問題分解成了容易解決的小問題，且 這些小問題相互獨立，每一個 33 枚硬幣和其他硬幣互不影響。
實際上類似于數(shù)學(xué)歸納法，先找到最小問題規(guī)模的求解方程，然后考慮隨著問題規(guī)模增大時的求解方程，然后根據(jù)方程式設(shè)計遞歸程序（當然，遞歸不是必須的），自頂而下的解決問題。
歸并排序
歸并排序是【分治算法】的典型應(yīng)用：多次分解數(shù)列，直至子數(shù)列中只有一個元素（【分】）。然后對子數(shù)列排序，合并相鄰的有序子數(shù)列，最終形成一個完整的有序數(shù)列（【治】）。
-
【分】階段：遞歸拆分子序列的過程，遞歸深度為
log2n
-
【合】階段：將兩個已經(jīng)有序的、相鄰的子序列合并成一個有序的序列，效率可以達到
O(n)
以最后一次合并為例：[4,5,7,8]、[1,2,3,6]
-
JavaScript版的實現(xiàn)function sort(arr, i, j) { // 直到拆分成只有一個元素的子序列 if(i >= j) return // 取中間值，分區(qū) let mid = Math.floor((i + j) / 2) // 1. 拆分左側(cè)一半 sort(arr, i, mid) // 2. 拆分右側(cè)一半 sort(arr, mid+1, j) // 比較, 合并左側(cè)和右側(cè)的結(jié)果 merge(arr, i, mid, j) } function merge(arr, left, mid, last) { // 一個臨時數(shù)組 及其角標指針, 存儲排序后的元素。即：歸并排序 需要申請額外的空間 let temp = [], k = 0 // 左側(cè)的起始角標 i, 右側(cè)的起始角標 j let i = left, j = mid + 1 while(i <= mid && j <= last) { // 左側(cè)和右側(cè)都是有序的, 一次比較，把較小的先放進臨時數(shù)組 // 即：相等的元素不會交換順序，故歸并排序是穩(wěn)定的 if(arr[i] < arr[j]) { temp[k++] = arr[i++] } else { temp[k++] = arr[j++] } } // 左側(cè)子序列 和 右側(cè)子序列 的長度不一定是相等的，但都是有序的， // 所以多出來的可以直接放進臨時數(shù)組中 while(i <= mid) { temp[k++] = arr[i++] } while(j <= last) { temp[k++] = arr[j++] } // 把排好序的數(shù)組temp, 添加進原數(shù)組中 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]
【歸并排序】的效率是比較高的，設(shè)數(shù)列長為N，將數(shù)列分開成小數(shù)列一共要 logN 步，每步都是一個合并有序數(shù)列的過程，時間復(fù)雜度可以記為O(N)，故一共為 O(N*logN)。
因為【歸并排序】每次都是在 相鄰 的數(shù)據(jù)中進行操作，所以【歸并排序】在 O(N*logN) 的幾種排序方法（快速排序，歸并排序，希爾排序，堆排序）也是效率比較高的。
快速排序
【快速排序】也是采用【分治算法】實現(xiàn)的，是對【冒泡算法】的改進。與【歸并排序】不同的是，它需要從數(shù)列中挑出一個元素作為 基準。
- 【分區(qū)】操作： 所有元素比 基準 小的擺放在 基準 前面，比 基準值 大的擺在 基準 的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，基準值 就處于數(shù)列的中間位置。
- 遞歸地重復(fù)【分區(qū)操作】，直到分區(qū)內(nèi)只有一個元素。
【快速排序】的難點在于 如何選取【基準點】，并按照【基準點】排序?
為了簡單起見，以第一個元素作為 基準值
-
填坑法
思路：-
i=begin, j=last，將基準挖出，形成第一個坑arr[i] - 從右向左（
j--）找比基準值小的數(shù)，填入arr[i]的坑中，并把基準值填入arr[j] - 從左向右（
i++）找比基準值大的數(shù)，填入arr[j]的坑中，并把基準值填入arr[i] - 重復(fù)步驟
2-3，直至i >= j，則第一個分區(qū)完成，基準值左側(cè)是比基準小的數(shù)，基準值右側(cè)是比基準大的數(shù)，分別對左分區(qū)和有分區(qū)進行排序。
function sort(arr, begin, last) { if(begin >= last) { return } let i = begin, j = last, mid let base = arr[i] while(true) { // j 從后向前找比 base 小的數(shù), 并放到基準值左側(cè) while(i !== j) { if(arr[j] < base) { // 找到了, 與基準值交換位置 arr[i] = arr[j] arr[j] = base // j 指向基準值 break } else { // 沒找到, 則向后移動角標, 繼續(xù)查找 j-- } } if(i >= j) { // 結(jié)束了, 記錄基準值的角標 j mid = j break } // i 從前向后找比 base 大的數(shù), 并放到基準值右側(cè) while(i !== j) { if(arr[i] > base) { // 找到了, 與基準值交換位置 arr[j] = arr[i] arr[i] = base // i 總是指向基準值 break } else { // 沒找到, 則向后移動角標, 繼續(xù)查找 i++ } } if(i >= j) { // 結(jié)束了, 記錄基準值的角標 i mid = i break } } // 左分區(qū) sort(arr, begin, mid-1) // 右分區(qū) 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) -
-
交換法
思路：- 分別設(shè)置左右兩個指針：
i=begin, j=last - 以左側(cè)第一個元素為基準時，先移動右側(cè)指針
j（稍后解釋為什么） - 當
j遇到比基準小的數(shù)時，停止掃描；開始掃描左側(cè)指針i - 當
i遇到比基準大的數(shù)時，停止掃描，并交換i和j處的值，此時i處的元素值一定比基準小 - 繼續(xù)移動指針
j，重復(fù)步驟3-4，直到j與i相遇，則交換基準與i/j處的元素值； - 至此，第一個分區(qū)完成。基準值左側(cè)一定是比基準小的數(shù)，基準值右側(cè)是比基準大的數(shù)，然后分別對左分區(qū)和有分區(qū)進行排序。
注：為什么先移動右指針
j？當然，這不是絕對的，這取決于基準的位置，因為當兩個指針相遇時，需要與基準交換元素值。當基準值在左邊時，必須確保指針相遇的值一定比基準小，而左指針i始終指向小于基準值的元素，所以讓右指針j先移動，讓j向i靠攏，最終相遇。function sort(arr, begin, last) { if(begin >= last) { // 結(jié)束 return } let base = arr[begin] let i = begin, j = last while(i < j) { // 先移動右側(cè)指針j, 找比基準值小的數(shù) while(i < j && arr[j] >= base) { j-- } // 再移動左側(cè)指針i, 找比基準值大的數(shù) 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 // 第一次分區(qū)結(jié)束, 以基準值的位置i 為分區(qū)線, 遞歸分區(qū)比較 // 1. 左側(cè)分區(qū) sort(arr, begin, i - 1) // 2. 右側(cè)分區(qū) sort(arr, i + 1, last) } - 分別設(shè)置左右兩個指針：
【快速排序】是不穩(wěn)定的，它的速度與【基準點】有關(guān)，【基準點】的好壞大大影響速度。
- 最差情況下，劃分由
n個元素構(gòu)成的數(shù)組需要進行n次比較和n次移動，因此劃分所需時間為O(n)。最差時間復(fù)雜度(n-1)+(n-2)+…+2+1= O(n^2) - 在最佳情況下，每次將數(shù)組劃分為規(guī)模大致相等的兩部分。和【歸并排序】的分析相似，快速排序的
T(n) = O(nlogn)
求數(shù)組中第K個最大（?。┰?/h3>
思路：這也是分治思想的應(yīng)用，與【快速排序】類似。但不同的是，【快速排序】每次都要處理基準兩側(cè)的分區(qū)，而【求第K個最大（?。┰亍恐恍枰幚硪粋?cè)分區(qū)即可。
求最接近原點的 K 個點
找出最大子序列
求 x 的 n 次冪
棋盤覆蓋問題
整數(shù)劃分問題
全排列問題
漢諾塔問題
大整數(shù)乘法
快速傅里葉變換
