排序与选择一个几乎排序后的数组

给定长度Ñ的阵列，其中每个项目具有从它的最终位置的排序后的数组中至多的log（n）的距离，如何有效地完成我排序，并我如何找到价值物品（select-k）的第k个？排序与选择一个几乎排序后的数组

这是我开始的想法：

对于排序，使用比较模式，我可以得到有将约为O（（LOGN）^ n）的可能的排列，因此的最大深度比较树应该是O（nloglogn）。另外，对于选择的问题，我有一种直觉，如果我看LOGN的范围为k个项的每一侧（2logn - 1），我可以在使用确定性选择算法O（logn），但我不确定如何证明此方法的正确性。

请注意，我是而不是正在寻找代码（使用任何语言），但抽象算法的草图和时间复杂度。

谢谢。

来源

2017-07-28 Mickey

如果你不看对于代码，最好转到https://cs.stackexchange.com/。 – hgazibara

使用minHeap长度

x=log(n)

开始从开始的，推动要素堆和X插入后相应，你会发现最小的元素，并继续等扫描其他元素。

复杂性 -

O(n(log(x))) = x*log(x)(for heap operations for first x elements) + (n-x)(log (x))(for remaining elements) 
x=log(n);

你可以用自己的方式来识别通过跟踪有多少个元素已经排序排序第k个值......

来源

2017-07-28 08:42:06

与minHeap的好主意。对于第k个值 - 我想要得到更好的复杂度，因此它应该是一个不同的算法（与排序分离），你有什么想法吗？ – Mickey

好吧，你只需要找到第k个最小的元素，然后？ –

是的，（和排序，但你已经回答:) :) – Mickey

排序与选择一个几乎排序后的数组

回答

相关问题