排序演算法 - 快速排序

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

快速排序最主要是使用分治法（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]

看到第一次分組出來的 lowPart 和 hightPart 中又可以再分成 sub-lowPart 和 sub-hightPart，再繼續比下去：

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

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

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

接下來根據分組的順序將 lowPart、middle、hightPart 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 會再做一次 quickSort，hightPart 也會，這裡開始便進入了 recursion。

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

和翻開玫瑰花一樣，一層一層的往內撥開，當然你不能把它撕爛，它還可以由內而外把它合起來合起來（ＸＤ）

所以第一次 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]

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