偏排序 | 张拓的博客

在计算机科学里，偏排序是排序算法的一个放宽的变种。全排序返回的列表中，每个元素都按一定顺序出现，而偏排序返回的列表中，仅有 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)。最坏情况下是二次方, 但这可以用中值算法的中位数替换随机支点来解决。