MergeSort变体的差异？
我正在上大学html" target="_blank">数据结构课程
当涉及到普通的MergeSort和自上而下的MergeSort时 - 有什么区别？到目前为止，我所读到的内容使我相信：
“正常”MergeSort只是将已经排序的数组/文件拆分为两半，并将其放入辅助数组中。然后我们开始通过连续比较左边的元素和右边的元素来检查辅助数组，将这些元素按排序顺序写入原始数组。
自上而下的MergeSort递归地将一个未排序的数组拆分为更小的部分，直到我们得到一个大小为1的数组（技术排序），直到两个原始的半部分都被排序，然后应用“普通”的MergeSort来得到最终的数组。
我确信我的理解是错误的——我在合并排序方面遇到了很多麻烦。有人能为我澄清一下吗？
谢了。
共有2个答案
MergeSort最流行的变体是自顶向下的，正如尼克·祖伯详细描述的那样。
自下而上的变体不会将整个阵列划分为越来越小的部分。相反，它在第一阶段合并长度为 1 的数组，在第二阶段合并长度为 2 的数组，在
第三阶段合并长度为 4 的数组，
依此类推，直到达到全长。
考虑一下尼克的计划从第四行到最后一行，它们是自下而上的阶段。
< code>merge sort的整体思想是使用分治法对列表进行排序。
规则是，只有在右辅助数组和左辅助数组都已排序的情况下，才能比较它们的元素。当列表最初未排序时，我们能保证子数组排序的唯一方法是当它只有一个元素时。此时，我们开始< code>merge部分，该部分比较来自左右辅助数组的元素，并将它们排序回主数组。
以下是我们< code >合并排序时发生的情况的示例:
如您所见，我们只需将数组减半，直到得到一个保证排序的数组（只有1个元素），现在我们可以将子数组合并在一起，因为它们是排序的。
如果您想了解更多关于它的信息，这里有一些很好的来源，但在我看来，您似乎在概念上掌握了merge-sort应该做什么，您可能只是将一些技术混淆了一些。
- https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/overview-of-merge-sort
- https://en.wikipedia.org/wiki/Merge_sort
- http://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html
-
我使用两个数组编写了一个简单的MergeSort实现，它输出垃圾： 1 2 3 2 5 4 4 3 9 8 8 7 8 7 6 5 17 16 16 15 16 15 14 13 16 15 14 13 12 11 10 9 33 32 31 32 31 30 29 32 31 30 29 28 27 26 25 25 32 31 30 29 28 27 26 25 24 23 22 21 20
-
如何查看改装错误正文消息？我所看到的是字节数组，我读它有困难。
-
问题内容： 我正在类 JAXBContext中* 尝试各种形式的 newInstance 方法（我正在使用Oracle JDK 1.7附带的默认Sun JAXB实现）。 * 我不清楚何时可以将具体类与 ObjectFactory* 类传递给 newInstance 方法。我应该注意，我纯粹是在解析XML文件时使用JAXB，即仅在XML-> Java方向上使用。 * 这是证明我的观点的绝对最少的代码
-
我在实现合并排序时遇到了分段错误。我已经检查了数组是否超出边界。我想得到一些帮助，找出我哪里出了问题。我尝试过小数组的输入，例如大小为10的数组，我将temp的大小作为静态值( 更新:我只需要改变mid=(低高)/2。
-
我想保存两个实体的差异。旧实体有一个id女巫不是空的。新的id值为null，所以我将它们作为ValueObject进行比较。问题是ValueChange确实保存了差异，但没有保存旧的id。ich如何做到这一点？
-
我正在开发一个程序来解决0/1背包问题的变体。 原始问题如下所述：https://en.wikipedia.org/wiki/Knapsack_problem.如果将来链接丢失，我会给你一个0/1背包问题的摘要（如果你熟悉它，跳过这一段）：假设我们有项，每个项都有重量和值。我们想把物品放在一个袋子里，这个袋子支持最大重量，这样袋子里的总价值是最大的，而不会加重袋子的重量。项目不能有多个实例（即，我