[科普中国]-偏排序

在计算机科学里，偏排序是排序算法的一个放宽的变种。全排序返回的列表中，每个元素都按一定顺序出现，而偏排序返回的列表中，仅有 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