一、分治思想

1.分治思想：分治，顧明思意，就是分而治之，將一個(gè)大問題分解成小的子問題來解決，小的子問題解決了，大問題也就解決了。

2.分治與遞歸的區(qū)別：分治算法一般都用遞歸來實(shí)現(xiàn)的。分治是一種解決問題的處理思想，遞歸是一種編程技巧。

二、歸并排序

1.算法原理

image.png

??????先把數(shù)組從中間分成前后兩部分，然后對(duì)前后兩部分分別進(jìn)行排序，再將排序好的兩部分合并到一起，這樣整個(gè)數(shù)組就有序了。這就是歸并排序的核心思想。如何用遞歸實(shí)現(xiàn)歸并排序呢？寫遞歸代碼的技巧就是分寫得出遞推公式，然后找到終止條件，最后將遞推公式翻譯成遞歸代碼。遞推公式怎么寫？如下

遞推公式：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
終止條件：p >= r 不用再繼續(xù)分解

2.代碼實(shí)現(xiàn)

image.png

// 歸并排序
const mergeArr = (left, right) => {
    let temp = []
    let leftIndex = 0
    let rightIndex = 0
    // 判斷2個(gè)數(shù)組中元素大小，依次插入數(shù)組
    while (left.length > leftIndex && right.length > rightIndex) {
        if (left[leftIndex] <= right[rightIndex]) {
            temp.push(left[leftIndex])
            leftIndex++
        } else {
            temp.push(right[rightIndex])
            rightIndex++
        }
    }
    // 合并 多余數(shù)組
    return temp.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
}

const mergeSort = (arr) => {
    // 當(dāng)任意數(shù)組分解到只有一個(gè)時(shí)返回。
    if (arr.length <= 1) return arr
    const middle = Math.floor(arr.length / 2) // 找到中間值
    const left = arr.slice(0, middle) // 分割數(shù)組
    const right = arr.slice(middle)
    // 遞歸 分解 合并
    return mergeArr(mergeSort(left), mergeSort(right))
}

const res = mergeSort([3,1,5,4,0])
console.log(res)

3.性能分析

1）算法穩(wěn)定性：

??????歸并排序穩(wěn)不穩(wěn)定關(guān)鍵要看merge()函數(shù)，也就是兩個(gè)子數(shù)組合并成一個(gè)有序數(shù)組的那部分代碼。在合并的過程中，如果 A[p…q] 和 A[q+1…r] 之間有值相同的元素，那我們就可以像偽代碼中那樣，先把 A[p…q] 中的元素放入tmp數(shù)組，這樣 就保證了值相同的元素，在合并前后的先后順序不變。所以，歸并排序是一種穩(wěn)定排序算法。

2）時(shí)間復(fù)雜度：分析歸并排序的時(shí)間復(fù)雜度就是分析遞歸代碼的時(shí)間復(fù)雜度

??????如何分析遞歸代碼的時(shí)間復(fù)雜度？
??????遞歸的適用場(chǎng)景是一個(gè)問題a可以分解為多個(gè)子問題b、c，那求解問題a就可以分解為求解問題b、c。問題b、c解決之后，我們?cè)侔裝、c的結(jié)果合并成a的結(jié)果。若定義求解問題a的時(shí)間是T(a)，則求解問題b、c的時(shí)間分別是T(b)和T(c)，那就可以得到這樣的遞推公式：T(a) = T(b) + T(c) + K，其中K等于將兩個(gè)子問題b、c的結(jié)果合并成問題a的結(jié)果所消耗的時(shí)間。這里有一個(gè)重要的結(jié)論：不僅遞歸求解的問題可以寫成遞推公式，遞歸代碼的時(shí)間復(fù)雜度也可以寫成遞推公式。套用這個(gè)公式，那么歸并排序的時(shí)間復(fù)雜度就可以表示為：
T(1) = C； n=1 時(shí)，只需要常量級(jí)的執(zhí)行時(shí)間，所以表示為 C。
T(n) = 2T(n/2) + n； n>1，其中n就是merge()函數(shù)合并兩個(gè)子數(shù)組的的時(shí)間復(fù)雜度O(n)。
T(n) = 2T(n/2) + n
= 2(2T(n/4) + n/2) + n = 4T(n/4) + 2n
= 4(2T(n/8) + n/4) + 2n = 8T(n/8) + 3n
= 8(2T(n/16) + n/8) + 3n = 16T(n/16) + 4n
......
= 2^k * T(n/2^k) + k * n
......
??????當(dāng)T(n/2^k)=T(1) 時(shí)，也就是 n/2^k=1，我們得到k=log2n。將k帶入上面的公式就得到T(n)=Cn+nlog2n。如用大O表示法，T(n)就等于O(nlogn)。所以，歸并排序的是復(fù)雜度時(shí)間復(fù)雜度就是O(nlogn)。

