3-6 随机快速排序代码debug疑问

Question

老师您好，我使用Java实现随记快速排序时，针对代码的debug执行逻辑有一点疑问，具体如下（可能写的有点多，怕老师不理解我的意思。。）

初始：l = 0，r = 7，数组：Integer[] arr = {5, 1, 9, 4, 2, 8, 6, 7}

第一次递归：l = 0，mid = 3

第二次递归：l = 0，mid = 1

第三次递归：l = 0，mid = 0

这时，进入下面第二个子递归函数，mid+1 = r (mid为0，r为1)，此时退出递归过程进入到第一次merge（arr, 0,0,r），数组前两个元素merge完成，此时debug标记如下：

问题：前两个数组元素merge结束后，这时应该对角标为3和4元素进行merge，但是为什么debug会走到如下图所示呢?又为什么 mid = 1， r = 3呢？因为上一个图的mid = 0, r = 1，逻辑倒是明白，但是此处的两个递归执行有点晕，望老师有空时解答下，谢谢老师~

Answer 1

liuyubobobo 2018-07-19 16:54:57

赞自己调试理解程序逻辑！

我画了一棵递归树帮助你理解：）

              [0, 7]
             /      \
       [0, 3]        [4, 7]
      /     \         /   \
  [0, 1]    [2, 3]   .......
  /    \    /    \
[0]    [1] [2]   [3]

这里，关键可能在于，当一个函数执行完以后，是要返回的，返回到上一次调用他的函数，继续执行！其实递归调用和子函数调用时一致的。在子函数调用中，A调用了B，B之行结束以后，回到A继续执行；在递归调用中，A调用了A，在A执行完成以后，回到上层调用它的A，继续执行：）

具体在这里：

首先l=0, r=7，计算出mid = 3；

-- 第一层递归，调用l=0， r=3， 计算出mid=1；

-- -- 第二层递归，调用l=0， r=1，计算出mid=0；

-- -- -- 第三层递归，调用l=0, r=0，不需要做事情，直接返回！

-- -- 返回到第二层递归，继续执行，下面要递归调用mergeSort(mid+1, r)，也就是l=1, r=1

-- -- -- 第三层递归，调用l=1, r=1，不需要做事情，直接返回！

-- -- 又返回第二层递归，继续执行，下面要调用merge(0, 0, 1)，将0， 1两个元素归并

-- -- 现在，第二层递归终于执行结束啦，返回到哪里？返回到第一层递归调用结束的地方

-- 返回到了第一层递归。你的问题在这里！之前，第一层递归只调用了mergeSort(0, 1)

-- 现在，mergeSort(0, 1)完全执行完了，下面要调用megeSort(mid+1, r)，即mergeSort(2, 3)！

-- 也就是此时，mid = 1, r = 3 这就是你看到debug的信息。但其实，已经在上一层的递归函数中了！

-- -- 进入新的第二层调用，调用l=2, r=3

...... 这个过程继续进行

仔细研究一下上面的过程，看看能不能理解？：）

关键在于：递归调用中，A调用了A，在A执行完成以后，回到上层调用它的A，从中断的地方，继续执行！：）

加油！

• 提问者 我是真的返 #1

  非常感谢！

• 提问者 我是真的返 #2

  根据老师的解答，又仔细debug代码好几次，终于明白了。
  每次递归都会有一个中断点，执行完毕后会返回到中断点，继续执行之后的代码。
  再次感谢老师的解答！！！！

• liuyubobobo 回复 提问者 我是真的返 #3

  大赞！相信你对递归的理解更深刻了：）打个小广告：我的《玩转数据结构》课程，对递归有更细致的讲解（因为目标用户更初级），我的《玩转算法面试课程》，则包含大量递归练习。有兴趣可以参考。关于我的课程学习路径建议，可以参考这里：https://coding.imooc.com/learn/questiondetail/54345.html 加油！：）