歸并排序

要排序一個(gè)數(shù)組，先把數(shù)組從中間分成前后兩部分，然后對(duì)前后兩部分分別排序，再將排好序的兩部分合并在一起。如下圖：

歸并排序分解圖

重點(diǎn)：

歸并排序使用的是分治思想。分治，就是分而治之，將一個(gè)大問(wèn)題分解成小的子問(wèn)題來(lái)解決。

分治思想跟遞歸思想很像，分治算法一般是用遞歸實(shí)現(xiàn)。

分治是一種解決問(wèn)題的處理思想，遞歸是一種編程技巧。

回憶一下之前學(xué)習(xí)遞歸的編程技巧：分析得出遞推公式，然后找到終止條件。

偽代碼如下：

// 歸并排序算法, A是數(shù)組，n表示數(shù)組大小
merge_sort(A, n) {
    merge_sort_c(A, 0, n-1)
}
// 遞歸調(diào)用函數(shù)
merge_sort_c(A, p, r) {
    // 遞歸終止條件
    if p >= r then return
    // 取p到r之間的中間位置q
    q = (p+r) / 2
    // 分治遞歸
    merge_sort_c(A, p, q)
    merge_sort_c(A, q+1, r)
    // 將A[p...q]和A[q+1...r]合并為A[p...r]
    merge(A[p...r], A[p...q], A[q+1...r])
}

merge(A[p...r], A[p...q], A[q+1...r]) {
    var i := p，j := q+1，k := 0 // 初始化變量i, j, k 
    var tmp := new array[0...r-p] // 申請(qǐng)一個(gè)大小跟A[p...r]一樣的臨時(shí)數(shù)組
    while i<=q AND j<=r do {
        if A[i] <= A[j] {
            tmp[k++] = A[i++] // i++等于i:=i+1
        } else {
            tmp[k++] = A[j++]
        }
    }
    // 判斷哪個(gè)子數(shù)組中有剩余的數(shù)據(jù)
    var start := i，end := q
    if j<=r then start := j, end:=r
    // 將剩余的數(shù)據(jù)拷貝到臨時(shí)數(shù)組tmp
    while start <= end do {
        tmp[k++] = A[start++]
    }
    // 將tmp中的數(shù)組拷貝回A[p...r]
    for i:=0 to r-p do {
        A[p+i] = tmp[i]
    }
}

歸并排序的性能分析

第一，歸并排序是穩(wěn)定的排序算法嗎？

歸并排序穩(wěn)不穩(wěn)定，關(guān)鍵看merge()函數(shù)。合并兩個(gè)數(shù)組時(shí)，保證相等元素的前后順序不變即可。

第二，歸并排序的時(shí)間復(fù)雜度是多少？

不僅遞歸求解的問(wèn)題可以寫(xiě)成遞推公式，遞歸代碼的時(shí)間復(fù)雜度也可以寫(xiě)成遞推公式。

定義求解問(wèn)題a的時(shí)間是T(a)，求解問(wèn)題b、c的時(shí)間分別是T(b)和T(c)，可以得到以下遞推關(guān)系式：

進(jìn)而得到如下的計(jì)算公式：

進(jìn)一步分解計(jì)算過(guò)程：

當(dāng)時(shí)，也就是，得到。將代入公式，得到。

用大O標(biāo)記法表示就是O(nlogn)

第三，歸并排序的空間復(fù)雜度是多少？

遞歸代碼的空間復(fù)雜度不像時(shí)間復(fù)雜度那樣累加。

盡管每次合并操作都需要申請(qǐng)額外的內(nèi)存空間，但合并完成之后，臨時(shí)開(kāi)辟的內(nèi)存空間就被釋放掉了。

所以空間復(fù)雜度是O(n)。

快速排序

快排思路：從排序數(shù)組中選擇任意一個(gè)數(shù)據(jù)作為privot（分區(qū)點(diǎn)），遍歷數(shù)組（p到r）之間的數(shù)據(jù)，將小于pivot的放到左邊，將大于pivot的放在后邊，將pivot放在中間。經(jīng)過(guò)這一步驟，將數(shù)組p到r之間的數(shù)據(jù)分成三個(gè)部分：

快速排序之分區(qū)

將上面的過(guò)程用遞推公式來(lái)表示：

偽代碼：

// 快速排序，A是數(shù)組，n表示數(shù)組的大小
quick_sort(A, n) {
    quick_sort_c(A, 0, n-1)
}
// 快速排序遞歸函數(shù)，p,r為下標(biāo)
quick_sort_c(A, p, r) {
    if p >= r then return
    q = partition(A, p, r) // 獲取分區(qū)點(diǎn)
    quick_sort_c(A, p, q-1)
    quick_sort_c(A, q+1, r)
}

partition(A, p, r) {
    pivot := A[r]
    i := p
    for j := p to r-1 do {
        if A[j] < pivot {
            swap A[i] with A[j]
            i := i+1
        }
    }
    swap A[i] with A[r]
    return i
}

<font color=red>注：一般pivot選擇區(qū)間數(shù)組的最后一個(gè)值。</font>

快速排序的性能分析

第一，快速排序是穩(wěn)定的排序算法嗎？

快排是不穩(wěn)定的排序算法。在分區(qū)操作時(shí)，相同元素的先后順序會(huì)改變。

第二，快速排序的時(shí)間復(fù)雜度是多少？

快排也是用遞歸來(lái)實(shí)現(xiàn)，歸并排序的公式同樣適用于快排。

所以，快排的時(shí)間復(fù)雜度也是O(nlogn)。

但是，公式成立的前提是每次分區(qū)操作選擇的pivot都很合適，正好能將大區(qū)間對(duì)待地一分為二。在極端的情況下，每次選擇的pivot，分區(qū)都是不均等的，這種情況下，時(shí)間復(fù)雜度就從O(nlogn)退化為。

第三，快速排序的空間復(fù)雜度是多少？

快排是原地的排序算法，空間復(fù)雜度是O(1)。

快速排序和歸并排序的區(qū)別

快速排序和歸并排序用的都是分治思想，遞推公式和遞歸代碼也非常相似，區(qū)別在于：

• 歸并排序處理過(guò)程是由下到上的。而快排是由上到下的。
• 歸并排序是非原地排序算法（主要原因是合并函數(shù)無(wú)法在原地執(zhí)行）?？焖倥判蚴窃嘏判蛩惴ǎㄍㄟ^(guò)設(shè)計(jì)巧妙的原地分區(qū)函數(shù)，實(shí)現(xiàn)原地排序）。

歸并排序 vs 快速排序

課后思考

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

按照日期/小時(shí)/分鐘來(lái)區(qū)分（主要看日期有多大），遍歷文件，把記錄分別記錄到對(duì)應(yīng)的文件里，然后再對(duì)所有文件逐一排序，最后再把文件按照日期來(lái)合并。假如存在文件超過(guò)1G的情況，再把文件細(xì)分。

每個(gè)文件內(nèi)可以使用快排來(lái)進(jìn)行排序。