遞歸自頂向下mergesort

我想讓我的頭圍繞歸併排序算法的一部分的遞歸排序函數。這是我的代碼，我幾乎可以肯定是正確的（在線課程之後）。遞歸自頂向下mergesort

private static void sort(Comparable[] a, Comparable[] aux, int low, int high) { 
     if (high <= low) return; 
     int mid = low + (high - low)/2; 
     sort (a, aux, low, mid); 
     sort (a, aux, mid+1, high); 
     merge(a, aux, low, mid, high); 
    }

我明白歸併does-它打破每個子陣列分解成2級較小的子陣列，重複該直到子陣列是一個長度（根據定義排序），然後合併。然而，這種排序函數用來實現這個功能的實際方法很難讓我遵循。也許是因爲我不習慣遞歸函數，但是我想知道是否有人能夠說明操作的順序以及第一次合併時的參數。

例如，當它遇到FIRST遞歸調用來排序（a，aux，low，mid）時 - 它是否中斷操作，而不是繼續執行第二個排序和下面的合併函數，而不是立即調用sort新參數？在這種情況下，當第二個電話進行排序時，排序（a，aux，mid + 1，high）;發生？

感謝您的任何幫助。這是我第一次在這裏發佈，如果有任何格式問題，請讓我知道。

來源

2017-01-27 Lyle

當它進行FIRST遞歸調用以排序（a，aux，low，mid）時 - 是否會中斷操作，而不是繼續執行第二個排序和下面的合併函數，而不是立即調用新的排序參數？

是的。它會再次調用該函數（遞歸），然後繼續下去，直到它對該部分進行排序。

何時，在這種情況下，第二次調用將進行排序;排序（a，aux，mid + 1，high）;發生？

第一次調用完成後執行。（當第一部分完成分類時）。

來源

2017-01-27 13:20:56

評論解釋的情況下，每一步你沒有得到任何：

if (high <= low) return; // if your high and low numbers are the same then this part of the loop is finished and it will start going back up 
int mid = low + (high - low)/2;//sets mid 
sort (a, aux, low, mid);//recursively calls itself so that it will eventually hit the first if. This handles from low to mid 
sort (a, aux, mid+1, high); //this handles from mid+1 to high 
merge(a, aux, low, mid, high); //This is where the merge starts.

我覺得它有助於運行一個簡單的例子，通過它在筆和紙運行，如果你真的有困難時期。

來源

2017-01-27 13:31:32

遞歸自頂向下mergesort

回答

相關問題