排序演算法 - 快速排序 (written in Go)

April 13, 2017

排序演算法 - 快速排序

最近突然看到一些排序相關的演算法,以前自己根本沒有好好的學過,趁機學習並筆記一下。

快速排序最主要是使用分治法(Divide and conquer)來將一個 Array 分割成 sub-array,再從 sub-array 不斷的重複做這些事。 首先我們會從一個 array 選出一個基準點,以這個基準點,把序列分為以基準點為中心,比基準點大和比基準點小

假如今天我有一個陣列:

Array = [1, 7, 7, 9, 1, 8, 5, 0, 6, 0]

根據上面所述,我要先找一個基準點,這裡假設我以第五個元素作為一個基準點,也就是 1

1 為中心來做分組這件事,比 1 小在右邊,比 1 大在左邊,我用另外兩個陣列來表示,middlePart 代表和基準點一樣大:

以下是根據下方由 Go 實作的 quick-sorting 所推導,實現的方式很多,重點是在於掌握 quick-sorting 的概念。

// 第一次分組

lowPart = [0, 0]
hightPart = [7, 7, 9, 8, 5, 6]
middlePart = [1, 1] // `middlePart` 表示和基準點的數字一樣大。

這是我們第一次對這個陣列進行分類,依照這個邏輯不斷的重複下去,直到每個元素都被比較過。

我們把上面第一次分類的 lowPart 以及 hightPart 再做相同的事:

// 從第一次分組的結果再做第二次分組

lowPart[0, 0] // 以 lowPart[1] 為基準點:
=> middlePart = [0, 0], lowPart = [], hightPart = []

hightPart[7, 7, 9, 8, 5, 6] // 以 lowPart[1] 為基準點:
=> middlePart = [7, 7], lowPart = [5, 6], hightPart = [9, 8]

看到第一次分組出來的 lowParthightPart 中又可以再分成 sub-lowPartsub-hightPart,再繼續比下去:

lowPart[5, 6] // 以 `6` 為基準點:
=> middlePart = [6], lowPart = [5], hightPart = []

hightPart[9, 8] // 以 `8` 為基準點:
=> middlePart = [8], lowPart = [], hightPart = [9]

到這邊我們已經透過這樣的方式比較到每個元素。

接下來根據分組的順序將 lowPartmiddlehightPart append 回來:

// 這裡把 append 用 `+` 來表示

lowPart[5] + middlePart[6] + hightPart[] => [5, 6]
lowPart[] + middlePart[8] + hightPart[9] => [8, 9]

lowPart[5, 6] + middlePart[7, 7] => [5, 6, 7, 7]
lowPart[5, 6, 7, 7] + hightPart[8, 9] => [5, 6, 7, 7, 8, 9]

lowPart[0, 0] + middlePart[1, 1] => [0, 0, 1, 1]
lowPart[0, 0, 1, 1] + hightPart[5, 6, 7, 7, 8, 9]

=> [0, 0, 1, 1, 5, 6, 7, 7, 8, 9]

上面的表示是透過遞歸的方式來做比較,當遞歸到最後時,就會開始收斂回去,並得到最後的結果。

用 Go 實作的 quick sorting:

// https://github.com/0xAX/go-algorithms/blob/master/sorting/quick_sort.go

func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    median := arr[rand.Intn(len(arr))] // 取得中位數
    lowPart := make([]int, 0, len(arr)) // 建立一個 lowPart 的 slice
    hightPart := make([]int, 0, len(arr)) // 建立一個 hightPart 的 slice
    middlePart := make([]int, 0, len(arr)) // 建立一個 middlePart 的 slice

        // 開始比較陣列內的元素,並分到相應的 slice 內
    for _, item := range arr {
        switch {
        case item < median:
            lowPart = append(lowPart, item)
        case item == median:
            middlePart = append(middlePart, item)
        case item > median:
            hightPart = append(hightPart, item)
        }
    }

    lowPart = quickSort(lowPart) // 對 lowPart 的部分再繼續做比較(遞歸)
    hightPart = quickSort(hightPart) // 對 hightPart 的部分再繼續做比較(遞歸)

    lowPart = append(lowPart, middlePart...) // 將 middlePart append 到 lowPart 上
    lowPart = append(lowPart, hightPart...) // 上面 append 完後,最後 append hightPart

    return lowPart
}

筆記心得

其實透過自己手寫的方式列出 quick-sorting 的結果感覺好像沒這麼難,但是透過程式實作時,使用遞歸(recursion)就會發現很抽象, 主要是因為 recursion 很多次時,腦袋就會卡住了,不知道到底執行到哪裡,這裡我想用收斂這個詞來表達,如果有不正確在煩請指正。

當我們第一次分組時得到的結果:

lowPart = [0, 0]
middlePart = [1, 1]
hightPart = [7, 7, 9, 8, 5, 6]

根據上面的程式碼來看,這麼做是有它的順序性存在的,也就是 lowPart 會再做一次 quickSorthightPart 也會,這裡開始便進入了 recursion

所以思考的方式就很像是:

和翻開玫瑰花一樣,一層一層的往內撥開,當然你不能把它撕爛,它還可以由內而外把它合起來合起來(XD)

所以第一次 lowPart[0, 0] 出來的結果會是:

middlePart = [0, 0], lowPart = [], hightPart = []

再來是第一次的 hightPart = [7, 7, 9, 8, 5, 6],這裡可以看到元素很多,必定會做了很多次的 recursion 來做計算。

根據上面的描述,這裡就很像是把一個陣列給發散出去,變成一個一個的元素,再根據這些發散出去的順序在反過來收斂回來。

1, 2, 3, 4, 5, 6, 7, 8, 9
=========================> 發散

// 上面做到最後結束後:

1, 2, 3, 4, 5, 6, 7, 8, 9
<========================= 收斂

所以看到上面的描述可以再把 [7, 7, 9, 8, 5, 6] 再細分成 sub-array:

hightPart[7, 7, 9, 8, 5, 6] // 以 lowPart[1] 為基準點:
=> middlePart = [7, 7], lowPart = [5, 6], hightPart = [9, 8]

// 再細分
=> middlePart = [6], lowPart = [5], hightPart = [] // 比較完畢
=> middlePart = [8], lowPart = [], hightPart = [9] // 比較完畢

我們根據程式碼的順序性:

lowPart = quickSort(lowPart)
hightPart = quickSort(hightPart)

lowPart = append(lowPart, middlePart...)
lowPart = append(lowPart, hightPart...)

return lowPart

所以就會從最後面比較完結束的地方,開始收斂回來:

// `next` 代表收斂回來的結果
nextLowPart = lowPart[5] + middlePart[6] + hightPart[]
nextHightPart' = lowPart[] + middlePart[8] + hightPart[9]

lowPart = nextLowPart + middlePart[7, 7] + nextHightPart

// return lowPart = [5, 6, 7, 7, 8, 9]

最後還有:

// 外層的 lowPart
lowPart = lowPart[0, 0] + middlePart[1, 1] + hightPart[]

// 收斂回來的 hightPart
hightPart = [5, 6, 7, 7, 8, 9]

lowPart + hightPart = [0, 0, 1, 1, 5, 6, 7, 7, 8, 9]

其實重點就是要掌握到遞歸的概念,還有程式碼是如何執行的,就可以明白他執行的順序了!