algorithm - 如何对特定类型的输入进行排序

Question

我有一系列元素，比如 a1,a2,...,an。(n ~ 4*10^7)

输入将主要进行排序。更具体地说，任何小于 a_i 的元素都将位于左侧或非常靠近右侧（约 300 个元素）。

我怎样才能有效地排序这个序列？

Answer 1

您可以使用一堆 N 元素来执行此操作，其中 N 是最大重叠（在您的情况下为 N=300）。

从空堆开始。

对于序列中的每个元素：

1. 向堆中添加元素

2. 如果堆有超过 N 个元素，则输出（并从堆中删除）最小的元素

最后输出堆中剩余的元素。

这将具有复杂性 O(nlogN)