sorting一个几乎sorting的数组（元素错位不超过k）

最近我被问到这个面试问题：

你得到一个几乎sorting好的数组，因为N元素中的每一个都可能被正确的sorting顺序放错位置不超过k位置。 查找空间和时间高效的algorithm来对数组进行sorting。

我有一个O(N log k)解决scheme如下。

让我们用arr[0..n)表示从索引0 （含）到N （独占）的数组元素。

• sortingarr[0..2k)
  • 现在我们知道arr[0..k)处于最后的sorting位置了…
  • …但是arr[k..2k)仍然可能被k放错位置！
• sortingarr[k..3k)
  • 现在我们知道arr[k..2k)处于最后的sorting位置了…
  • …但是arr[2k..3k)仍然可能被k放错了位置
• sortingarr[2k..4k)
• ….
• 直到你sortingarr[ik..N) ，那么你就完成了！
  • 当您剩余的元素less于2k时，最后一步可能比其他步骤便宜

在每个步骤中，您最多可以sortingO(k log k) 2k元素，每个步骤结束时至less将k元素放在最终的sorting位置。 有O(N/k)步，所以总的复杂度是O(N log k) 。

我的问题是：

• O(N log k)最优的吗？ 这可以改善吗？
• 你能不能（部分）重新sorting相同的元素？

Answer 1

正如Bob Sedgewick在他的论文工作（和后续）中所展示的那样，插入sorting绝对会压倒 “接近sorting的数组”。 在这种情况下，你的渐进式看起来不错，但是如果k <12，我敢打赌插入sorting每一次都赢。 我不知道为什么插入sorting做的很好，但是有一个很好的解释，那就是在Sedgewick的教科书“ algorithm （他为不同的语言做了很多版本）”之后。

• 我不知道O（N log k）是否是最优的，但更重要的是，我并不在意 – 如果k很小，那么这个常数是重要的，如果k很大，那么也可以sorting数组。

• 插入sorting将钉住这个问题，而不重新sorting相同的元素。

大O符号对于algorithm类来说是非常好的，但是在现实世界中，常量很重要。 忽略这一点太容易了。 （我说这是教授Big-O符号的教授！）

Answer 2

如果仅使用比较模型，则O（n log k）是最优的。 考虑k = n时的情况。

要回答你的其他问题，是的，可以做到这一点，没有sorting，通过使用堆。

使用2k元素的最小堆。 首先插入2k元素，然后删除min，插入下一个元素等

这保证了O（n log k）时间和O（k）空间和堆通常有足够小的隐藏常量。

Answer 3

由于k显然被认为是相当小的，所以插入sorting可能是最明显和普遍接受的algorithm。

在对随机元素的插入sorting中，必须扫描N个元素，并且必须将每个元素移动平均N / 2个位置，从而给出总共N * N / 2个操作。 在大O（或类似）表征中忽略“/ 2”常数，给出O（N ² ）复杂度。

在你提出的情况下，期望的操作次数是〜N * K / 2 – 但是由于k是一个常数，因此整个k/2项在大O表征中被忽略，所以总的复杂度是O （N）。

Answer 4

如果k足够大，你的解决scheme是一个很好的解决scheme。 在时间复杂性方面没有更好的解决scheme; 每个元素可能不在k位置，这意味着你需要学习log2 k位信息来正确放置它，这意味着你至less需要做log2 k比较 – 所以它至less是一个复杂度O(N log k) 。

但是，正如其他人所指出的那样，如果k很小，常数条件就会杀了你。 在这种情况下，使用一些非常快的操作，比如插入sorting。

如果你真的想要最优化，你会实现这两种方法，并根据k从一个切换到另一个。

Answer 5

有人已经指出，其中一个渐近最佳的解决scheme使用最小的堆，我只是想提供Java代码：

 public void sortNearlySorted(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int i = 0; i < k; i++) { minHeap.add(nums[i]); } for (int i = 0; i < nums.length; i++) { if (i + k < nums.length) { minHeap.add(nums[i + k]); } nums[i] = minHeap.remove(); } }