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

Question

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

You're given an array that is almost sorted, in that each of the N elements may be misplaced by no more than k positions from the correct sorted order. Find a space-and-time efficient algorithm to sort the array.

我有一个 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 时，这最后一步可能比其他步骤成本更低

在每个步骤中，您最多对 O(k log k) 中的 2k 元素进行排序，将至少 k 元素放入它们的最终在每个步骤结束时排序的位置。有 O(N/k) 个步骤，因此整体复杂度为 O(N log k)。

我的问题是:

• O(N log k) 是最优的吗？这可以改进吗？
• 你能做到这一点而不(部分地)重新排序相同的元素吗？

Answer 1

作为Bob Sedgewick在他的论文工作(和后续论文)中显示，插入排序绝对粉碎“几乎排序的数组”。在这种情况下，您的渐近线看起来不错，但如果 k < 12，我敢打赌插入排序每次都会获胜。我不知道是否有很好的解释为什么插入排序做得这么好，但可以在 Sedgewick 的一本题为算法的教科书(他已经完成不同语言的许多版本)。

• 我不知道 O(N log k) 是否最优，但更重要的是，我真的不在乎——如果 k 很小，那么重要的是常数因子，如果 k 很大，您也可以只对数组进行排序。

• 插入排序将解决这个问题，而无需重新排序相同的元素。

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