Go歸併排序演演算法的實現方法

2022-04-06 19:02:35

歸併排序的思想

與快速排序一樣，歸併排序採用的也是分治的策略，把原本的問題先分解成一些小問題進行求解，再把這些小問題各自的答案修整到一起得到原本問題的答案，從而達到分而治之的目的。

歸併排序演演算法會把要排序的序列分成長度相當的兩個子序列，當分無可分每個子序列中只有一個資料的時候，就對子序列進行歸併。

歸併指的是把兩個排序好的子序列合併成一個有序序列。該操作會一直重複執行，直到所有子序列歸併為一個整體為止。

歸併排序的過程下面我們依然用圖例過一遍歸併排序對一個序列進行排序的過程。

圖例出自—《我的第一本演演算法書》

首先，假設有下面這樣一個待排序的序列：

待排序的一串數位

將序列以對半分割的形式分成兩段。

把序列二分成兩段

再繼續對子序列進行對半分割，分解下去。

再繼續往下分

直到分無可分，每個子序列中只有一個資料。

分解到每個子序列只有一個資料

接下來對分割後的資料進行合併，合併時需要將數位按從小到大的順序排列。

合併序列時按大小排序

把 6 和 4 合併，合併時按照數位大小排序，合併後的順序為【4，6】，接下來把 3 和 7 合併，合併後的順序為【3，7】。

[繼續按照大小順序合併後面的序列]。

下面，我們看看怎麼合併【4，6】和【3，7】這兩個序列。合併這種含有多個數位的子序列時，要先比較首位數位，再移動較小的數位。

合併多元素的序列時，從首位開始比較，小的先移動

這裡要比較兩個子序列的首位數位是4 和 3。由於 4 > 3，所以合併序列時先移動 3。

4 > 3，所以合併序列時先移動 3

接下來，再按照比較兩個序列首位，小的先合併，大的留下來繼續比較的規則合併兩個序列。

4 小於 7，所以先移動 4 到合併的序列。

由於4<7，所以移動4

兩個子序列剩下的元素中，6 小於 7，所以先移動 6。

6 < 7 所以先移動 6

最後移動剩下的 7。

子序列最後剩下了7，合併到序列中去

遞迴執行上面的操作，直到所有的數位都合併到一個整體的序列上為止。

小序列合併成兩個大的序列

再繼續往完整的序列上合併

最後得到一個完整的排序完成的序列。

排序完成的序列

歸併排序的 Go 程式碼實現

下面上一個用歸併排序的Go程式碼實現，程式碼很簡單，實現步驟就都放在了程式碼的註釋裡，就不再多說啦，先收藏文章(也要記得點贊)，等有時間了自己在電腦上執行一下試試吧。

package main
import "fmt"
// 自頂向下歸併排序，排序範圍在 [begin,end) 的陣列
func MergeSort(array []int, begin int, end int) {
    // 元素數量大於1時才進入遞迴
    if end - begin > 1 {
        // 將陣列一分為二，分為 array[begin,mid) 和 array[mid,high)
        mid := begin + (end-begin+1)/2
        // 先將左邊排序好
        MergeSort(array, begin, mid)
        // 再將右邊排序好
        MergeSort(array, mid, end)
        // 兩個有序陣列進行合併
        merge(array, begin, mid, end)
    }
}
// 歸併操作
func merge(array []int, begin int, mid int, end int) {
    // 申請額外的空間來合併兩個有序陣列，這兩個陣列是 array[begin,mid),array[mid,end)
    leftSize := mid - begin         // 左邊陣列的長度
    rightSize := end - mid          // 右邊陣列的長度
    newSize := leftSize + rightSize // 輔助陣列的長度
    result := make([]int, 0, newSize)
    l, r := 0, 0
    for l < leftSize && r < rightSize {
        lValue := array[begin+l] // 左邊陣列的元素
        rValue := array[mid+r]   // 右邊陣列的元素
        // 小的元素先放進輔助陣列裡
        if lValue < rValue {
            result = append(result, lValue)
            l++
        } else {
            result = append(result, rValue)
            r++
        }
    // 將剩下的元素追加到輔助陣列後面
    result = append(result, array[begin+l:mid]...)
    result = append(result, array[mid+r:end]...)
    // 將輔助陣列的元素複製回原陣列，這樣該輔助空間就可以被釋放掉
    for i := 0; i < newSize; i++ {
        array[begin+i] = result[i]
    return

歸併排序的時間複雜度

老規矩，看完演演算法思想和實現步驟後，我們再來分析一下歸併排序演演算法的時間複雜度。

歸併排序中，分割序列所花費的時間不算在執行時間內 (可以當作序列本來就是分割好的)。在合併兩個已排好序的子序列時，只需依次比較處在序列首位資料的大小，然後移動較小的資料，因此只需花費和兩個子序列的長度相應的執行時間。也就是說，完成一行歸併所需的執行時間取決於這一行的資料量。

看一下這個圖便能得知，無論哪一行都是 n 個資料，所以每行的執行時間都為 O(n)。

歸併排序每一行的資料都是 n 個

而將長度為 n 的序列對半分割直到只有一個資料為止時，可以分成行，因此，總共有 log2n 行。也就是說，總的執行時間為，這與前面講到的快速排序相同。

到此這篇關於Go歸併排序演演算法的實現方法的文章就介紹到這了,更多相關go歸併排序演演算法內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Go歸併排序演演算法的實現方法

目錄

歸併排序的思想

歸併排序的 Go 程式碼實現

歸併排序的時間複雜度

熱門文章