java - 合并排序跟踪说明

Question

我在跟踪归并排序过程时遇到了一点困难... 从概念上理解，一个未排序的数组会被划分，直到它的子数组的子数组的长度变为1，其中它变成一个每个包含1个元素的数组，这就是说排序。 使用

 mergeSort(A,p,r) //where p = lowest index, r = highest
     if (p < r) {
         q = (p+r) / 2
         mergeSort(A,p,q)
         mergeSort(A,q+1,r)
         merge(A,p,q,r) 
     }

在一个未排序的数组 [3, 5, 2, 1, 6, 4] 上，其中 p 是元素 3 的索引，q 是元素 2 的索引，r 是元素 4 的索引。根据我的理解, 由于调用了 mergeSort(A,p,q)，它首先会被分成 [3, 5, 2]；现在新索引将是元素 3 的 p，元素 5 的 q，元素 2 的 r；所以 [3, 5, 2] 将被划分为 [3, 5]，其中 p 和 q 是元素 3 的索引，r 是元素 5 的索引；将分为[3]。我的问题是，[2](来自除法后的 [3, 5, 2])是否被索引为 p 或 q+1？

....其实，我觉得我的问题不够清楚，所以换一种方式问， 因为 [3, 5, 2, 1, 6, 4] 将分为 [3, 5, 2] 和 [1, 6, 4]；将分为 [3, 5] 和 [2] ； [1, 6] 和 [4]；也将分为 [3] [5] 和 [1] [6]；划分的哪一部分调用 mergeSort(A,p,q)，划分的哪一部分调用 mergeSort(A,q+1,r)？ [1, 6, 4] 在元素 1 也索引为 p，在元素 4 索引为 r？

Answer 1

最简单的追踪方法是拿笔和纸。为自己做。

有什么规律可循？是的，当您调用一个函数时，该函数就会被执行。 (或者你的注意力应该在那个功能上)。

我的意思是:-

mergesort([3, 5, 2, 1, 6, 4]) 你调用了。

然后最终你面对这条线

     q = (p+r) / 2
     mergeSort(A,p,q)   [3,5,2] <------
     mergeSort(A,q+1,r) [1,6,4]
     merge(A,p,q,r) 

现在你的注意力应该在 mergesort( [3,5,2] )

这样你就可以继续了。在某个时刻，您将到达这条线。

     q = (p+r) / 2
     mergeSort(A,p,q)   [2,3,5] // this is sorted now
     mergeSort(A,q+1,r) [1,6,4] <--------
     merge(A,p,q,r)

然后继续这样。这样，您将在某一时刻调用 merge，它将排序的子数组合并到完整的排序数组中。

• 在排序 mergeSort(A,p,q) 时，不要打扰自己 mergeSort(A,q+1,r)。此 si seuqntially 处理不是并行的，因此除非此子数组已排序，否则不会调用其他部分。

---

为了回答你的第二个问题，让我给你看另一张照片。

 [3, 5, 2, 1, 6, 4]
  p     q        r
       /\
[3,5,2]  [1, 6, 4]
 p q r    p  q  r
  |   \       |    \ 
[3,5] [2]  [1, 6]  [4]
 p r        p  r
 q          q
 /  \        |\
[3] [5]     [1] [6]

这是对数组调用合并排序的方式。

在回溯中，每个函数调用都有自己的参数。在父数组中充当 q 的子数组将充当 p 或 r。