MergeSort 递归解释

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

想当然的认为当sort(i, j)returns时数组排序在[i..j].

现在 sort(l, q) returns 已排序 array[l..q]，sort(q+1, r) returns 已排序 array[q+1, r]。然后 merge(l, q, r) 将两个已排序的子数组交织在一个子数组中，以便 array[l, r] 变成已排序的（合并两个已排序的数组是一个简单的操作）。

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

注意当 l==r 时，函数 returns 立即执行，因为单个元素的数组是强制排序的。

Answer 2

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

我建议你调试你的程序（或打印你的 sort() 调用的索引），你会看到第一个 merge() 调用只在几次调用 [=36= 之后发生] 并且它只会在已经排序的数组左右被调用。

也可能值得在一些论文上做，这样你就明白了这个概念。

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

MergeSort 递归解释

MergeSort recursion explained

java

algorithm

mergesort