圖解演算法基礎--快速排序,附 Go 程式碼實現

語言: CN / TW / HK

很多面試題的解答都是以排序為基礎的,如果我們寫出一個 O() 的演算法,大概率要被掛,今天寫個快排的基礎文章,後面看情況再把歸併和堆排序寫一寫,至於選擇排序、氣泡排序這種時間複雜度高的就不寫了,有興趣的可以找書自己看一下。

文中演算法的實現是用 Go 寫了一個比較簡單的快速排序,方便大家理解(旁邊畫外音:其實是他好幾年沒面試了,太厲害的他也寫不出來)。

關於更優秀的程式碼實現,可以在評論區裡發出來一起學習,相信咱們讀者裡一定是臥虎藏龍,有不少演算法大拿。

快速排序的思想

快速排序演算法首先會在序列中隨機選擇一個基準值(pivot),然後將除了基準值之外的數分為 "比基準值小的數" 和 "比基準值大的數" 這兩個類別,再將其排列成以下形式。

【比基準值小的數】 基準值 【比基準值大的數】

接著,繼續對兩個序列 "【】"中的資料進行排序之後,整體的排序便完成了。對基準值左右兩側的序列排序時,同樣也會使用快速排序。

快速排序是一種"分治法",將原本的問題分解成兩個子問題—— 比基準值小的數和比基準值大的數,然後再分別解決這兩個子問題。解決子問題的時候會再次使用快速排序,只有在子問題裡只剩下一個數字的時候,排序才算完成。

快排的過程

下面我們用示意圖更好地理解一下快速排序對一個序列進行排序的過程。

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

假定有如下待排序序列

待排序序列

首先在序列中隨機選擇一個基準值,這裡選擇了 4。

選擇基準值 pivot

將其他數字和基準值進行比較,小於基準值的往左移,大於基準值的往右移。

首先比較第一個元素 3 和基準值4,因為 3 < 4, 所以將 3放在基準值的左邊。

首先比較 3 和基準值4,因為 3 < 4, 所以將 3放在基準值的左邊

接下來,比較 5 和基準值,因為 5 > 4,所以將 5 放在基準值的右邊。

5 > 4, 將5放在基準值右邊

對整個序列進行同樣操作後,所有小於基準值的數字全都放到了基準值的左邊,大於的則全都放在了右邊。

一輪排序完成後的結果
把基準值放入序列

現在排序就分成了兩個子問題,分別再對基準值左邊和右邊的資料進行排序。

分解成了兩個子問題

兩邊的排序操作也和前面的一樣,也是使用快排演算法,選取基準值,把小於的數字放左邊大於的放右邊。

對子序列使用快速排序

子問題有可能會再分解成子問題,直到子問題裡只剩下一個數字,再也無法分解出子問題的時候,整個序列的排序才算完成。

排序完成

因為快速排序演算法在對序列進行排序的過程中會再次使用該演算法,所以快速排序演算法在實現時需要使用"遞迴”來實現。

快速排序的Go程式碼實現

下面上一個用 Go 版本的快速排序演算法的簡單實現


func quickSort(sequence []int, low int, high int) {
if high <= low {
return
}
j := partition(sequence, low, high)
quickSort(sequence, low, j-1)
quickSort(sequence, j+1, high)
}

// 進行快速排序中的一輪排序
func partition(sequence []int, low int, high int) int {
i, j := low+1, high
for {
// 把頭元素作為基準值 pivot
for sequence[i] < sequence[low] {
// i 座標從前往後訪問序列,如果位置上的值大於基準值,停下來。
// 準備和 j 座標訪問到的小於基準值的值交換位置
i++
if i >= high {
break
}
}
for sequence[j] > sequence[low] {
// j 座標從後往前訪問序列,如果位置上的值小於基準值,停下來。
// 和 i 座標指向的大於基準值的值交換位置
j--
if j <= low {
break
}
}
if i >= j {
break
}
sequence[i], sequence[j] = sequence[j], sequence[i]
}
sequence[low], sequence[j] = sequence[j], sequence[low]

return j
}

每一輪快速排序都會經歷下面這幾個步驟:

  1. 設定兩個變數i、j,排序開始的時候:i=0,j=待排序序列長度 - 1。

  2. 以第一個陣列元素作為基準值 pivot(也可以是最後一個元素,或者是隨機的一個元素)。

  3. i 座標從開始向後訪問序列裡的元素,即 i++,找到第一個大於 pivot 的位置 ,和 j 座標訪問到的小於基準值的值交換位置。

  4. j 座標從末尾向前搜尋,即j--,找到第一個小於 pivot 的位置,將i,j座標上的值進行互換。

  5. 重複第3、4步,直到i=j,然後將 pivot 和 j 座標上的值互換,完成一輪排序,小於 pivot 的值都放在了它的左邊,大於的則放到了右邊。

重複進行上面的過程,直到排序完成。最後我們可以生成一個隨機數序列 對上面的快速排序函式進行測試:

func main() {
 rand.Seed(time.Now().Unix())
 sequence := rand.Perm(34)
 fmt.Printf("sequence before sort: %v", sequence)
 quickSort(sequence, 0, len(sequence) - 1)
 fmt.Printf("sequence after sort: %v", sequence)
}

快速排序的時間複雜度

分割子序列時需要選擇基準值,如果每次選擇的基準值都能使得兩個子序列的長度為原本的一半,那麼快速排序的執行時間和歸併排序的一樣,都為 O ( n log n )。將序列對半分割 log2 n 次之後,子序列裡便只剩下一個數據,這時子序列的排序也就完成了。

因此,如果像下圖這樣一行行地展現根據基準值分割序列的過程,那麼總共會有 log2 n 行。

快排分解序列的次數

每行中每個數字都需要和基準值比較大小,因此每行所需的執行時間為 O ( n )。由此可知,整體的時間複雜度為  O ( n log n )。

如果運氣不好,每次都選擇最小值作為基準值,那麼每次都需要把其他資料移到基準值的右邊,遞迴執行 n 行,執行時間也就成了 O()。

所以真正應用的時候基準值的選取也比較講究,比如以中位數做基準值:本輪排序序列的第一個、最後一個、中間位置三個數的中位數作為基準值進行排序。

今天的內容分享到這裡就結束了,喜歡的話還請點贊、在看多多支援,關注不迷路。

文章的圖片來自書籍《我的第一本演算法書》,想要 PDF 的可以後臺私信我,覺得內容不錯了建議下單買一本,支援原作者的創作。

下期再見吧。

- END -

掃碼關注公眾號「網管叨bi叨」

給網管個星標,第一時間吸我的知識 :point_up_2:

網管為大家整理了一本超實用的《Go 開發參考書》收集了70多條開發實踐。去公眾號回覆【gocookbook】即刻領取!

覺得有用就點個在看   :point_down::point_down::point_down: