问题标签 [mergesort]

我有用户在 textBox3 中输入的数字，我将它们转换为数组 nums 现在我想将其中的一半放在 arraylist A 中，将一半放在 arraylist B 中我该怎么做？谢谢

编辑：

谢谢，我测试了你的答案，但你所有代码的输出都是 system.collection.generic [system.int32]，有什么问题？谢谢

例如，我测试了 ArsenMkrt 写的这个：

我正在尝试在 Java 中实现几种排序算法，以比较性能。根据我的阅读，我期望 quickSort 比 mergeSort 更快，但在我的代码中它不是，所以我认为我的 quickSort 算法一定有问题：

结果（在 0 到 1500000 之间的 100 万个整数上）：

mergeSort（也用 arrayList 实现）：1.3sec（平均）（0.7sec 用 int[] 代替）

快速排序：3 秒（平均）

只是我的支点选择不好，还是算法中也存在一些缺陷。

另外，有没有更快的方法用 int[] 而不是 ArrayList() 来编码？（如何声明更大/更小数组的数组大小？）

PS：我现在可以以就地方式实现它，因此它使用更少的内存，但这不是重点。

编辑 1：我通过更改 concat 方法赢得了 1 秒。谢谢！

好的，我知道 Mergesort 的最坏情况时间为 theta(NlogN)，但它的开销很高，并且出现在进行合并的递归树的底部附近。有人建议我们在大小达到 K 时停止递归，并在此时切换到插入排序。我需要证明这个修改后的递归关系的运行时间是theta(NK + Nlog(N/k))？我对如何解决这个问题感到茫然..

我制作了这个程序来对数组进行排序。它工作正常，但它不会排序！请帮我找出我的逻辑中的错误。谢谢

[更新]它能够工作！我只是按照下面的建议降低了 i、j 和 k。另外，从 i

有人可以告诉我下面的合并排序实现有什么问题吗？我已经挠头好几个小时了..

在这里回顾我的基本 ADT 内容以修改面试，并在我学习 Java 的同时尝试用一块石头杀死两只鸟。尝试使用通用链表（我自己创建）为合并排序编写一个简单的算法。事实证明这比我最初想象的要困难得多！谁能帮帮我？我将开始研究基础知识，并在我进一步深入时更新这篇文章。

我的通用链表代码如下：

我正在尝试在我制作的另一个类中访问这个类，如下所示：

我相信，到目前为止，在 add 和 addEnd 方法之前，一切都是正确的，它们应该分别在列表的开头和列表的结尾添加一个泛型。

我的代码继续：

我得到了错误：

MyList 中的 addEnd(S) 不能应用于 (NodeList)

当我跑步时发生

leftSide.addEnd(节点);

谁能看到这个原因/告诉我我的工作是否正确？再次非常感谢！

我在论坛中阅读了以下内容：

合并排序对于链表等不可变数据结构非常有效

和

当数据存储在内存中时，快速排序通常比合并排序快。但是，当数据集很大并且存储在硬盘等外部设备上时，归并排序在速度方面显然是赢家。它最大限度地减少了外部驱动器的昂贵读取

和

对链表进行操作时，归并排序只需要少量的常量辅助存储

有人可以帮我理解上述论点吗？为什么对大型链表进行排序时首选合并排序？它如何最大限度地减少对外部驱动器的昂贵读取？基本上我想了解为什么要选择合并排序来对大链表进行排序。

我在谷歌搜索：“并行合并排序”并找到“奇/偶合并”是基本组件的算法，但不明白如何使用它。

你能给我链接到并行合并排序的实现或伪代码吗？

我已经用 C 编写了这个“合并排序”。我认为在将元素复制回原始数组时存在错误。有人能帮我吗？

非常感谢提前。

在必须“最有效地”使用内存的 C++ 中，什么是“合并排序”的最佳算法？我只知道执行此操作的标准方法，但这不是使用内存的最有效方法。这是我知道的唯一变体：

谁能告诉我一个更好的“合并排序”算法，它以“更有效”的方式使用内存？它也不能与数组一起使用。

非常感谢！