偏排序

在計算機科學里，偏排序是排序算法的一個放寬的變種。全排序返回的列表中，每個元素都按一定順序出現，而偏排序返回的列表中，僅有 k 個最小(或 k 個最大)的元素是有序的。其他元素(第 k 個最小之外) 也可能被就地排序後存儲，也可能被捨棄。這常見於流式偏排序中。偏排序最普遍的實例是計算某個列表的 "Top 100"。

就索引而言，偏排序後的列表中，對每一個從 1 到 k 的索引 i ，都有第 i 個元素與全排列後列表保持相同位置：偏排序後列表的第 i 個元素包含了輸入列表中的第 i 個順序統計量。

離線問題

基於堆的解決方案

當 k 固定時，堆允許一個簡單的單次偏排序：向一個最大堆中插入輸入中的前 k 個元素，然後遍歷剩餘的元素，依次加到堆中，並刪除最大的那個。每個插入操作耗時 O(log k) ，總耗時達 O(n log k)。該算法適合求解第 k 小的值與配置在線算法. 另一個選擇是為所有值構建一個最小堆(構建過程耗費 O(n)) 並將堆頭移除，重複 K 次, 每次移除操作耗費 O(log n). 在該情況下，總的算法複雜度為 O(n+klog n)。

劃分選擇的解決方案

進一步的放寬要求，只需要 k 個最小元素的列表，但不保證它們有序。這使得問題簡化為基於分區的選擇; 原本的偏排序問題可以通過基於選擇算法來解決，這將得到一個包含前 k 個最小元素並保證它們有序的數組，總體耗費 O(n + k log k)。該算法方案的一個流行實現是結合快速選擇與快速排序，該結果常稱為 "quickselsort".

專門的排序算法

比上述更高效的，是基於歸併排序與快速排序的專門偏排序算法。在快速排序的變體裡，不需要對只包含最終排序後數組(從左邊界開始)的第 k 個位置之後元素的劃分(partition)，進行遞歸的排序。因此，如果支點(pivot)在 k 之後, 我們的遞歸僅限於左邊的劃分(partition):

 function partial_quicksort(A, i, j, k)
     if i < j
         p ← pivot(A, i, j)
         p ← partition(A, i, j, p)
         partial_quicksort(A, i, p-1, k)
         if p < k-1
             partial_quicksort(A, p+1, j, k)

所得算法稱之為偏快速排序，且只需要耗時 O(n + k log k)，這在實踐中相當高效，尤其當一個選擇排序被用於 k 相對於 n 很小時的情況。然而，最壞的時間複雜度依然很糟糕, 例如在選取了一個不好的支點(pivot)時。支點(pivot)的選擇沿著最壞線性時間線通常可以讓選擇算法的最壞情況稍好一些。

增量排序

增量排序是偏排序問題的一個在線算法版本。其中輸入被丟棄在前面，而 k 是未知的：給定一個 k-sorted 的數組，它應該可以擴展為偏排序部分，使之稱為 (k+1)-sorted.

堆引出一個針對在線偏排序，複雜度為 O(n + k log n) 的解決方案：先以線性時間「堆積」全部輸入數組，以產生一個最小堆。然後依次提取 k 次該堆的最小值。

一個更快的漸近增量排序可通過修改快速選擇獲得。由於 Paredes 和 Navarro 版本通過調用時維護了一個支點堆，故用增量排序求解數組 A 的最小元素可通過以下算法重複地完成：

Algorithm IQS(A : array, i : integer, S : stack) returns the i'th smallest element in A

• If i = top(S):
  • Pop S
  • Return A[i]
• Let pivot ← random [i, top(S))
• Update pivot ← partition(A[i : top(S)), A[pivot])
• Push pivot onto S
• Return IQS(A, i, S)

堆疊 S 被初始化為長度為 n 的 A。循環 i = 0, 1, 2, ... 中調用 IQS(A, i, S) 可完成對數組的 k-sorting。這一系列調用的平均複雜度為 O(n + k log k)。最壞情況下是二次方, 但這可以用中值算法的中位數替換隨機支點來解決。

程式語言/庫的支持

• C++ 標準庫有 std::partial_sort。
• Python 標準庫的heapq 模塊里有 nlargest and nsmallest 方法。

參閱

• 選擇排序

外部連結

• J.M. Chambers (1971). Partial sorting （頁面存檔備份，存於網際網路檔案館）. CACM 14(5):357–358.