遞歸部分解釋

我被合併排序遞歸部分卡住了。遞歸部分解釋

void divide(int arr[], int low, int high) { 

int mid; 

if(low < high) { 
    mid = (low + high)/2; 
    divide (arr, low, mid); 
    divide (arr, mid+1, high); 
    numbersSort (arr, low, mid, high); 
    } 
}

假設數組大小爲4。第一時，它將由分別divide(arr,0,4)然後divide(arr,0,2)，divide(arr,0,1)，divide(arr,0,0)被調用。但是一說到divide(arr,0,0)就應該停在低位<高位。那麼如何分工和numberSort()函數？

我有另一個查詢問，什麼時候numberSort（）工作？如果你可以通過模擬上面的代碼給我一行一行，我會感激你的。我對此感到非常恐慌。高級謝謝。

來源

2015-10-17 Rana

爲什麼你不能使用調試器來查看代碼的行爲？ –

@rana如上所示，使用調試器。如果您對編碼真的很陌生，並且不知道如何使用它，請先嚐試在每行之後添加打印件。這將有助於您快速瞭解代碼。然後查看GDB手冊或類似的東西來學習調試 – knightrider

http://wiki.codeblocks.org/?title=Debugging_with_Code:Blocks –

示例自頂向下合併排序divide（）函數只是保持調用自身，直到子數組大小減小到1，在這種情況下，可以將大小爲1的子數組視爲排序。只有這樣，纔開始實際的合併，在分割（arr，0,0）和分割（arr，1,1）之後開始，然後不做任何事情。 numbersSort（）然後合併arr [0]和arr [1]，然後返回。下一個合併發生在分割（arr，2,2）和分割（arr，3,3），合併arr [2]和arr [3]之後。然後在返回之後，arr [0 1]和arr [2 3]被合併，產生一個由4個整數組成的有序數組。請注意，所有劃分都會生成索引對（低，高），numbersSort（）是實際合併數據的位置。

一般來說，自頂向下歸併排序是一個深度優先，左先排序。非迭代自底向上合併排序跳過用於生成索引的所有遞歸，並且通過偶數和奇數索引合併開始，將[0]與[1]，[2]和[3]，[4]合併爲[ 5]，...。然後在下一個過程中合併大小爲2的運行，[0 1]與[2 3]，[4 5]與[6 7]合併，等等，直到數組合併爲止。

傳遞與待排序數組大小相同的臨時數組可以用來消除在合併排序期間創建，複製和刪除工作數組。

範例顯示自頂向下的歸併排序操作的順序：操作

7 4 2 5 3 0 6 1 
7 4 2 5|3 0 6 1 
7 4|2 5 
7|4 
4 7 
    2|5 
    2 5 
2 4 5 7 
     3 0|6 1 
     3|0 
     0 3 
      6|1 
      1 6 
     0 1 3 6 
0 1 2 3 4 5 6 7

範例顯示自下而上歸併排序順序：

7 4 2 5 3 0 6 1 
7|4|2|5|3|0|6|1   run size = 0 
4 7|2 5|0 3|1 6   run size = 1 
2 4 5 7|0 1 3 6   run size = 4 
0 1 2 3 4 5 6 7   done

來源

2015-10-17 18:57:21 rcgldr

那麼它是如何分裂和numberSort（）函數的工作？

當您調用另一個函數時，給定函數中的執行不會停止，它只會暫停，直到該函數返回。所以想象你目前正在執行divide(arr,0,1)。 low仍然小於high，所以你輸入條件並致電divide(arr,0,0)，它可以做任何它需要做的事情（提示：儘量不要擔心它現在所做的事情），然後你打電話給divide(arr,1,1)，這又是它的事情，並返回。接下來，你調用numbersSort(arr,0,0,1)，它重新組合了數組的兩部分，結果是該數組從索引0到索引1排序。

好到目前爲止？好吧，接下來你就回來。和它發生的divide(arr,0,1)調用剛纔我們談到是由divide(arr,0,2)調用來調用，所以當divide(arr,0,1)回報的divide(arr,0,2)執行剛剛divide(arr,0,1)後從點繼續進行。所以接下來的事情將是divide(arr,2,2)電話，對吧？ 2不小於2，因此只需立即返回，然後點擊numbersSort(arr,0,1,2)，即將數組的兩部分（即0到1和2到2）組合到一個從0到正確排序的數組中2.現在的陣列從指數0到索引2

但排序，當然，這divide(arr,0,2)被稱爲在divide(arr,0,4)調用的上下文，所以當divide(arr,0,2)返回發生的divide(arr,3,4)接下來的事情。讓我們假設，做正確的事情，從排序索引3索引4的數組，然後你到了numbersSort(arr,0,2,4)，該陣列的兩個部分，並返回結合，任何函數調用divide(arr,0,4)。

絕對可以硬朗首先要解決遞歸你的頭。保持它 - 它會最終點擊。如果您可以在調試器中逐步查看代碼，可以幫助您瞭解發生了什麼。此外，通過紙上的代碼工作可以提供幫助。儘量不要理解它是如何在一個層次上同時運行的，而是要尋找單個層次上發生的事情，並相信調用任何函數（甚至是遞歸調用）只是做正確的事情。

來源

2015-10-17 15:17:57 Caleb

遞歸部分解釋

回答

相關問題