问题标签 [mergesort]

我现在对此感到非常恼火。我正在为大学学习合并排序，并且正在经历我在网上找到的这种合并排序。但是，我似乎没有得到重复，我想要重复。它的这一点如下，但我已经评论了这一点和东西，它使排序无法正常工作。有什么办法可以保留重复项吗？如果您能保持答案简单，我将不胜感激。谢谢

我有一些处理列表的函数。我有一个偶数函数，它接受一个列表参数并获取列表的偶数索引。奇函数做同样的事情，但索引奇数。我还有另一个合并两个排序列表的函数，称为合并列表，它接受两个列表作为参数。

问题在于我现在正在编写的函数：合并排序。

这是我所拥有的：

出于某种原因，我不断收到错误

java.lang.ClassCastException: clojure.lang.PersistentList cannot be cast to clojure.lang.IFn

我可以像这样传递奇函数rest lis (odd(rest lis))（与偶数相同）。它运行良好，但这显然没有给我想要的解决方案。

我对 Clojure 很陌生，所以任何提示都将不胜感激。谢谢。

我需要使用归并排序对 1000 个整数的列表进行排序；据我所知，我的算法看起来应该可以工作，但是当我打印出“排序”列表时，它仍然没有排序。我真的很难过，我想知道是否有人能指出我正确的方向。这是我的代码：

我有一个单线程版本的合并排序http://pastebin.com/2uMGjTxr

它创建一个数组，用随机数填充它并调用它的 sort 方法来执行合并排序：

现在我想使用 java 中的多线程技术来提高性能。代码来自我的导师，他说我必须在排序方法中添加一些东西，但这实际上让我感到困惑。

归并排序是一种分而治之的算法：

• 如果列表的长度为 0 或 1，则它已经排序。否则：
• 将未排序的列表分成两个大约一半大小的子列表。
• 通过重新应用合并排序对每个子列表进行递归排序。
• 将两个子列表合并回一个排序列表。

所以我实际上会为每个子列表启动一个线程。你怎么看？如何根据给定实现并行化合并排序？有谁知道为什么我应该编辑排序方法？

我尝试parallelize我的合并排序实现： http: //pastebin.com/2uMGjTxr。我想创建 Java-VM 可以提供的尽可能多的线程。我想使用java.lang.Runtime确定可能的最大线程数。

所以我想出了一个名为 MergeThread 的类：

还有一个真正开始这个过程的类

但是，这种合并排序不起作用。控制台打印了很多java.lang.OutOfMemmoryError's unable to create new native thread.

稍后，消息更改为类似java heap.

我必须更改什么才能使合并排序正常工作，以及如何使用 java.lang.Runtime 来实现？

我知道归并排序的运行时间是 O(n*lg(n)) 并且归并排序是比较排序，这也意味着在最坏的情况下需要 Ω(n logn) 对列表进行排序。

因此，我可以得出结论，归并排序的运行时间是 theta(n*lg n) 吗？

这是在一次采访中问我的，这是我提供的解决方案：

有没有更有效的方法来做到这一点？

编辑：更正了长度方法。

我有一个不寻常的问题。我一直在实现合并排序并遇到以下情况： 该方法正常工作，除了最后一次。给定一个随机Integer数组作为输入，返回一个Integer数组，其中前半部分和后半部分分别排序。合并工作正常，除了最后一次。在摆弄调试器几个小时后，我发现“提及点”总是false在最后一次通过时评估，即使它不应该基于值。

感谢所有帮助。

http://pastebin.com/YMS4ehRj

^ 这是我的并行合并排序实现。基本上我所做的是，对于每个拆分，前半部分由一个线程处理，而后半部分是顺序的（即）说我们有一个由 9 个元素组成的数组，[0..4] 由线程 1 处理，[0 ..1] 由线程 2 处理，[5..6] 由线程 3 处理（请查看源代码以获得说明）。

其他一切都保持不变，例如合并。但问题是，这比归并排序慢得多，甚至比普通冒泡排序还要慢！我的意思是一个 25000 个整数的数组。我不确定瓶颈在哪里：是互斥锁吗？是合并吗？

关于如何加快速度的任何想法？

MergeSort 是一种分而治之的算法，它将输入分成几个部分并递归求解这些部分。

...拆分功能有几种方法。一种方法是从中间分开。这种方法有一些很好的特性，但是，我们将专注于一种更快一点的方法：奇偶分割。这个想法是将每个偶数位置的元素放在一个列表中，将每个奇数位置的元素放在另一个列表中。

这直接来自我的讲义。为什么奇偶分割比数组中间更快？

我推测它与传递给 MergeSort 的列表以及已经排序的质量有关，但我不完全确定。

任何人都可以对此有所了解吗？

编辑：我尝试在 Python 中运行以下命令...

（MergeSort 是奇偶合并，MergeSort2 向下划分中心）

结果是：

0.771506746608

0.843161219237