合并排序跟踪说明

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,q+1,r) mergeSort(A,p,q)。这个 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.

合并排序跟踪说明

Merge Sort tracing clarification

java

arrays

sorting

algorithm

mergesort