16

我遇到了以下问题。

给定一个包含n 个元素的数组和一个整数k，其中k < n。元素 { a 0 ... a k } 和 { a k +1 ... a n } 已经排序。给出一个在 O( n ) 时间和 O(1) 空间中排序的算法。

在我看来，它似乎不能在 O( n ) 时间和 O(1) 空间内完成。问题似乎真的是在询问如何就地进行合并排序的合并步骤。如果可能的话，合并排序不会以这种方式实现吗？我无法说服自己，需要一些意见。

4

3 回答 3

9

这似乎表明可以在 O(lg^2 n) 空间中进行操作。我看不出如何证明不可能在恒定空间中合并，但我也看不出如何去做。

编辑：追逐参考资料，Knuth Vol 3 - 练习 5.5.3 说“L. Trabb-Pardo 的一个相当复杂的算法为这个问题提供了最好的答案：可以在 O(n) 时间内进行稳定的合并并且稳定在 O(n lg n) 时间内排序，对于固定数量的索引变量，仅使用 O(lg n) 位辅助存储器。

更多我没有读过的参考资料。感谢一个有趣的问题。

进一步编辑：本文声称 Huang 和 Langston 的文章有一个算法，可以在时间 O(m + n) 内合并两个大小为 m 和 n 的列表，因此您的问题的答案似乎是肯定的。不幸的是，我无法访问这篇文章，所以我必须相信二手信息。我不确定如何将这与 Knuth 的 Trabb-Pardo 算法是最优的声明相协调。如果我的生活取决于它，我会选择 Knuth。

我现在看到这个问题已经被问过很多次了。我不忍心将其标记为重复。

黄 B.-C. 和 Langston MA，实用的就地合并，Comm。ACM 31 (1988) 348-352

于 2010-07-20T01:16:04.003 回答
2

有几种算法可以做到这一点，但都不是很容易直觉。关键思想是使用数组的一部分作为缓冲区进行合并，然后使用此缓冲区作为辅助空间进行标准合并。如果您可以重新定位元素以使缓冲区元素位于正确的位置，那么您就是黄金。

如果您有兴趣查看它，我已经在我的个人网站上编写了其中一种算法的实现。它基于 Huang 和 Langston 的论文“Practical In-Place Merging”。您可能需要查看该论文以获得一些见解。

我还听说对此有很好的自适应算法，它使用您选择的一些固定大小的缓冲区（如果您愿意，可以是 O(1)），然后随着缓冲区大小优雅地缩放。我不知道其中的任何一个，但我确信快速搜索“自适应合并”可能会出现一些问题。

于 2010-11-13T23:40:32.260 回答
1

不，这是不可能的，尽管如果是这样的话，我的工作会容易得多:)。

您有一个无法避免的 O(log n) 因素。您可以选择将其视为时间或空间，但避免它的唯一方法是不排序。使用 O(log n) 空间，您可以构建一个延续列表，以跟踪您将不太适合的元素隐藏在何处。通过递归，这可以适应 O(1) 堆，但这只能通过使用 O(log n) 堆栈帧来代替。

这是从 1-9 合并排序赔率和偶数的进度。请注意您如何需要日志空间记帐来跟踪由常量空间和线性交换的双重约束引起的顺序倒置。

. -
135792468
 . -
135792468
  : .-
125793468
   : .-
123795468
    #.:-
123495768
     :.-
123459768
      .:-
123456798
       .-
123456789

123456789

有一些微妙的边界条件，比二分搜索稍微难一点，即使是这种（可能的）形式，因此是一个糟糕的作业问题；但真的是很好的脑力锻炼。

更新 显然我弄错了，有一种算法可以提供 O(n) 时间和 O(1) 空间。我已经下载了论文来启发自己，并将这个答案作为不正确的答案撤回。

于 2010-07-20T02:34:13.053 回答