问题标签 [mergesort]

如果我们需要实现一个函数，它接受一个整数数组并返回集合中的最大整数，假设数组的长度小于 1000。你会使用冒泡排序还是归并排序，为什么？

另外，如果数组长度大于 1000，上述算法选择会发生什么情况？我对为什么我应该使用一种特定的算法而不是另一种算法感到有点困惑。仅仅是因为它的复杂性和时间还是其他因素也参与其中？如果我必须测试上述函数，而简单算法需要更多时间而复杂算法需要更少时间怎么办？

我目前正在从事一个涉及使用替换选择和 k 路合并的外部合并排序的项目。我已经用 C++ [在 linux 上运行] 实现了这个项目。它非常简单，现在只处理固定大小的记录。

对于阅读和写作，我使用 (i/o)fstream 类。在执行程序几次迭代后，我注意到

• 大小超过 4K（典型块大小）的请求的 I/O 读取块。事实上，提供大于 4K 的缓冲区大小会导致性能下降。
• 输出操作似乎不需要缓冲，linux 似乎负责缓冲输出。所以我发出一个 write(record) 而不是维护特殊的写入缓冲区，然后使用 write(records[]) 一次将它们刷新出来。

但是应用程序的性能似乎不是很好。我怎样才能提高性能？我应该维护特殊的 I/O 线程来处理读取块还是现有的 C++ 类已经提供了这种抽象？（类似于 java 中的 BufferedInputStream）

所以，基本上，这是在我的讲义上。总的来说，我觉得这很令人困惑，但我理解其中最大的部分。我不明白的是“if (j <= low + k - 1)”部分的需要。看起来它检查左侧是否有任何元素“左侧”。合并排序时甚至可能吗？

嗨，我对 Batcher 的奇偶合并排序有疑问。我有以下代码：

我将提供一些关于代码功能的评论：
它分为由变量索引的阶段p最后一个阶段p==n是批处理器奇偶合并的时间下一个阶段p==n/2是奇偶合并与第一阶段和所有比较器的时间交叉 n/2 消除倒数第三个阶段是p==n/4奇偶合并与前两个阶段和所有跨越 n/4 任意倍数的比较器消除等等。

结果是：

我错过了什么？
怎么了？

我在互联网上找到了这段代码，它是用于数组的，我想将其更改为双向链表（而不是索引，我们应该使用指针）你能帮我看看如何更改合并方法（我已经更改了排序方法我自己）这也不是我的家庭作业，我喜欢使用链表！

我试图了解合并排序的空间要求，O(n)。
我看到时间要求基本上是级别（logn）*合并（n）的数量，因此使得（n log n）。
现在，我们仍然在每个级别分配 n，在左右 2 个不同的数组中。
我明白这里的关键是当递归函数返回时，空间被释放，但我没有看到它太明显。
此外，我找到的所有信息，只是说明所需的空间是 O(n)，但不解释。
有什么提示吗？

编辑 好的，感谢@Uri，这是
我一开始没看到的技巧是时间只增加，而内存增加和减少，所以最大时间量是在执行结束时，但最大量内存位于递归堆栈的底部。

所以，如果我们继续添加 n + n/2 + n/4 + n/8.... 不管我们添加多少次，它永远不会大于 2n，当我们到达递归堆栈时底部并开始上升，我们不保留前一个分支使用的内存，所以在最大值，2n 将是使用的内存量，O(n)。

我们有两个数组或链表的合并排序如何为两个以上的链表编写合并部分？请帮帮我谢谢

我正在尝试在 Coldfusion 中实现合并排序，但它吐出不正确的结果，代码：

它在名为“attr3”的结构键上对结构数组进行排序。发生的事情是它似乎正确地拆分了列表，但随后继续将相同的列表附加到结果集中。因此，例如，如果我将 left_.attr3 作为“Title”，将 right_.attr3 作为“Another”，则结果最终是“Title”、“Another”、“Another”、“Another”……等等。

我遇到了以下问题。

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

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

我编写了一个 java 程序，可以在具有不同数量处理器的不同机器上测试几个多线程算法的速度。

在某些机器上，归并排序* 会失败，因为它需要相当大的堆空间来处理非常大的数组。在运行程序之前，我可以自己轻松地更改 Java 堆空间，但我觉得更健壮和简单的方法是从程序本身内部完成这项任务。

有没有办法在 Java 程序的过程中从虚拟机请求/获得更多的堆空间？

注意：我知道我可以使用“java -Xmx1g Program”之类的脚本来执行程序；我对这个主题的好奇心部分是学术性的。

*我的实现不会在线合并。它需要 O(n) 额外的内存。