合并排序递归解释

Question

我知道这个问题已经被问了很多，有很多有用的和好的答案，但我有一个关于递归的具体问题。当我们多次递归调用sort时，到底发生了什么?例如:int[] intArr = {16, 12, 9, 3, 19};当我们把这个数组分成两部分或者用两个下标看它时，merge()对这两个未排序的部分做了什么?我的意思是在第一次迭代中前两半是无序的，对吧?该方法应按当前顺序到达merge():merge({16, 12}, {9, 3, 19})

public static int[] sort(int l, int r) { 

if (l < r) { 
int q = (l + r) / 2; 

sort(l, q); 
sort(q + 1, r); 
merge(l, q, r); 
} 
return intArr; 
} 

我不知道问题是什么，但我不完全理解归并排序背后的递归。有一个基本的理解，但是merge()方法使我很难理解。

Answer 1

当您为intArr = {16, 12, 9, 3, 19}调用sort(0, 4)时，您将再次调用sort(0, 2)，然后是sort(0, 1)，最后是sort(0, 0)。当您达到l < r将不再为真，您将返回未更改的数组作为一个元素的数组16已经排序。所以我们回到对sort(0,1)的调用，所以下一件事是对sort(1,1)的调用，其中l < r将不再为真，并且您将返回未更改的数组，因为12是单个元素，因此已经排序。只有这样，您才能到达第一个merge(0, 1)调用，它将获取{16, 12, 9, 3, 19}并将所有值从0到1排序，因此结果将是(假设升序){12, 16, 9, 3, 19}。注意，我们调用merge(0, 1)时使用的是q左右的两个排序数组。然后，我们已经完成了sort(0, 1)调用，并返回到之前的sort(0, 2)调用，现在有一个对sort(2, 2)的调用。这将返回数组不变，因为l < r不再为真，我们将带着数组{12, 16, 9, 3, 19}移动到merge(0, 2)。调用的结果将是{9, 12, 16, 3, 19}，我们已经完成了sort(0, 2)，并移动到sort(0, 4)，等等。

我建议您通过程序进行调试(或打印sort()调用的索引)，您将看到第一个merge()调用只发生在对sort()的几个调用之后，并且它只会被调用已经排序的数组左和右。

也值得在纸上做一下，这样你就能理解这个概念了。

16 12 9 3 19    Sort(0, 4)
16 12 9 | 3 19  Sort(0, 2)
16 12 | 9 3 19  Sort(0, 1)
16 | 12 9 3 19  Sort(0, 0)
^sorted 
16 | 12 9 3 19  Sort(1, 1)
^sorted 
12 16 | 9 3 19  Merge(0, 1)
^sorted
12 16 | 9 3 19  Sort(2, 2)
^sorted
9 12 16 | 3 19  Merge(0, 2)
^sorted
9 12 16 | 3 19  Sort(3, 4)
9 12 16 3 | 19  Sort(3, 3)
^sorted
9 12 16 3 | 19  Sort(4, 4)
^sorted
9 12 16 | 3 19  Merge(3, 4)
^sorted
3 9 12 16 19    Merge(0, 4)
all sorted          

Answer 2

假定当sort(i, j)返回时，数组按[i..j]排序。

现在sort(l, q)返回array[l..q]排序，sort(q+1, r)返回array[q+1, r]排序。然后，merge(l, q, r)将两个排序的子数组交织成一个，这样array[l, r]就排序了(合并两个排序的数组是一个简单的操作)。

因此，归并排序对越来越大的数组进行排序。

注意，当l==r时，函数立即返回，因为只有一个元素的数组是强制排序的。