Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（七）：歸并排序

一、實(shí)現(xiàn)原理

今天介紹比前面三種排序算法性能更好的排序算法 —— 歸并排序。

所謂歸并排序，指的是如果要排序一個(gè)數(shù)據(jù)序列，我們可以先把該序列從中間分成前后兩部分，然后對(duì)這兩部分分別做排序操作，再將排好序的兩部分合并在一起，這樣整個(gè)數(shù)據(jù)序列就都有序了。

歸并排序使用了分治思想，分治，顧名思義，就是分而治之，將一個(gè)大問(wèn)題分解成小的子問(wèn)題來(lái)解決。說(shuō)到這里，可能你會(huì)聯(lián)想起我們之前講到的一個(gè)編程技巧 —— 遞歸，沒(méi)錯(cuò)，歸并排序就是通過(guò)遞歸來(lái)實(shí)現(xiàn)的。這個(gè)遞歸的公式是每次都將傳入的待排序數(shù)據(jù)序列一分為二，直到變成不能繼續(xù)分割的最小區(qū)間單元，然后將最小區(qū)間單元數(shù)據(jù)排序后合并起來(lái)，最終返回的就是排序好的數(shù)據(jù)序列了。圖示如下：

由于涉及到遞歸，所以歸并排序從理解上要比前面三個(gè)排序要困難一些，還是建議通過(guò)這個(gè)動(dòng)態(tài)圖幫助理解：https://visualgo.net/zh/sorting（在界面頂部選擇歸并排序，然后在左下角點(diǎn)擊執(zhí)行即可）。

二、示例代碼

通過(guò)上面的分析，我們知道歸并=遞歸+合并，對(duì)應(yīng)的 Go 實(shí)現(xiàn)代碼如下：

package main

import (
    "fmt"
)

// 歸并排序
func mergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }

    // 獲取分區(qū)位置
    p := len(nums) / 2
    // 通過(guò)遞歸分區(qū)
    left := mergeSort(nums[0:p])
    right := mergeSort(nums[p:])
    // 排序后合并
    return merge(left, right)
}

// 排序合并
func merge(left []int, right []int) []int {
    i, j := 0, 0
    m, n := len(left), len(right)
    // 用于存放結(jié)果集
    var result []int
    for {
        // 任何一個(gè)區(qū)間遍歷完，則退出
        if i >= m || j >= n {
            break
        }
        // 對(duì)所有區(qū)間數(shù)據(jù)進(jìn)行排序
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    // 如果左側(cè)區(qū)間還沒(méi)有遍歷完，將剩余數(shù)據(jù)放到結(jié)果集
    if i != m {
        for ; i < m; i++ {
            result = append(result, left[i])
        }
    }

    // 如果右側(cè)區(qū)間還沒(méi)有遍歷完，將剩余數(shù)據(jù)放到結(jié)果集
    if j != n {
        for ; j < n; j++ {
            result = append(result, right[j])
        }
    }

    // 返回排序后的結(jié)果集
    return result
}

func main() {
    nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
    sortedNums := mergeSort(nums)
    fmt.Println(sortedNums)
}

運(yùn)行上述代碼，打印結(jié)果如下：

三、性能分析

最后我們來(lái)看下歸并排序的性能：

• 歸并排序不涉及相等元素位置交換，是穩(wěn)定的排序算法；

• 時(shí)間復(fù)雜度是 O(nlogn)，要優(yōu)于冒泡排序和插入排序的 O(n²)；

• 歸并排序需要額外的空間存放排序數(shù)據(jù)，不是原地排序，最多需要和待排序數(shù)據(jù)序列同樣大小的空間，所以空間復(fù)雜度是 O(n)。

歸并排序的時(shí)間復(fù)雜度推導(dǎo)過(guò)程

歸并的思路是將一個(gè)復(fù)雜的問(wèn)題 a 遞歸拆解為子問(wèn)題 b 和 c，再將子問(wèn)題計(jì)算結(jié)果合并，最終得到問(wèn)題的答案，這里我們將歸并排序總的時(shí)間復(fù)雜度設(shè)為 T(n)，則 T(n) = 2*T(n/2) + n，其中 T(n/2) 是遞歸拆解的第一步對(duì)應(yīng)子問(wèn)題的時(shí)間復(fù)雜度，n 則是排序合并函數(shù)的時(shí)間復(fù)雜度（一個(gè)循環(huán)遍歷），依次類推，我們可以推導(dǎo) T(n) 的計(jì)算邏輯如下：

T(n) = 2*T(n/2) + n
        = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
        = 4(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
        = ...
        = 2^k*T(n/2^k) + k*n

遞歸到最后，T(n/2^k)≈T(1)，也就是 n/2^k = 1，計(jì)算歸并排序的時(shí)間復(fù)雜度，就演變成了計(jì)算 k 的值，2^k = n，所以 k=log₂n，我們把 k 的值帶入上述 T(n) 的推導(dǎo)公式，得到：

T(n) = n*T(1) + n*log2n = n(C + log2n)

注：上述公式中 2 是下標(biāo)，即 log₂n。

把常量和低階忽略，所以 T(n) = nlogn。