3）空間復(fù)雜度：歸并排序算法不是原地排序算法，空間復(fù)雜度是O(n)

??????為什么？因?yàn)闅w并排序的合并函數(shù)，在合并兩個(gè)數(shù)組為一個(gè)有序數(shù)組時(shí)，需要借助額外的存儲(chǔ)空間。為什么空間復(fù)雜度是O(n)而不是O(nlogn)呢？如果我們按照分析遞歸的時(shí)間復(fù)雜度的方法，通過遞推公式來求解，那整個(gè)歸并過程需要的空間復(fù)雜度就是O(nlogn)，但這種分析思路是有問題的！因?yàn)?，在?shí)際上，遞歸代碼的空間復(fù)雜度并不是像時(shí)間復(fù)雜度那樣累加，而是這樣的過程，即在每次合并過程中都需要申請(qǐng)額外的內(nèi)存空間，但是合并完成后，臨時(shí)開辟的內(nèi)存空間就被釋放掉了，在任意時(shí)刻，CPU只會(huì)有一個(gè)函數(shù)在執(zhí)行，也就只會(huì)有一個(gè)臨時(shí)的內(nèi)存空間在使用。臨時(shí)空間再大也不會(huì)超過n個(gè)數(shù)據(jù)的大小，所以空間復(fù)雜度是O(n)。

三、快速排序

1.算法原理

??????快排的思想是這樣的：如果要排序數(shù)組中下標(biāo)從p到r之間的一組數(shù)據(jù)，我們選擇p到r之間的任意一個(gè)數(shù)據(jù)作為pivot（分區(qū)點(diǎn)）。然后遍歷p到r之間的數(shù)據(jù)，將小于pivot的放到左邊，將大于pivot的放到右邊，將povit放到中間。經(jīng)過這一步之后，數(shù)組p到r之間的數(shù)據(jù)就分成了3部分，前面p到q-1之間都是小于povit的，中間是povit，后面的q+1到r之間是大于povit的。根據(jù)分治、遞歸的處理思想，我們可以用遞歸排序下標(biāo)從p到q-1之間的數(shù)據(jù)和下標(biāo)從q+1到r之間的數(shù)據(jù)，直到區(qū)間縮小為1，就說明所有的數(shù)據(jù)都有序了。

遞推公式：quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
終止條件：p >= r

2.代碼實(shí)現(xiàn)

var quickSort = function(arr) {
    if (arr.length <= 1) {//如果數(shù)組長(zhǎng)度小于等于1無需判斷直接返回即可 
        return arr;
    }
    //取基準(zhǔn)點(diǎn) 
    var pivotIndex = Math.floor(arr.length / 2)
    //取基準(zhǔn)點(diǎn)的值,splice(index,1)函數(shù)可以返回?cái)?shù)組中被刪除的那個(gè)數(shù)
    var pivot = arr.splice(pivotIndex, 1)[0];
    var left = [];//存放比基準(zhǔn)點(diǎn)小的數(shù)組
    var right = [];//存放比基準(zhǔn)點(diǎn)大的數(shù)組 
    for (var i = 0; i < arr.length; i++){ //遍歷數(shù)組，進(jìn)行判斷分配 
    　　if (arr[i] < pivot) {
    　　　　left.push(arr[i]);//比基準(zhǔn)點(diǎn)小的放在左邊數(shù)組 
    　　} else {
    　　　　right.push(arr[i]);//比基準(zhǔn)點(diǎn)大的放在右邊數(shù)組 
    　　}
    }
    //遞歸執(zhí)行以上操作,對(duì)左右兩個(gè)數(shù)組進(jìn)行操作，直到數(shù)組長(zhǎng)度為<=1； 
    return quickSort(left).concat([pivot], quickSort(right));
};

console.log(quickSort([5,8,3,6,9,4]))

3.性能分析

1）算法穩(wěn)定性：

??????因?yàn)榉謪^(qū)過程中涉及交換操作，如果數(shù)組中有兩個(gè)8，其中一個(gè)是pivot，經(jīng)過分區(qū)處理后，后面的8就有可能放到了另一個(gè)8的前面，先后順序就顛倒了，所以快速排序是不穩(wěn)定的排序算法。比如數(shù)組[1,2,3,9,8,11,8]，取后面的8作為pivot，那么分區(qū)后就會(huì)將后面的8與9進(jìn)行交換。

