需要幫助簡化我的合併排序實現

Question

我正在構建一個可擴展ArrayList的類，它擴展了ArrayList。目標是能夠在SortDoubleArray上調用排序方法，並通過所描述的方法對該數組進行排序。我得到了快速排序，插入排序，氣泡排序和選擇排序所有工作，因爲我想要的。不過，我在合併排序時遇到了一些困難。

排序工作，但由於涉及的遞歸工作方式，我強制重置列表的內容是應用於自身的方法。

首先，這裏是測試儀類。它顯示了其他類型如何實施。如果我在解釋我的問題方面做得不好，希望您會看到必須使用mergeSort（）方法的區別。

public class SortTester 
{ 
    /** 
    * @param args 
    */ 
    public static void main(String[] args) 
    { 
     SortDoubleArray list = new SortDoubleArray(); 

     // Code to fill an array with random values. 

     //list.quickSort(); 
     //list.insertionSort(); 
     //list.selectionSort(); 
     //list.bubbleSort(); 
     list = list.mergeSort(); 

     // Code to print the sorted array. 
    } 
} 

接下來，這裏是SortDoubleArray類。所有其他種類，但插入排序（作爲我想要的一個工作的示例）已被刪除，以簡潔起見。

public class SortDoubleArray extends ArrayList<Double> 
{ // Start of class. 
    private static final long serialVersionUID = 1271821028912510404L; 

    /** 
    * Progresses through the elements one at a time inserting them in their proper place 
    * via swaps. 
    */ 
    public void insertionSort() 
    { // Start of insertionSort. 
     int current = 1; 

     while (current < size()) 
     { 
      int i = current; 
      boolean placeFound = false; 

      while(i > 0 && !placeFound) 
      { 
       if (get(i) < get(i - 1)) 
       { 
        double temp = get(i); 
        set(i, get(i - 1)); 
        set(i - 1, temp); 
        i -= 1; 
       } 
       else 
       { 
        placeFound = true; 
       } 
      } 
      current += 1; 
     } 
    } // End of insertionSort. 

    /** 
    * Triggers the recursive mSort method. 
    * @return 
    */ 
    public SortDoubleArray mergeSort() 
    { // start of mergeSort. 
     return mSort(this); 
    } // End of mergeSort. 

    /** 
    * Separates the values each into their own array. 
    */ 
    private SortDoubleArray mSort(SortDoubleArray list) 
    { // Start of mSort. 
     if (list.size() <= 1) 
     { 
      return list; 
     } 

     SortDoubleArray left = new SortDoubleArray(); 
     SortDoubleArray right = new SortDoubleArray(); 

     int middle = list.size()/2; 

     for (int i = 0; i < middle; i += 1) 
     { 
      left.add(list.get(i)); 
     } 

     for (int j = middle; j < list.size(); j += 1) 
     { 
      right.add(list.get(j)); 
     } 

     left = mSort(left); 
     right = mSort(right); 

     return merge(left, right); 
    } // End of mSort. 

    /** 
    * Merges the separated values back together in order. 
    */ 
    private SortDoubleArray merge(SortDoubleArray left, SortDoubleArray right) 
    { // Start of merge. 
     SortDoubleArray result = new SortDoubleArray(); 

     while (left.size() > 0 || right.size() > 0) 
     { 
      if (left.size() > 0 && right.size() > 0) 
      { 
       if (left.get(0) <= right.get(0)) 
       { 
        result.add(left.get(0)); 
        left.remove(0); 
       } 
       else 
       { 
        result.add(right.get(0)); 
        right.remove(0); 
       } 
      } 
      else if (left.size() > 0) 
      { 
       result.add(left.get(0)); 
       left.remove(0); 
      } 
      else if (right.size() > 0) 
      { 
       result.add(right.get(0)); 
       right.remove(0); 
      } 
     } 

     return result; 
    } // End of merge. 
} // End of class. 

請給我我如何可以改變SortDoubleArray類中的歸併（）/ mSort（）函數具有相同的實現爲各種其餘的一些想法。

謝謝！

Answer 1

鑑於mSort和merge方法是正確的，那麼這個怎麼樣？

public void mergeSort() 
{ // start of mergeSort. 
    SortDoubleArray result = mSort(this); 
    clear(); 
    addAll(result); 
} // End of mergeSort. 

在測試中的相關行會則是：

list.mergeSort(); 

祝你好運！

Answer 2

當前您的mergeSort()和merge()函數每個都會創建新的SortedDoubleArray對象。理想情況下，您可以在不創建新陣列的情況下完成所有任務，創建和複製的數量將爲您的算法創造出相當高的性能。

所以你的方法將有原型是這樣的：

private SortDoubleArray mSort(SortDoubleArray list, int startIndex, int length) 

private SortDoubleArray merge(SortDoubleArray list, 
           int leftIndex, int leftlength, 
           int rightIndex, int rightlength) 

然後使用ArrayList.set和.get一個臨時變量做就地調換。這意味着你只能在一個數組上工作而不會創建任何新的不必要的數組。

這有幫助嗎？如果我理解了這個問題，或者需要更多解釋，請告訴我。

注意int endIndex也可以代替工作的int length