递归到底条件

Question

void __mergeSort(T arr[], int l, int r) {
if (l >= r)
return;
}
这里面if的条件我没理解；
l<=r时还有两个元素要排序也没懂；

Answer 1

liuyubobobo 2021-04-04 03:36:49

__mergeSort 处理的数组区间是 arr[l, r]，这个区间是前闭后比的。

l >= r，说明这个区间里最多只有一个元素。

如果 l == r，比如 arr[3, 3]，这个区间里只有 arr[3] 这一个元素，一个元素的数组肯定自己就是有序的，不需要排序，直接返回；

如果 l > r，比如 arr[4, 3]，这个区间左边界比右边界还大，所以里面不包含任何元素（没有一个 i 满足 i >= 4 并且 i <= 3），一个空区间也不需要排序，直接返回。

继续加油！：）

• 提问者 BSJ_dong2020 #1

  此问题我懂了，谢谢您！

• ych_1997 #2

  老师，我看了您的回答还是有点疑惑。l 为左边界，r为右边界。答案中“如果 l == r，比如 arr[3, 3]”，描述“相等”使用了具体元素的值，而课程的代码中体现的应该是元素的下标大小，针对这个提问是不是还有更好的解释呢？

• ych_1997 #3

  我已经想明白这个边界问题了！老师您看看我是否有一个合理的思考过程！。首先，l 为左边界，r为右边界。l和r就是数组的下标。【1】当数组中有2个元素时，下标是0，1。此时l == mid == 0;  r == 1;   则__mergeSort(arr, 0, 0); __mergeSort(arr, 1, 1); 两路依次到达递归终点，则要求。 l == r。【2】当数组中只有1个元素时，下标 l == r == mid == 0; 则__mergeSort(arr, 0, 0);   __mergeSort(arr, 1, 0);  两路依次到达递归终点，则要求l >= r；【3】综上，l >= r即可让两种边界情况到达递归终点。

点开查看后面3条评论