text: 在計算機科學裡，偏排序是排序演算法的一個放寬的變種。全排序返回的列表中，每個元素都按一定順序出現，而偏排序返回的列表中，僅有 "k" 個最小(或 "k" 個最大)的元素是有序的。其他元素(第 "k" 個最小之外) 也可能被就地排序後儲存，也可能被捨棄。這常見於流式偏排序中。偏排序最普遍的例項是計算某個列表的 "Top 100"。就索引而言，偏排序後的列表中，對每一個從 1 到 "k" 的索引 "i" ，都有第 "i" 個元素與全排列後列表保持相同位置：偏排序後列表的第 "i" 個元素包含了輸入列表中的第 "i" 個順序統計量。離線問題.基於堆的解決方案.當 "O"(n+klog "n")。劃分選擇的解決方案.進一步的放寬要求，只需要 "O"("n" + "k" log "k")。該演算法方案的一個流行實現是結合快速選擇與快速排序，該結果常稱為 "quickselsort".專門的排序演算法.比上述更高效的，是基於歸併排序與快速排序的專門偏排序演算法。在快速排序的變體裡，不需要對只包含最終排序後陣列(從左邊界開始)的第 k 之後, 我們的遞迴僅限於左邊的劃分(partition):function partial_quicksort(A, i, j, k)if i &lt; jp ← pivot(A, i, j)p ← partition(A, i, j, p)partial_quicksort(A, i, p-1, k)if p &lt; k-1partial_quicksort(A, p+1, j, k)所得演算法稱之為偏快速排序，且只需要耗時 n 很小時的情況。然而，最壞的時間複雜度依然很糟糕, 例如在選取了一個不好的支點(pivot)時。支點(pivot)的選擇沿著最壞線性時間線通常可以讓選擇演算法的最壞情況稍好一些。增量排序.增量排序是偏排序問題的一個線上演算法版本。其中輸入被丟棄在前面，而 ("k"+1)-sorted.堆引出一個針對線上偏排序，複雜度為 k 次該堆的最小值。一個更快的漸近增量排序可透過修改快速選擇獲得。由於 Paredes 和 Navarro 版本透過呼叫時維護了一個支點堆，故用增量排序求解陣列 A 的最小元素可透過以下演算法重複地完成：Algorithm Atop("S"):堆疊 "i"0, 1, 2, ... 中呼叫 "O"("n" + "k" log "k")。最壞情況下是二次方, 但這可以用中值演算法的中位數替換隨機支點來解決。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 偏排序
metadata: https://zh.wikipedia.org/wiki?curid=5985429