这部分代码会在合并排序中执行吗?

安娜·戴维(Ania David)

合并排序的算法是

步骤1-如果它只是列表中已经被排序的一个元素,则返回。第2步-将列表递归分为两半,直到无法再将其划分为止。步骤3-将较小的列表按排序顺序合并到新列表中。

使用以下psedu代码:

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array

   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while

   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while

   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while

   return c

end procedure

我的问题是:

合并功能,有两个while循环来检查ab仍然有项目,并将它们添加到c阵列。

我的疑问是(可以)在同一函数中执行这两个while吗?

还是喜欢如果a还有物品,那意味着b一定是空的,反之亦然?

阿维亚德

否。如果两个条件仍然比第一个while条件还为空,则它们将为真。

在第一个while结束之后,a,b中的至少一个为空。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章