1回答

liuyubobobo

2018-11-16

咦？我还以为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

加油！：）

0

8

liuyubobobo

回复

不是谁都叫QB

只有折腾，才能进步：）不过谢谢你的建议，你说得对：）继续加油！：）

2019-01-17

共8条回复