问题标签 [mergesort]

我有两个 1 GB 的文件，每个文件仅包含按排序顺序的数字。现在我知道如何读取文件的内容并使用合并排序算法对它们进行排序并将其输出到另一个文件中，但我感兴趣的是如何仅使用 100MB 缓冲区大小来执行此操作（我不担心划痕空间）。例如，一种方法是从两个文件中读取 50 MB 块并对其进行排序，当它被排序时，我可以读取一个新元素并继续该过程，直到我到达两个文件的末尾（任何人都可以告诉我如何实现这）。

由于 Internet 通信，我可能有两个（或多个）相同数据周期的 RINEX 格式（GPS ASCII 格式）的 ASCII 文件，我想将它们合并到一个文件中。

每个数据集（epoch）包含多于一行（在本例中为 19 行）。我想合并这些文件，它们可能在某些部分相互重叠。

这是 RINEX epoch 数据集的示例：

第一行包含时间信息，下面是每个 GPS 卫星的原始数据。

我的想法是单独打开每个文件并将原始数据存储在某种与时间相关的数组中。每次我读到新的纪元时，我都会问我的数组是否已经有了时间某某的东西，如果没有，我将原始数据放在那里。

我的问题是如何存储与时间相关的原始数据，因为它不是一条线，而是一种动态的东西，总是可以改变的。

如果您有更好的想法，请与我分享。

问候

我在使用自下而上的归并排序时遇到问题。我在排序/合并时遇到问题。当前代码包括：

我正在复习我的数据结构和算法分析课，我得到一个问题，如何确定合并排序和快速排序 算法的空间复杂度？

链表合并排序的递归深度仅为 O(log n)

连续快速排序所需的额外存储空间量为 O(n)。

我的想法：

两者都使用分治策略，所以我猜链表合并排序的空间复杂度应该与连续快速排序相同。实际上我选择 O(log n) 因为在每次迭代或递归调用之前，列表被分成两半。

感谢您的任何指示。

谁能指出我对外部内存合并排序的一个很好的参考？我已经阅读了 wiki 页面，但无法准确理解它。动画可能会有所帮助，但我似乎找不到。

基本上，我知道您在磁盘上有一定数量的块，并且您可以在内存中放置一定数量的块。假设您在磁盘上有 32 个块，在内存中有 4 个块。在第一遍中，您一次将 4 个块读入内存，在内存中对它们进行排序，然后将它们写回磁盘。所以此时你有 4 个块的 8 次排序运行。合并是如何工作的？由于我在内存中有 4 个块（假设我还有一个用于输出），我想我应该能够一次合并这 8 个运行中的 4 个，然后合并接下来的 4 个运行。然后在最后一遍我想合并整个事情。但是您不必每次都从磁盘读取每个块吗？那么这怎么不成为一个^2的解决方案呢？

我写了整个事情，但我得到了模糊的错误。我不知道出了什么问题......呃。另外，你可能会问为什么我的老师在测试中使用非递归方法。

我正在尝试使用void*. 如果我保留想要排序为 1 字节的数字，它可以完美运行。但是，如果数字位于超过 1 个字节中，则效果不佳。我相信它需要2个数字。我用数字 500 对其进行了测试，最后我有 256 和 244 没有排序....

主文件

1 字节数字的输出正常：

如果有 2 字节数字，则输出不正常，排序效果不佳：

Snape 的“Unfriendly Algorithms for Wizards”教科书声称归并排序的运行时间为 O(n^4)。这种说法正确吗？

解决方案：是的。这种说法在技术上是正确的，因为 O(n^4) 只给出了算法需要多长时间的上限。然而，这是一个令人讨厌的无用答案，因为严格的界限是Θ(n log n).

我不太明白解决方案在说明什么。O(n^4) 怎么可能是正确的？

我有各种排序方法，它们都对相同的 100,000 个随机数数组进行排序。

我正在使用以下方法来查找每个的运行时

以下为随机数数组

我该如何修改它，以便我可以让它们中的每一个对 1​​00 个数组而不是一个数组进行排序，并计算每个数组的时间？例如。运行1 - 23ms；运行 2 - 25 毫秒；... 运行 100 - 22 毫秒

编辑： 我还有最后一件事要做。所以每次迭代都会以几种方式对数组进行排序，比如说插入、合并和快速排序。所以说插入 = 300 毫秒，合并 = 200 毫秒，快速 = 100 毫秒。对于每次迭代，我需要找到排序最快的方法。

我知道这是一个简单的最小/最大类型的事情，你在较低的编程课程中做了一千次。将每个值放入数组并使用 array.min 调用会更容易吗？（不管它实际上是什么，Java 语法的新手..）

我有以下代码

但这是这样的警告

请帮我修复它

我已经更新了我的代码