2）時(shí)間復(fù)雜度：最好、最壞、平均情況

??????快排也是用遞歸實(shí)現(xiàn)的，所以時(shí)間復(fù)雜度也可以用遞推公式表示。
如果每次分區(qū)操作都能正好把數(shù)組分成大小接近相等的兩個(gè)小區(qū)間，那快排的時(shí)間復(fù)雜度遞推求解公式跟歸并的相同。
T(1) = C； n=1 時(shí)，只需要常量級(jí)的執(zhí)行時(shí)間，所以表示為 C。
T(n) = 2*T(n/2) + n； n>1
??????所以，快排的時(shí)間復(fù)雜度也是O(nlogn)。
??????如果數(shù)組中的元素原來已經(jīng)有序了，比如1，3，5，6，8，若每次選擇最后一個(gè)元素作為pivot，那每次分區(qū)得到的兩個(gè)區(qū)間都是不均等的，需要進(jìn)行大約n次的分區(qū)，才能完成整個(gè)快排過程，而每次分區(qū)我們平均要掃描大約n/2個(gè)元素，這種情況下，快排的時(shí)間復(fù)雜度就是O(n^2)。
前面兩種情況，一個(gè)是分區(qū)及其均衡，一個(gè)是分區(qū)極不均衡，它們分別對(duì)應(yīng)了快排的最好情況時(shí)間復(fù)雜度和最壞情況時(shí)間復(fù)雜度。那快排的平均時(shí)間復(fù)雜度是多少呢？T(n)大部分情況下是O(nlogn)，只有在極端情況下才是退化到O(n^2)，而且我們也有很多方法將這個(gè)概率降低。

3）空間復(fù)雜度：快排是一種原地排序算法，空間復(fù)雜度是O(1)

四、歸并排序與快速排序的區(qū)別

??????歸并和快排用的都是分治思想，遞推公式和遞歸代碼也非常相似，那它們的區(qū)別在哪里呢？
??????1.歸并排序，是先遞歸調(diào)用，再進(jìn)行合并，合并的時(shí)候進(jìn)行數(shù)據(jù)的交換。所以它是自下而上的排序方式。何為自下而上？就是先解決子問題，再解決父問題。

??????2.快速排序，是先分區(qū)，在遞歸調(diào)用，分區(qū)的時(shí)候進(jìn)行數(shù)據(jù)的交換。所以它是自上而下的排序方式。何為自上而下？就是先解決父問題，再解決子問題。

五、思考

??????1.O(n)時(shí)間復(fù)雜度內(nèi)求無序數(shù)組中第K大元素，比如4，2，5，12，3這樣一組數(shù)據(jù)，第3大元素是4。
我們選擇數(shù)組區(qū)間A[0...n-1]的最后一個(gè)元素作為pivot，對(duì)數(shù)組A[0...n-1]進(jìn)行原地分區(qū)，這樣數(shù)組就分成了3部分，A[0...p-1]、A[p]、A[p+1...n-1]。

??????如果p+1=K，那A[p]就是要求解的元素；如果K>p+1，說明第K大元素出現(xiàn)在A[p+1...n-1]區(qū)間，我們按照上面的思路遞歸地在A[p+1...n-1]這個(gè)區(qū)間查找。同理，如果K<p+1，那我們就在A[0...p-1]區(qū)間查找。
時(shí)間復(fù)雜度分析？

??????第一次分區(qū)查找，我們需要對(duì)大小為n的數(shù)組進(jìn)行分區(qū)操作，需要遍歷n個(gè)元素。第二次分區(qū)查找，我們需要對(duì)大小為n/2的數(shù)組執(zhí)行分區(qū)操作，需要遍歷n/2個(gè)元素。依次類推，分區(qū)遍歷元素的個(gè)數(shù)分別為n、n/2、n/4、n/8、n/16......直到區(qū)間縮小為1。如果把每次分區(qū)遍歷的元素個(gè)數(shù)累加起來，就是等比數(shù)列求和，結(jié)果為2n-1。所以，上述解決問題的思路為O(n)。

??????2.有10個(gè)訪問日志文件，每個(gè)日志文件大小約為300MB，每個(gè)文件里的日志都是按照時(shí)間戳從小到大排序的?，F(xiàn)在需要將這10個(gè)較小的日志文件合并為1個(gè)日志文件，合并之后的日志仍然按照時(shí)間戳從小到大排列。如果處理上述任務(wù)的機(jī)器內(nèi)存只有1GB，你有什么好的解決思路能快速地將這10個(gè)日志文件合并？