合併排序跟蹤澄清

我在追蹤合併排序的過程中有點困難...... 從概念上講，我明白一個未排序的數組將被分割，直到它的子數組的子數組變成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？

來源

2017-06-30 john lee

跟蹤這個最簡單的方法是用鉛筆和紙。併爲你自己做。

要遵循的規則？是的，當你調用一個函數，然後執行該funstion。（或者你的注意力應該在這個功能中）。

我的意思是： -

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)。這個siuqntially處理不平行，所以除非這個子數組排序，另一部分不被調用。

至於回答你的第二個問題讓我告訴你另一張照片。

[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]

這是在數組上調用mergesort的方式。

而在recusrion中，每個函數調用都有自己的參數。子數組中的父數組中的q作爲p或r。

來源

2017-06-30 06:57:38 coderredoc

合併排序跟蹤澄清

回答

相關問題