归并排序递归问题

Question

• (void)mergearr:(NSMutableArray*)array left:(int)left right:(int)right{
  if (left >= right) {
  return;
  }
  int center = (left + right)/2;
  [self mergearr:array left:left right:center];
  [self mergearr:array left:center+1 right:right];
  [self megearrSort:array left:left center:center right:right];//合并
  }
  请问老师 [self megearrSort:array left:left center:center right:right];这句代码没有递归为什么会一直合并呢

Answer 1

liuyubobobo 2019-04-28 09:20:08

不是这句代码在一直合并，是mergearr这个递归函数在一值调用这个函数。所以mergearr在不断地被调用，megearrSort就在不断地被调用：）

对于一个小测试数据集，比如8个元素，你先思考一下，megearrSort会被调用几次？为什么？然后，再使用单步跟踪的方式，实际看一下，megearrSort被调用了几次？都是在什么时候被调用的？和你的设想一样不一样？如果不一样，哪里不一样？最初的设想，哪里有问题？

不要怕麻烦，进步就发生在这个过程中哦：）

及亚欧！：）

• 提问者 慕粉1330426222 #1

  老师我一步一步看代码运行过程是这样的（三个元素）执行两次：[self mergearr:array left:left right:center];———》执行一次：[self mergearr:array left:center+1 right:right];———》执行一次：[self megearrSort:array left:left center:center right:right]; ———》方法结束：- (void)mergearr:(NSMutableArray*)array left:(int)left right:(int)right ———》执行一次：[self mergearr:array left:center+1 right:right];———》执行一次：[self megearrSort:array left:left center:center right:right];———》方法结束：- (void)mergearr:(NSMutableArray*)array left:(int)left right:(int)right
  
  我想的是 ：
  1 - (void)mergearr:(NSMutableArray*)array left:(int)left right:(int)right{
  2    if (left >= right) {
  3        return;
  4    }
  5    int center = (left + right)/2;
  6    [self mergearr:array left:left right:center];
  7    [self mergearr:array left:center+1 right:right];
  8    [self megearrSort:array left:left center:center right:right];
  9}
  
  进入第1行后运行到第六行开始递归然后就是1-6的运行代码直到if条件满足结束
  然后第六行结束进入第七行 第七行开始递归1-7的运行代码直到if条件满足结束
  然后第七行结束进入第八行 这样第八行就只会执行一次
  人比较傻 希望老师不要烦 跪求出坑 谢谢老师！！！

• liuyubobobo 回复 提问者 慕粉1330426222 #2

  抱歉，因为评论里没有格式，我看起来太不方便了。我理解你实际跟踪调试的结果和你自己的设想有出入，并且你还有问题？如果是那样的话，请再把这些内容，包括你的详细问题描述放到一个新的问答中，方便我看一下。谢谢：）