偏排序
偏排序
条目
历史版本
在计算机科学里，偏排序是排序算法的一个放宽的变种。全排序返回的列表中，每个元素都按一定顺序出现，而偏排序返回的列表中，仅有 k 个最小(或 k 个最大)的元素是有序的。其他元素(第 k 个最小之外) 也可能被就地排序后存储，也可能被舍弃。这常见于流式偏排序中。偏排序最普遍的实例是计算某个列表的 "Top 100"。就索引而言，偏排序后的列表中，对每一个从 1 到 k 的索引 i ，都有第 i 个元素与全排列后列表保持相同位置：偏排序后列表的第 i 个元素包含了输入列表中的第 i 个顺序统计量。
离线问题
基于堆的解决方案
当k固定时， 堆允许一个简单的单次偏排序：向一个最大堆中插入输入中的前k个元素，然后遍历剩余的元素，依次加到堆中，并删除最大的那个。每个插入操作耗时
，总耗时达
。该算法适合求解第k小的值与配置在线算法。另一个选择是为所有值构建一个最小堆(构建过程耗费
)并将堆头移除，重复K次，每次移除操作耗费
.在该情况下，总的算法复杂度为
。
划分选择的解决方案