老师，这个归并算法我死活是理解不了，特别是merge()函数里的操作，想不通，怎么办~~

Answer 1

liuyubobobo 2018-11-16 11:33:08

咦？我还以为mergeSort最难理解，没想到想不通merge：）

首先，我不确定你的水平，这个课程由于设计的定位原因，不是和算法零基础的同学。关于这个课程的定位，可以参考这里：https://coding.imooc.com/learn/questiondetail/16248.html

如果算法根基比较差，可能我的另一门课程《玩转数据结构》会更适合你。《玩转数据结构》从课程设计上，更照顾相对比较基础的同学：）传送门：https://coding.imooc.com/class/207.html

具体的merge过程，完全是课程3-1小节（https://coding.imooc.com/lesson/71.html#mid=1453）从7:30开始的动画过程。请再回顾一下整个动画，思考一下，这个动画所演示的过程，如果让你用代码实现，要怎么实现？在这个基础上，再回顾以下课程代码。我又将这部分所对应的课程代码添加了更多注释，看看你是否可以理解？

// 将arr[l...mid]和arr[mid+1...r]两部分进行归并    
template<typename  T>    
void __merge(T arr[], int l, int mid, int r){    
   
    T aux[r-l+1];  
    
    // 把我们在这个函数中，要处理的arr[l, r]这段数组中的内容，复制到aux中。    
    for( int i = l ; i <= r; i ++ )    
        aux[i-l] = arr[i];  
    // 这里为什么要减去l？因为aux是这个函数里面创建的临时空间，索引是从0开始的！
    // 关于这个问题，也可以参考这个问答：
    // http://coding.imooc.com/learn/questiondetail/3828.html  
   
    int i = l, j = mid+1;  // i 和 j 就是PPT中两个红色箭头
    // k 就是PPT中的拿一个蓝色箭头。  
    for( int k = l ; k <= r; k ++ ){ 
        // 循环中，每次决定arr[k]是谁。
        // arr[k]的值，只能从aux[i - l]和aux[j - l]中选择 
        
        if( i > mid ){  // 如果左半部分元素已经全部处理完毕  
                        // arr[k] 是 aux[j - l]  
            arr[k] = aux[j-l]; j ++;    
        }    
        else if( j > r ){  // 如果右半部分元素已经全部处理完毕  
                           // arr[k] 是 aux[i - l]  
            arr[k] = aux[i-l]; i ++;     
        }    
        else if( aux[i-l] < aux[j-l] ) {  // 左半部分所指元素 < 右半部分所指元素    
                                          // arr[k] 是 aux[i - l]
            arr[k] = aux[i-l]; i ++;      
        }    
        else{  // 左半部分所指元素 >= 右半部分所指元素  
               // arr[k] 是 aux[j - l]  
            arr[k] = aux[j-l]; j ++;     
        }    
    }    
  
}

对于整个归并排序的过程，可以参考如下问答：

https://coding.imooc.com/learn/questiondetail/20335.html

其中，对于归并排序中的递归过程，是理解起来的难点，可以看看这些问答，看是否能够理解：

https://coding.imooc.com/learn/questiondetail/43472.html

https://coding.imooc.com/learn/questiondetail/14346.html

https://coding.imooc.com/learn/questiondetail/12139.html

https://coding.imooc.com/learn/questiondetail/12065.html

加油！：）

• 提问者 三郎_ #1

  谢谢老师，递归什么的没问题，只是marge里的for循环里的内容想不明白…其他还好

• liuyubobobo 回复 提问者 三郎_ #2

  现在呢？觉得还能理解吗？

• 提问者 三郎_ #3

  谢谢老师，基本上理解了。但是在for循环中所有的操作下标都会减L，这个操作没想明白

点开查看后面5条评论