我想知道这个函数调用本身之后发生了什么,它会恢复还是会继续调用自己直到条件变为假
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
最佳答案
it will keeping calling itself until condition became false
是的,这就是它的工作原理。
该算法采用范围 l
至r
并将其分成两个范围并调用 mergesort
在每个范围内。
示例(为了保持简短,我使用 ms 而不是 mergeSort)
初始系列调用:
ms(a, 0, 8) ---> ms(a, 0, 4) ---> ms(a, 0, 2) ---> ms(a, 0, 1) ---> ms(a, 0, 0)
由于值 0
和0
不满足条件l < r
这样该调用就会返回,并且第二次调用 mergeSort
之前的递归级别将被执行。导致:
ms(a, 0, 8) ---> ms(a, 0, 4) ---> ms(a, 0, 2) ---> ms(a, 0, 1) ---> ms(a, 0, 0)
|
--> ms(a, 1, 1)
再次显示值 1
和1
不满足条件l < r
这样该调用就会在 merge
之后返回我们将返回到之前的递归级别并对 mergeSort
进行第二次调用在那个级别。
ms(a, 0, 8) ---> ms(a, 0, 4) ---> ms(a, 0, 2) ---> ms(a, 0, 1) ---> ms(a, 0, 0)
| |
| --> ms(a, 1, 1)
|
--> ms(a, 2, 2)
2
和2
只是让我们回到之前的递归级别,其中 mergeSort
被称为第二次。我猜你现在看到了这张照片......
ms(a, 0, 8) ---> ms(a, 0, 4) ---> ms(a, 0, 2) ---> ms(a, 0, 1) ---> ms(a, 0, 0)
| | | |
| | | --> ms(a, 1, 1)
| | |
| | --> ms(a, 2, 2)
| |
| --> ms(a, 3, 4) ---> ms(a, 3, 3)
| |
| --> ms(a, 4, 4)
|
--> ms(a, 5, 8) ---> ... finish this your self ...
理解调用序列的另一种方法是添加“递归级别”并在 mergeSort
时执行一些简单的打印。称为:
#include <stdio.h>
void mergeSort(int arr[], int l, int r, int level)
{
printf("Recursion level %d l=%d r=%d\n", level, l, r);
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m, level+1);
mergeSort(arr, m+1, r, level+1);
// merge commented out as it is irrelevant for the call sequence
// merge(arr, l, m, r);
}
}
int main()
{
int a[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
mergeSort(a, 0, 8, 0);
return 0;
}
输出:
Recursion level 0 l=0 r=8
Recursion level 1 l=0 r=4
Recursion level 2 l=0 r=2
Recursion level 3 l=0 r=1
Recursion level 4 l=0 r=0
Recursion level 4 l=1 r=1
Recursion level 3 l=2 r=2
Recursion level 2 l=3 r=4
Recursion level 3 l=3 r=3
Recursion level 3 l=4 r=4
Recursion level 1 l=5 r=8
Recursion level 2 l=5 r=6
Recursion level 3 l=5 r=5
Recursion level 3 l=6 r=6
Recursion level 2 l=7 r=8
Recursion level 3 l=7 r=7
Recursion level 3 l=8 r=8
相同的输出,但具有与级别相关的缩进:
Recursion level 0 l=0 r=8
Recursion level 1 l=0 r=4
Recursion level 2 l=0 r=2
Recursion level 3 l=0 r=1
Recursion level 4 l=0 r=0
Recursion level 4 l=1 r=1
Recursion level 3 l=2 r=2
Recursion level 2 l=3 r=4
Recursion level 3 l=3 r=3
Recursion level 3 l=4 r=4
Recursion level 1 l=5 r=8
Recursion level 2 l=5 r=6
Recursion level 3 l=5 r=5
Recursion level 3 l=6 r=6
Recursion level 2 l=7 r=8
Recursion level 3 l=7 r=7
Recursion level 3 l=8 r=8
关于c - 我想知道它是如何工作的,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51724292/