iT邦幫忙

2021 iThome 鐵人賽

DAY 10
0
自我挑戰組

30天不怕演算法:白話文版系列 第 10

Day 10:快速排序(quicksort)

看完了分治法與遞迴,再來看這樣的方法如何解決排序問題。

快速排序是一種利用分治法的演算法,比前面提到的排序方法都要快速許多,有些程式語言的函式庫也直接包含了快速排序的函式,可以直接在實務中運用。

快速排序的步驟是:

  1. 在一個數列中挑選出一個數字當作基準(pivot)。
  2. 將所有比基準小的元素放前面,所有比基準大的元素放後面。
  3. 用遞迴的方式,對基準兩邊的數列進行快速排序。

以實際例子來說,如果有一個數列 24, 32, 5, 45, 15, 7,第一步我們隨意挑選第一個數字24作為基準。

接下來第二個步驟叫做分割(partitioning),將比24小的數字放前面,比24大的放後面:

5, 15, 7, 24, 32, 45

經過分割,我們會得到:比基準小的子數列(5, 15, 7)、基準(24)、比基準大的子數列(32, 45)。

接著遞迴地對子數列進行上述步驟。那麼既然是遞迴,這裡的基本情況是什麼?什麼時候問題會小到排序可以直接完成、不必再分割下去?答案就是當子數列只有0個或1個數字,可以直接當作排序完成。

所以我們將上述例子的子數列(5, 15, 7)、(32, 45)再進行挑選基準和分割,此時得到的子數列長度都<=1,遞迴結束,最後所有的數列合併可以得到排序好的數列:5, 7, 15, 24, 32, 45。

這樣的演算法以虛擬碼可以表示為:

source:維基百科
function quicksort(q)
 {
     var list less, pivotList, greater
     if length(q) ≤ 1 
         return q
     else 
     {
         select a pivot value pivot from q
         for each x in q except the pivot element
         {
             if x < pivot then add x to less
             if x ≥ pivot then add x to greater
         }
         add pivot to pivotList
         return concatenate(quicksort(less), pivotList, quicksort(greater))
     }
 }

執行時間

快速排序跟其他演算法比較不一樣的地方在於,它的執行時間跟如何挑選基準有很大的關係。

我們可以先想像,無論怎麼挑選基準,每一層遞迴都會處理陣列裡的所有元素,所以每次增加執行堆疊都會經過n次操作,這部份時間為O(n)。換句話說,執行堆疊越少,則整體執行時間越短。

基於上述所說,最壞的情況就是執行堆疊最高的情況。如果每次的基準都是陣列中最大或最小的數字,分割時就會所有元素都被分在同一邊,等於每次的子陣列只比原本少一個元素,那麼需要n-1層的遞迴才能完成排序。再乘以每層的操作時間,整個演算法的最壞情況執行時間為O(n²)。

最佳的情況,則是每次的基準都將陣列分割成兩個差不多大小的子陣列,這樣就只需要log n層遞迴。整體執行時間可以縮短為O(n log n)。

以陣列[1, 2, 3, 4, 5, 6, 7, 8]為例,如果以第一個數字作為基準,分割後會得到空陣列[]、[1]、[2, 3, 4, 5, 6, 7],以此類推,要經過7層遞迴才能達到基本情況。但如果以4為基準,只要3層次的遞迴就可以達到基本情況。

不過快速排序的一大優勢在於,它的最佳情況執行時間也就是平均情況執行時間,也就是說一般情況下,若隨機選擇一個元素作為基準,快速排序的平均執行時間即可以達到O(n log n)。


上一篇
Day 09:遞迴(2)
下一篇
Day 11:合併排序(mergesort)
系列文
30天不怕演算法:白話文版30

尚未有邦友留言

立即登入留言