Java中MergeSort實現中的錯誤反轉和重複數字

Question

我正在創建一個Java程序，其中實現了MergeSort算法。我的代碼是下面的（迄今爲止）：

public void merge(Integer [] left, Integer[] right, Integer[] a) { 

    int i = 0;     // a[] index (A) 
    int lIndex = 0;    // left[] index (B) 
    int rIndex = 0;    // right[] index (C) 

    // Begin main merge process 
    while((lIndex < left.length) && (rIndex < right.length)) { 
     if(left[lIndex] <= right[rIndex]) { 
      a[i] = left[lIndex]; // Store it 
      lIndex++; // Increase index of left[] 
     } 
     else { 
      a[i] = right[rIndex]; // Store it 
      rIndex++; // Increase index of right[] 
     } 
     i++; // Increase index of a[] 
    } 
    if(i == lIndex) { // If the left array is sorted 
     while(rIndex < right.length) { // Copy the contents of rhe right array to a[] 
      a[i] = right[rIndex]; 
      i++; 
      rIndex++; 
     } 
    } 
    else { // If the right array is sorted 
     while(lIndex < left.length) { // Copy the contents of the left array to a[] 
      a[i] = left[lIndex]; 
      i++; 
      lIndex++; 
     } 
    } 
} 

的問題是，每一次執行該功能時，輸入數組返回部分排序。我的意思是大多數元素都處於正確的位置，但有一兩個是錯誤的，還有一些是其他元素的重複。由於我看不到真正的問題，誰能幫我嗎？該實現是一個小課程，我不能使用int []（比方說）而不是Integer []，以便使用Arrays.copyOf（）方法複製數組A []的內容。預先感謝，請原諒我的語法/拼寫錯誤。

請注意，輸入數組總是2的冪（2,4,8,16等），所以每次我除以2找到中間元素的索引時，我總是得到一個偶數。

Answer 1

從我所知道的，問題是你的合併方法，在這裏：

if (i == lIndex) { // If the left array is sorted ... 

i不一定等於lIndex當左數組進行排序。結果，合併的最後部分並不總是被執行。您所看到的重複元素在原始數組A中未被覆蓋的位置上因此遺留下來。

正確的條件是：

if (lIndex == left.length) { // If the left array is sorted ... 

Answer 2

我覺得你的問題是在這裏：

if(i == lIndex) 

的方法來檢查，如果你已經用完了在列表中的元素是這樣的：

if (lIndex == left.length) 

換句話說，如果你從左邊和右邊的一些元素，即使你用盡了左ar當你用盡了左邊陣列時，i將不等於lIndex。它會更大。