给定一个长度为 n 的数组，其中每个项目与其在排序数组中的最终位置的距离最多为 log(n)，我如何有效地排序它，以及如何找到 k-th 值项 (select-k)？
这是我的初步想法:
对于排序，使用比较模型我可以得到大约 O((logn)^n) 可能的排列，因此比较树的最大深度应该是 O(nloglogn)。此外，对于选择问题，我有一个直觉，如果我查看 k-th 项的每一侧的 logn 范围(2logn - 1 )，我可以在 O(logn) 中使用确定性选择算法，但是我不确定如何证明这种方法的正确性。
请注意，我不是在寻找代码(使用任何语言)，而是寻找抽象算法的草图及其时间复杂度。
谢谢。
最佳答案
使用长度为 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 个值......
关于arrays - 排序和选择几乎排序的数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45367681/