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

Question

第一个问题,是的,这是一个功课问题.我们的任务是在数组上执行合并排序(我很熟悉),但在某种程度上我不确定如何做.通常我会有一个单独的合并和合并排序功能,并使用这两个.然而,听起来他想用一种方法做所有事情？我只是希望也许有人可以帮我清理一下,或者说出我能更好理解的条款.

从作业:

您需要实现一个非递归版本的merge-sort算法.安排两个嵌套循环来完成此任务.外循环应提供合并段的大小.内环应该注意选择段的位置.内循环应从左边缘开始,并将分段向右移动.排列左,中,右变量的适当值,以便通过迭代调用合并(a,left,middle,right)来完成排序.

我讨厌这么模糊,但我真的不明白他在说什么.首先,"外环应该提供段的大小"是什么意思？循环如何提供任何东西？下一句话怎么样？他对段的意思是什么？数据？

我不是要求代码,但任何伪代码都会非常有用.

如果有人可以尝试破译他的意思,我会很感激.我已经通过电子邮件向他发了电子邮件,但已经过了几个小时,我还没有回复.

谢谢!

Answer 1

这并不困难.考虑递归合并:

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

如果你注意到,当你分手时,你什么都不做.您只需告诉递归函数对数组进行部分排序.对数组进行排序包括首先对两半进行排序然后合并它.所以基本上,你有这个:

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

从现在开始,这应该是显而易见的.您首先由2合并阵列2的元素,4乘4,然后乘8等即外然后for给你2,4,8,16,32,...(这是它所谓的大小段,因为i在循环的包含该号码)和内for(与迭代说j)变为在阵列上,i通过i合并array[j...j+i/2-1]使用array[j+i/2..j+i-1].

我不会写代码,因为这是作业.

编辑:内部如何for运作的图片

想象一下如果i是4,那么你就处于这个阶段:

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

你会有一个for曾经给你0(当然0*i)j然后4(也就是1*i)j.(如果i是2,你会j像0,2,4,6那样)

现在,一旦你需要合并array[0..1]使用array[2..3](通过制定array[j..j+i/2-1]和array[j+i/2..j+i-1]使用j = 0),然后array[4..5]用array[6..7](这是由相同的公式制定array[j...j+i/2-1]并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工作,那就是一个暗示:

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我写的等同物)