3-6 随机快速排序代码debug疑问
来源：3-6 随机化快速排序法
我是真的返
2018-07-19
老师您好，我使用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，逻辑倒是明白，但是此处的两个递归执行有点晕，望老师有空时解答下，谢谢老师~
1回答
-
赞自己调试理解程序逻辑！
我画了一棵递归树帮助你理解：）
[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，从中断的地方，继续执行！：）
加油！
132018-07-20
相似问题