快速選擇

計算機科學中,快速選擇(英語:Quickselect)是一種從無序列表找到第k小元素的選擇算法。它從原理上來說與快速排序有關。與快速排序一樣都由托尼·霍爾提出的,因而也被稱為霍爾選擇算法[1] 同樣地,它在實際應用是一種高效的算法,具有很好的平均時間複雜度,然而最壞時間複雜度則不理想。快速選擇及其變種是實際應用中最常使用的高效選擇算法。

快速選擇
快速選擇算法的動畫演示:選擇第22小的元素。
快速選擇算法的動畫演示:選擇第22小的元素。(注意:這和條目中的算法不完全相同)
概況
類別選擇算法
資料結構數組
複雜度
平均時間複雜度O(n)
最壞時間複雜度О(n2)
最優時間複雜度О(n)
空間複雜度O(1)
相關變量的定義

快速選擇的總體思路與快速排序一致,選擇一個元素作為基準來對元素進行分區,將小於和大於基準的元素分在基準左邊和右邊的兩個區域。不同的是,快速選擇並不遞歸訪問雙邊,而是只遞歸進入一邊的元素中繼續尋找。這降低了平均時間複雜度,從O(n log n)至O(n),不過最壞情況仍然是O(n2)。

與快速排序一樣,快速選擇一般是以原地算法的方式實現,除了選出第k小的元素,數據也得到了部分地排序。

算法

快速排序中,有一個子過程稱為分區,可以在線性時間裡將一個列表分為兩部分(leftright),分別是小於基準和大於等於基準的元素。下面是以list[pivotIndex]進行分區的偽代碼:

 function partition(list, left, right, pivotIndex)
     pivotValue := list[pivotIndex]
     swap list[pivotIndex] and list[right]  // Move pivot to end
     storeIndex := left
     for i from left to right-1
         if list[i] < pivotValue
             swap list[storeIndex] and list[i]
             increment storeIndex
     swap list[right] and list[storeIndex]  // Move pivot to its final place
     return storeIndex

在快速排序中,我們遞歸地對兩個分支進行排序,導致最佳時間複雜度為O(n log n)。然而,在快速選擇中,雖然大部分元素仍是亂序的,但是基準元素已經在最終排序好的位置上,所以我們知道想找的元素在哪個分區中。 因此,一個遞歸循環分支就能幫助我們定位想找的元素,從而得到快速選擇的算法:

  // Returns the k-th smallest element of list within left..right inclusive
  // (i.e. left <= k <= right).
  // The search space within the array is changing for each round - but the list
  // is still the same size. Thus, k does not need to be updated with each round.
  function select(list, left, right, k)
     if left = right        // If the list contains only one element,
         return list[left]  // return that element
     pivotIndex  := ...     // select a pivotIndex between left and right,
                            // e.g., left + floor(rand() % (right - left + 1))
     pivotIndex  := partition(list, left, right, pivotIndex)
     // The pivot is in its final sorted position
     if k = pivotIndex
         return list[k]
     else if k < pivotIndex
         return select(list, left, pivotIndex - 1, k)
     else
         return select(list, pivotIndex + 1, right, k)

注意到與快速排序的相似之處:就像基於尋找最小值的選擇算法是部分選擇排序,這可以認為是部分快速排序,只進行O(n log n)而不是O(n)次分區。這個簡單的過程具有預期的線性時間複雜度,並且如快速排序一樣有相當良好的實際表現。 這也是一個原地算法,只需要棧內常數級的內存,或者可以用循環來去掉尾遞歸

 function select(list, left, right, k)
     loop
         if left = right
             return list[left]
         pivotIndex := ...     // select pivotIndex between left and right
         pivotIndex := partition(list, left, right, pivotIndex)
         if k = pivotIndex
             return list[k]
         else if k < pivotIndex
             right := pivotIndex - 1
         else
             left := pivotIndex + 1

時間複雜度

與快速排序類似,快速選擇算法在平均狀況下有著不錯的表現,但是對於基準值的選擇十分敏感。如果基準值選擇上佳,搜索範圍每次能夠指數級減少,這樣一來所耗時間是線性的(即O(n))。但如果基準值選擇非常不好,使得每次只能將搜索範圍減少一個元素,則最糟的總體時間複雜度是平方級的(O(n2)):例如對一個升序排列的數組搜索其最大值,而每次都選擇第一個元素作為基準值。

算法變體

最簡單的快速排序變化是每次隨機選擇基準值,這樣可以達到近乎線性的複雜度。更為確定的做法是採用「取三者中位數」[2]的基準值選擇策略,這樣對已部分排序的數據依然能夠達到線性複雜度。但是,特定人為設置的數組在此方法下仍然會導致最差時間複雜度,如大衛·穆塞爾英語David Musser所描述的「取三者中位數殺手」數列,這成為他發表反省式選擇英語introselect算法的動機。

利用中位數的中位數英語Median of medians算法,可以在最壞情形下依然保證線性時間複雜度。但是這一方法中的基準值計算十分複雜,實際應用中並不常見。改進方法是在快速選擇算法的基礎上,使用「中位數的中位數」算法處理極端特例,這樣可以保證平均狀態與最差情形下的時間複雜度都是線性的,這也是反省式選擇英語introselect算法的做法。

精確計算下,隨機選擇基準值策略最差會導致 複雜度。採用Floyd–Rivest算法英語Floyd–Rivest algorithm可以使這一常數進一步減少,在最壞情形下達到  

參考文獻

  1. ^ Hoare, C. A. R. Algorithm 65: Find. Comm. ACM. 1961, 4 (7): 321–322. doi:10.1145/366622.366647. 
  2. ^ 存档副本. [2017-03-07]. (原始內容存檔於2021-01-24).