对几乎排序的数组进行排序(元素放错的位置不超过 k)

最近有人问我这样一个面试问题:

您得到一个几乎排序好的数组，因为每个 N元素都可能在正确的排序顺序中错放了不超过 k的位置。找到一个空间和时间有效的算法来对数组进行排序。

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

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

  • 排序 arr[0..2k)
    • 现在我们知道 arr[0..k)已经到了最后排序的位置。
    • 但是 arr[k..2k)可能还是被 k放错了地方！
  • 排序 arr[k..3k)
    • 现在我们知道 arr[k..2k)已经到了最后排序的位置。
    • 但是 arr[2k..3k)可能还是被 k放错了地方
  • 排序 arr[2k..4k)
  • ....
  • 直到你排序 arr[ik..N)，然后你就完成了！
    • 当剩下的 2k元素少于 2k元素时，这最后一个步骤可能比其他步骤更便宜

在每个步骤中，对 O(k log k)中的大多数 2k元素进行排序，在每个步骤结束时至少将 k元素放在它们的最终排序位置。有 O(N/k)步骤，所以总体复杂度是 O(N log k)。

我的问题是:

  • O(N log k)是最佳的吗? 这个可以改进吗？
  • 您能在不(部分地)重新排序相同元素的情况下做到这一点吗？
36882 次浏览
小开

由于 k显然被认为是非常小的，所以插入排序可能是最明显和被普遍接受的算法。

在随机元素的插入排序中，你必须扫描 N 个元素，你必须移动每个元素的平均 N/2位置，给出 ~ N * N/2的总运算。“/2”常数在大 O (或类似)角色塑造中被忽略，从而导致 o (N2)的复杂性。

在你提出的例子中，预期的操作数是 ~ N * k/2——但是因为 k是一个常数，所以整个 k/2项在一个大 O 角色塑造中被忽略了，所以整体的复杂度是 O (N)。

小开

正如 Bob Sedgewick在他的论文工作(和后续工作)中所展示的，插入排序绝对是 迷恋的“几乎排序的数组”。在这种情况下，渐近性看起来很好，但是如果 k < 12，我打赌插入排序每次都会赢。我不知道对于 为什么插入排序是否有一个很好的解释，但是我们可以在塞奇威克的一本名为 算法的教科书中找到(他已经为不同的语言编写了许多版本)。

  • 我不知道 O (N log k)是否是最优的，但更重要的是，我并不关心 & mash; 如果 k 很小，那么常量因子才是最重要的，如果 k 很大，你也可以对数组进行排序。

  • 插入排序不需要重新排序相同的元素就可以解决这个问题。

大 O 符号对于算法类来说非常好，但是在现实世界中，常量很重要。我们很容易忽视这一点。(作为一个教过 Big-O 记谱法的教授，我这样说!)

小开

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

然而，正如其他人所指出的，如果 k很小，常数项将会杀死你。在这种情况下，每次操作都使用非常快的方法，比如插入排序。

如果您真的希望达到最优，那么可以同时实现这两种方法，并根据 k从一种方法切换到另一种方法。

小开

如果只使用比较模型，O (n log k)是最优的。

要回答您的另一个问题，是的，通过使用堆，不进行排序就可以做到这一点。

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

这保证了 O (n log k)时间和 O (k)空间以及堆通常具有足够小的隐藏常量。

小开

已经指出，其中一个渐近最优的解决方案使用 min 堆，我只想提供 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();
}
}

提交答案