采纳答案成功!
向帮助你的同学说点啥吧!感谢那些助人为乐的人
咦?我还以为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,
mid,
r){
T aux[r-l+1];
// 把我们在这个函数中,要处理的arr[l, r]这段数组中的内容,复制到aux中。
for
(
i = l ; i <= r; i ++ )
aux[i-l] = arr[i];
// 这里为什么要减去l?因为aux是这个函数里面创建的临时空间,索引是从0开始的!
// 关于这个问题,也可以参考这个问答:
// http://coding.imooc.com/learn/questiondetail/3828.html
i = l, j = mid+1;
// i 和 j 就是PPT中两个红色箭头
// k 就是PPT中的拿一个蓝色箭头。
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
( j > r ){
// 如果右半部分元素已经全部处理完毕
// arr[k] 是 aux[i - l]
arr[k] = aux[i-l]; i ++;
( aux[i-l] < aux[j-l] ) {
// 左半部分所指元素 < 右半部分所指元素
{
// 左半部分所指元素 >= 右半部分所指元素
对于整个归并排序的过程,可以参考如下问答:
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
加油!:)
谢谢老师,递归什么的没问题,只是marge里的for循环里的内容想不明白…其他还好
现在呢?觉得还能理解吗?
谢谢老师,基本上理解了。但是在for循环中所有的操作下标都会减L,这个操作没想明白
登录后可查看更多问答,登录/注册
课程专为:短时间内应对面试、升职测评等艰巨任务打造
8.9k 21
5.8k 3
5.0k 5
1.4k 18