对于索引合法不太理解，尤其是j>r的情况，为什么要选择aux[i-l]

来源：3-2 归并排序法的实现

Pinesong

2019-06-26

if( i > mid ){ // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j-l]; j ++;
}
else if( j > r ){ // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i-l]; i ++;

写回答

1回答

liuyubobobo

2019-06-27

已采纳

i指向左半部分，j指向右半部分。

如果i > mid，说明i已经到了左半部分的尽头，（左半部分的尽头是mid），所以，不用再管左半部分，只需要把右半部分剩下的元素添加进来就好了，所以我们只处理j就好了；

同理，如果j > r，说明j已经到了右半部分的尽头，（右半部分的尽头是r），所以，不用再管右半部分，只需要把左半部分剩下的元素添加进来就好了，所以我们只处理i就好了；

我不确定你是否对为什么对aux数组，要用i-l或者j-l，而不是i, j 有疑问。对此，可以参考这个问答：http://coding.imooc.com/learn/questiondetail/3828.html

继续加油！：）

Pinesong

非常感谢！

2019-06-27

共1条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11186 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 8

回答 1

回答 2