在计算机科学里，偏排序是排序算法的一个放宽的变种。全排序返回的列表中，每个元素都按一定顺序出现，而偏排序返回的列表中，仅有 k 个最小(或 k 个最大)的元素是有序的。其他元素(第 k 个最小之外) 也可能被就地排序后存储，也可能被舍弃。这常见于流式偏排序中。偏排序最普遍的实例是计算某个列表的 "Top 100"。
就索引而言，偏排序后的列表中，对每一个从 1 到 k 的索引 i ，都有第 i 个元素与全排列后列表保持相同位置：偏排序后列表的第 i 个元素包含了输入列表中的第 i 个顺序统计量。
离线问题
基于堆的解决方案
当 固定时，堆允许一个简单的单次偏排序：向一个最大堆中插入输入中的前 个元素，然后遍历剩余的元素，依次加到堆中，并删除最大的那个。每个插入操作耗时 ，总耗时达 。该算法适合求解第 小的值与配置在线算法.
function partial_quicksort(A, i, j, k)
if i [http://en.cppreference.com/w/cpp/algorithm/partial_sort std::partial_sort]。
- Python 标准库的heapq 模块里有 [https://docs.python.org/library/heapq.html#heapq.nlargest nlargest] and [https://docs.python.org/library/heapq.html#heapq.nsmallest nsmallest] 方法。
参阅
- 选择排序
参考文献
外部链接
- J.M. Chambers (1971). [http://dl.acm.org/citation.cfm?id=362602 Partial sorting] . CACM 14(5):357–358.
评论 (0)