需要帮助简化我的合并排序实现

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