老师，归并算法中这段代码为了得到什么呢？

Question

void __mergeSort(T arr[], int l, int r){

    if( l >= r )

        return;

    int mid = (l+r)/2;

    __mergeSort(arr, l, mid);

    __mergeSort(arr, mid+1, r);

    __merge(arr, l, mid, r);

}

Answer 1

liuyubobobo 2017-08-10 16:37:55

如果用自然语言解释的话，见下面的注释：

// __mergeSort函数将arr数组中l到r位置的所有元素排好序
void __mergeSort(T arr[], int l, int r){
    
    // 如果 l>=r，不需要排序，直接返回
    if( l >= r )
        return;
        
    int mid = (l+r)/2;
    
    // 先将arr数组中l到mid位置的所有元素排好序
    __mergeSort(arr, l, mid); 
    
    // 再将arr数组中mid+1到r位置的所有元素排好序   
    __mergeSort(arr, mid+1, r);  
    
    // 将arr数组中已经排好序的两部分：arr[l...mid]和arr[mid+1...r]合并成一个有序数组
    // 通过__merge，arr[l...r]的所有元素也已经排好序了
    __merge(arr, l, mid, r);     
}

这个过程使用了递归过程。如果对递归理解的不深入，理解这段代码可能确实有难度。

这里要说明一下，首先，这个课程不是针对算法0基础的课程，所以课程中对于诸如“递归”这样的概念没有进行深入阐述。如果第一次接触算法，尤其是对递归理解的不够深入的话，还是建议要结合学校所讲解的基础知识。对这个课程的定位，见这个帖子：http://coding.imooc.com/learn/questiondetail/16248.html

另外，对于算法，不理解的过程千万不要只是看着代码去理解。实际运行一下：）最简单的理解算法的方式，就是使用一个小数据量，一步一步跟踪算法，看看算法在每步运行的过程中，数据实际发生了什么变化，这些变化和你的预期哪里不一样，为什么不一样。自己之前的预期哪里出现了错误。比如对于归并排序，可以使用一个觉有8个数据的数组，甚至只有4个数据的数组一步一步跟踪，查看算法的运转过程。经过这样的过程，不仅会对算法有更深刻的认识，编程能力也会大大提高哦。

加油！：）