问题标签 [mergesort]

我有一个结构：

数组

和一个文件，所以用这个读入文件

和比较方法

我想要一个具有 nlog(n) 时间的稳定排序，或者按从最低到最高的顺序合并排序

我只需要 20 个最低的价格。

我将如何使用我的比较方法来实现这一点？

谢谢

我有以下代码用于自下而上的合并排序，它对文件进行操作 m-by-m 每次通过时合并双倍 m 这里是代码

但是当我运行此代码时，出现异常，表示发生矢量超出范围错误，请帮助

http://pt.wikipedia.org/wiki/Merge_sort#Java 该代码无法编译。

谢谢你。

在我深入解释之前，您应该知道以下代码可能非常糟糕。我大约 2 个月前开始编程（在那里和那里几个小时）。所以我缺乏经验，我的编码风格非常可改进，我仍然怀念实践和大量（基本）知识。这也包括我可能用错误的名字称呼事物:)。

我对算法（大学）很感兴趣，想练习一些指针处理（一开始有很多问题），所以我决定用单链表进行合并排序，看看它与我教授的合并排序算法（其中排序数组）。不，这不是家庭作业（我的大学课程（电气工程）都没有家庭作业）——这是我对算法、C 语言和简单练习的理解的提高。

我的代码已经可以工作了。出于测试目的，我总是创建反向排序列表。对于列表为 NULL 的情况，它仍然缺少一些东西。

因此，在发布我正在使用的结构的代码之前：

我有两个函数，mergeSort 和 merge。mergeSort 返回排序（子）列表的新头部，merge 返回合并序列的头部。

现在我给 mergeSort 未排序列表的当前头部和元素的数量。然后它递归地分解列表（显然:)）。我不确定对以下代码要说多少。如果有什么不清楚的地方，我会尽快回答和解释，但是

merge 接收两个子列表的头部（可以是一个元素或已经排序的序列）以及第一个和第二个列表的元素。

因此，我欢迎任何关于我所做的愚蠢的评论，我没有考虑可能的问题，一些输入代码破坏代码或如何做得更好，我相信还有很多改进的可能性。提前致谢。

在“算法简介”中，合并排序算法是通过一个名为的辅助函数实现的MERGE(A, p, q, r)- 即合并两个先前排序的序列。

这个函数引入了两个额外的数组L和R.

据"create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]"我了解为他们两个分配额外的内存。

是否可以重写这个函数，这样我就不需要额外的内存，直接对 A 进行操作？

你们中的大多数人都会意识到这一点，但对我来说，这有点令人惊讶：使用合并排序（保持信息总量不变）对（例如）每个大小为 4Mb 的 96 个文件进行排序比对 6 个 64Mb 的文件进行排序要快得多。我偶然发现了这个发现。所以这就引出了一个问题，合并排序的最佳输入文件大小是多少？

我假设排序时间（y 轴）和文件数量（x 轴）之间存在曲线形状的关系。有没有一种算法，是更多的经验法则还是只是尝试几种不同的文件大小？会影响这一点的明显因素是： * 操作系统可以同时打开的最大文件数。
* 硬盘的读/写速度

欢迎任何参考！

我按照mergesort算法在Xcode上用C语言编写了这段代码。问题是有时我得到 EXC_BAD_ACCESS 并且我无法管理错误在哪里！合并算法应该可以工作（我在合并排序函数之外尝试过并且可以工作！）。感谢您的帮助和耐心！

编辑：非常感谢！但我认为还有另一个问题，当我尝试对更大的数组（200 个元素）进行排序时，程序不起作用（我得到一个 malloc 错误：释放对象的校验和不正确 - 对象可能在被释放后被修改）。但是，如果我从 xCode 调试器运行它，一切正常

i want to write merge sort algorithm,when i debug the program and give numbers to it,it goves index out of range error,whats the problem of my code?thanks in advance.

这段代码应该像归并排序算法一样工作，但它不起作用并给出输出 0 而不是对数字进行排序，朋友有什么问题？谢谢

这段代码给出了输出，但它有一个问题是当用户在 textbox1 中写入 5,6 和在 textbox3 中写入 7,8 时，它输出 5,6。我知道问题是当数组的元素结束时，它不会打印其余部分其他数组的元素，我评论了问题行。

编辑：我使用 textbox1 和 textbox3 来获取用户想要合并的数组元素