具有两个嵌套循环的非递归合并排序 - 如何？

这是第一个问题，是的，这是一个家庭作业问题。我们的任务是对数组（我熟悉的）执行合并排序，但在某种程度上我不确定该怎么做。通常我会有一个单独的合并和合并排序函数，并使用这两个函数。不过，听起来他想要一切都用一种方法？我只是希望有人可以帮助我解决问题，或者用我可以更好理解的术语来表达它们。

从任务中：

您将需要实现合并排序的非递归版本 算法。安排两个嵌套循环来完成此任务。外层 循环应提供用于合并的段的大小。内循环 应注意选择段的位置。内循环 应从左边缘开始并将片段移至右侧。 将变量左、中、右排列适当的值，使得 只需迭代调用即可完成排序 合并（a，左，中，右）。

我讨厌说得这么含糊，但我真的听不懂他在说什么。首先，“外循环应提供段的大小”是什么意思？一个循环是如何实现的provide任何事物？下一句话怎么样——他所说的分段是什么意思？数据？

我不是要求代码，但任何伪代码都会非常有帮助。

如果有人能尝试解读他的意思，我将不胜感激。我已经给他发了电子邮件询问此事，但几个小时过去了，我还没有收到回复。

谢谢你！

这并不难。考虑递归合并：

       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+
            /     \               split
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+
      /   \         /  \          split
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
  / \     / \     / \     / \     split
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
  \ /     \ /     \ /     \ /     merge
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
      \   /         \  /          merge
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+
            \     /               merge
       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+

如果你注意到的话，当你分手时，你并没有真正做任何事情。您只需告诉递归函数对数组进行部分排序即可。对数组进行排序首先对两半进行排序，然后将其合并。基本上，你所拥有的是这样的：

+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
  \ /     \ /     \ /     \ /     merge
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
      \   /         \  /          merge
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+
            \     /               merge
       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+

现在从这里应该很明显了。首先将数组的元素合并为 2 × 2，然后合并 4 × 4，然后合并 8 × 8 等。这就是外部for给你 2, 4, 8, 16, 32, ...（这就是它所谓的段的大小因为i循环的包含该数字）和内部for（用迭代器说j) 遍历数组，i by i合并array[j...j+i/2-1] with array[j+i/2..j+i-1].

我不会编写代码，因为这是家庭作业。

Edit:一张关于内部如何的图片for works

想象一下如果i是 4，所以你现在处于这个阶段：

  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
      \   /         \  /          merge
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+

你将会有一个for曾经给你0（这是0*i) as j进而4（这是1*i) as j. (if i是 2，你会j像 0、2、4、6）

现在，一旦您需要合并array[0..1] with array[2..3]（其公式为array[j..j+i/2-1] and array[j+i/2..j+i-1] with j = 0） 进而array[4..5] with array[6..7]（由相同的公式制定array[j...j+i/2-1] and array[j+i/2..j+i-1]因为现在j = 4） 那是：

i = 4:
       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+
        ^ ^ ^ ^ ^ ^ ^ ^
        | | | | | | | |
       / / / /   \ \ \ \
     (j  =  0)   (j  =  4)
      | | | |     | | | |
      j | | |     j | | |
      | | | j+i-1 | | | j+i-1
      | | j+i/2   | | j+i/2
      | j+i/2-1   | j+i/2-1
      | | | |     | | | |
      | | | |     | | | |
      \ / \ /     \ / \ /
       v   v       v   v
       merge       merge

希望这一点至少清楚一点。

侧面帮助：如果您真的不知道如何操作，只是一个提示for works:

for (statement1; condition; statement2)
{
    // processing
}

就像写作

statement1;
while (condition)
{
    // processing
    statement2;
}

所以，如果你总是写

for (int i = 0; i < 10; ++i)

这意味着从0开始，而i小于 10，做一些事情i然后递增它。现在如果你愿意i要改变不同，你只需改变statement2例如：

for (int i = 1; i < 1024; i *= 2)

（尝试理解最后的结果是如何for基于其等效项的作品while我写给你的）