关于java归并排序问题

Question

老师你好，我这边用java写到归并排序有个关于递归的问题

关于这段代码，java具体是个什么顺序执行的呢？

以前接触到的递归都是最后一行调用自己的方法，没有接触过这种调用自己本身后面还有操作的情况

具体一点比如，这个行数走到28行之后，是从23行重新开始还是会继续走到30行？

Answer 1

liuyubobobo 2017-06-18 02:19:45

走到28行以后，将调用mergeSort函数，也就是会从23行开始，进入另外一个mergeSort。但是这个mergeSort，和上一个mergeSort不是一个mergeSort，参数不一样！

事实上，递归函数的调用和普通函数的调用是没有区别的。普通函数的调用中，A函数里执行B，B执行完以后将继续执行A。递归函数也是一样的。在A函数里执行A，这个A执行完以后，要返回到上层继续执行上层的A。

如果对这个过程的细节感觉理解的还不透彻，不要只对着代码生想。实际使用一个小数据量的测试用例，比如只包含8个元素的无序数组，然后使用debug一步一步跟着程序走一遍，观察程序在运行每一行代码之后数据和各种辅助的变量具体是怎样变化的，看看和自己的理解是否有偏差。这是非常好的理解算法运行机制的形式。千万不要怕麻烦！踏踏实实拿一张纸一根笔，找一个下午做一遍这个事情，是绝对值得的。

当然了，在程序里加几行输出，能够帮助你更容易地理解这个过程，比如这样：）

private static void sort(Comparable[] arr, int l, int r) {    
    System.out.println("in mergesort, l =" + l + ", r =" + r )
    if (l >= r)    
        return;    
    int mid = (l+r)/2;    
    sort(arr, l, mid);    
    sort(arr, mid + 1, r);    
    merge(arr, l, mid, r);    
}

 

加油！

• 提问者 慕雪2120388 #1

  感谢老师解答