Java使用合併排序對數組進行排序

Question

我想在Java中使用合併排序來對數組進行排序。在這種情況下，數組是numBars。我製作了一個由30個數字組成的小數組，並附加了控制檯的輸出。我跟蹤合併方法，看看爲什麼我會遇到索引問題。我相信我在某個地方的位置是1，但似乎無法弄清楚我的邏輯在哪裏干擾。

public void mergeSort() { 
     mergeSortHelper(numBars, 0); 
     System.out.println(Arrays.toString(numBars)); 
    } 

    public void mergeSortHelper(int[] theArray, int leftIndex) { 

     //split the list in half 
     int mid = theArray.length/2; 
     if (mid < 1) { 
      return; 
     } else { 
      System.out.println("Left Index is originally: " + leftIndex); 
      int[] left = Arrays.copyOfRange(theArray, 0, mid); 
      int[] right = Arrays.copyOfRange(theArray, mid, theArray.length); 
      //sort the lower half 
      mergeSortHelper(left, leftIndex); 
      mergeSortHelper(right, leftIndex + left.length); 
      //merge them together 
      merge(left, right, leftIndex); 
      System.out.println("Left Index is now: " + leftIndex); 
      System.out.println("Right Index is now: " + (leftIndex + mid)); 
      System.out.println(Arrays.toString(numBars)); 
      left = Arrays.copyOfRange(numBars, leftIndex, leftIndex + mid); 
      right = Arrays.copyOfRange(numBars, leftIndex + mid, leftIndex + mid + right.length); 
     } 
    } 

    public void merge(int[]a, int[]b, int leftIndex) { 
     int i = 0; 
     int j = 0; 
     int result = leftIndex; 
     while (i < a.length && j < b.length) { 
      //System.out.println("Comparing from A: " + a[i] + " Comparing from B: " + b[i]); 
      if (a[i] < b[j]) { 
       theCanvas.wait(theDelay); 
       theCanvas.eraseRectangle(graphWidth + i * barWidth, graphHeight - barScale * numBars[i], barScale, barScale * numBars[i]); 
       numBars[result] = a[i]; 
       result++; 
       theCanvas.fillRectangle(graphWidth + i * barWidth, graphHeight - barScale * numBars[i], barScale, barScale * numBars[i]); 
       i++; 
      } else { 
       theCanvas.wait(theDelay); 
       theCanvas.eraseRectangle(graphWidth + j * barWidth, graphHeight - barScale * numBars[j], barScale, barScale * numBars[j]); 
       numBars[result] = b[j]; 
       result++; 
       theCanvas.fillRectangle(graphWidth + j * barWidth, graphHeight - barScale * numBars[j], barScale, barScale * numBars[j]); 
       j++; 

      } 
      //System.out.println("First Loop, Comparing Size" + Arrays.toString(output)); 
     } 
     while (i < a.length) { 
      numBars[result] = a[i]; 
      result++; 
      i++; 
      //System.out.println("Second Loop, Finishing A array" + Arrays.toString(output)); 
     } 

     while(j < b.length) { 
      numBars[result] = b[j]; 
      result++; 
      j++; 
      //System.out.println("Third Loop, Finishing B array" + Arrays.toString(output)); 
     } 
     //System.out.println(Arrays.toString(output)); 
    } 

控制檯輸出：

Left Index is originally: 0 
Left Index is originally: 0 
Left Index is originally: 0 
Left Index is originally: 1 
Left Index is now: 1 
Right Index is now: 2 
[10, 50, 55, 99, 18, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53] 
Left Index is now: 0 
Right Index is now: 1 
[10, 55, 50, 99, 18, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53] 
Left Index is originally: 3 
Left Index is originally: 3 
Left Index is now: 3 
Right Index is now: 4 
[10, 55, 50, 18, 99, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53] 
Left Index is originally: 5 
Left Index is now: 5 
Right Index is now: 6 
[10, 55, 50, 18, 99, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53] 
Left Index is now: 3 
Right Index is now: 5 
[10, 55, 50, 9, 46, 99, 18, 80, 37, 35, 69, 77, 34, 53, 53] 
Left Index is now: 0 
Right Index is now: 3 
[10, 55, 50, 99, 18, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53] 
Left Index is originally: 7 
Left Index is originally: 7 
Left Index is originally: 7 
Left Index is now: 7 
Right Index is now: 8 
[10, 55, 50, 99, 18, 9, 46, 37, 80, 35, 69, 77, 34, 53, 53] 
Left Index is originally: 9 
Left Index is now: 9 
Right Index is now: 10 
[10, 55, 50, 99, 18, 9, 46, 37, 80, 35, 69, 77, 34, 53, 53] 
Left Index is now: 7 
Right Index is now: 9 
[10, 55, 50, 99, 18, 9, 46, 35, 69, 80, 37, 77, 34, 53, 53] 
Left Index is originally: 11 
Left Index is originally: 11 
Left Index is now: 11 
Right Index is now: 12 
[10, 55, 50, 99, 18, 9, 46, 35, 69, 80, 37, 34, 77, 53, 53] 
Left Index is originally: 13 
Left Index is now: 13 
Right Index is now: 14 
[10, 55, 50, 99, 18, 9, 46, 35, 69, 80, 37, 34, 77, 53, 53] 
Left Index is now: 11 
Right Index is now: 13 
[10, 55, 50, 99, 18, 9, 46, 35, 69, 80, 37, 53, 53, 77, 34] 
Left Index is now: 7 
Right Index is now: 11 
[10, 55, 50, 99, 18, 9, 46, 77, 34, 53, 53, 80, 37, 35, 69] 
Left Index is now: 0 
Right Index is now: 7 
[10, 55, 50, 80, 37, 35, 69, 77, 34, 53, 53, 99, 18, 9, 46] 
[10, 55, 50, 80, 37, 35, 69, 77, 34, 53, 53, 99, 18, 9, 46] 

任何幫助將不勝感激！謝謝！

Answer 1

} else { 
    System.out.println("Left Index is originally: " + leftIndex); 
    int[] left = Arrays.copyOfRange(theArray, 0, mid); 
    int[] right = Arrays.copyOfRange(theArray, mid, theArray.length); 
    //sort the lower half 
    mergeSortHelper(left, leftIndex); 
    mergeSortHelper(right, leftIndex + left.length); 
    //merge them together 
    merge(left, right, leftIndex); 
    System.out.println("Left Index is now: " + leftIndex); 
    System.out.println("Right Index is now: " + (leftIndex + mid)); 
    System.out.println(Arrays.toString(numBars)); 
    left = Arrays.copyOfRange(numBars, leftIndex, leftIndex + mid); 
    right = Arrays.copyOfRange(numBars, leftIndex + mid, leftIndex + mid + right.length); 
} 

最後，當您複製numBars值到left和right，那是完全沒有意義的，因爲這些走出去的範圍隨即，將進行垃圾回收。

在調用者中，應該排序的數組保持不變。您需要將合併的值從numBars複製到作爲參數的數組theArray中，以便在調用方合併時合併排序後的數組。

因此，與

for(int i = 0; i < mid; ++i) { 
    theArray[i] = numBars[leftIndex + i]; 
} 
for(int i = mid; i < mid + left.length; ++i) { 
    theArray[i] = numBars[leftIndex + i]; 
} 

替換else塊中的最後兩行復制的合併結果到相同的對象呼叫者通過。

但是，如果您將合併結果作爲參數傳遞給merge的參數傳遞給它，那麼它會導致更簡潔的代碼。