排序算法与约束阵列

Question

我想要一个算法，排序和O（nlog（logn））时间A阵列。 其中对于所有j> = log（n），A [0 ... n-1]具有性质A [i]> = A [i-j]。

到目前为止，我曾想过将分区A分成每个logn大小的块。

那么我认为第一个块会比它之后的块要小得多？

我想我错过了它的一部分。

Answer 1

Tree Sort将是一个选项。您从数组的左端开始并将元素传入树中。无论何时你的树有多于log（n）个元素，你都会把最小的元素拿出来，因为你确定知道所有后续元素都较大，并将其放回到排序后的数组中。这样树的大小总是log（n），而树操作的开销是log（log（n））。事实上，你只需要操作（1）插入随机元素和（2）删除最小的元素，所以你不一定需要一棵树，但任何种类的priority queue都可以做到这一点。这样，平均和最差情况下的性能都能满足您的要求。