2

我已经阅读了书籍，但遇到了我无法解决的问题。我查资料很久了。我打破了我的想法试图理解它。

因此，我得到了一个长度为 N (int) 的数组，以使用非递归合并排序算法对其进行排序。我学习了长度为 2^n 的数组的合并排序算法。但我完全不明白它对长度为 N 的数组是如何工作的。

有人可以解释一下它是如何工作的吗？

4

2 回答 2

4

给定七个元素，子任务树如下所示：

          [3,5,2,1,4,7,6]
             /         \
      [3,5,2,1]        [4,7,6]
      /       \        /      \
   [3,5]    [2,1]    [4,7]    [6]
   /   \    /   \    /   \    /
 [3]  [5]  [2]  [1] [4]  [7] [6]

这个想法是在每个级别将数组“分成两半”。如果一个数组有奇数个元素，那么拆分它会导致一个子数组比另一个多一个元素。它不会使问题变得更加困难：合并两个不同长度的数组并不麻烦。

于 2019-10-08T20:08:05.297 回答
0

非递归合并排序将包含 N 个元素的数组视为大小为 1 的 N 次排序运行，然后将偶数和奇数运行从一个数组合并到另一个数组。如果有奇数个运行，最后一个只是被复制（没有合并它），这可以在 merge() 函数中处理。完成一次合并后，运行大小加倍为 2，并重复合并过程。当运行大小加倍并且 >= 数组大小时，合并排序完成。

代码维护 3 个索引：左运行开始、右运行开始（== 左运行结束）、右运行结束。在设置或推进索引时，如果索引变为 >= 数组大小，则它会减小为数组的大小。如果这发生在左边的运行中，那么这是最后一个奇怪的运行，所以它被复制（同样，这可以在 merge() 函数中处理）。

维基百科有伪代码：

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation

于 2019-10-08T08:00:06.197 回答