這個特定的合併排序程序是如何工作的？

我在學習排序算法。我已經完成了以下鏈接中的程序。爲了簡單起見，我附加了鏈接和程序本身。這個特定的合併排序程序是如何工作的？

public class Mergesort { 
private int[] numbers; 
private int[] helper; 
private int number; 

public void sort(int[] values) { 
    this.numbers = values; 
    number = values.length; 
    this.helper = new int[number]; 
    mergesort(0, number - 1); 
} 

private void mergesort(int low, int high) { 
    if (low < high) { 
    int middle = low + (high - low)/2; 
    mergesort(low, middle); 
    mergesort(middle + 1, high); 
    merge(low, middle, high); 
    } 
} 

private void merge(int low, int middle, int high) { 
    for (int i = low; i <= high; i++) { 
     helper[i] = numbers[i]; 
    } 
    int i = low; 
    int j = middle + 1; 
    int k = low; 
    while (i <= middle && j <= high) { 
     if (helper[i] <= helper[j]) { 
      numbers[k] = helper[i]; 
      i++; 
     } else { 
      numbers[k] = helper[j]; 
      j++; 
     } 
     k++; 
    } 
    while (i <= middle) { 
     numbers[k] = helper[i]; 
     k++; 
     i++; 
    } 
}

}

我沒有收到在合併方法的原因包括這最後的一段時間（我< =中部）的任何線索。意味着（j < =高）也存在，但這種情況被忽略。我得到這個程序的鏈接是http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html

對不起，我的壞解釋。希望有人能向我解釋。

來源

2016-12-05 S.kalya

它工作嗎？你有沒有嘗試桌面檢查或調試？ – GurV

是的，它正在工作併產生預期的產出。 –

線索實際上是引用的文章：

  // Copy the rest of the left side of the array into the target array 
      while (i <= middle) { 
        numbers[k] = helper[i]; 
        k++; 
        i++; 
      }

考慮的情況下，上半年的數字均大於下半年的數字更大。然後在第一個while週期中，您只會增加j，您不會複製上半年的任何數字。第二個while週期從上半年複製剩餘的數字。

一個很好的問題是爲什麼你實際上不需要從下半部分複製剩餘的數字。我會留給你的。 :)

來源

2016-12-05 11:29:14 lexicore

是的，更好的問題是爲什麼我們不需要複製下半部分的數字。我得到了我的答案。非常感謝:) –

@ S.kalya - 從後半部分開始的數字是不需要的，因爲在合併之前複製到臨時數組，並且合併從臨時數組合併到原始數組。如果合併排序更有效且交替地根據遞歸級別在原始和臨時緩衝區之間合併方向，則將不存在複製步驟，並且合併將需要複製來自第一或第二半的任何剩餘數字。在運行大小== 1並從原始合併到臨時的特定情況下，它需要複製1個元素。 – rcgldr

這個特定的合併排序程序是如何工作的？

回答

相關問題