無效合併排序方法java

Question

所以，我的計算機科學老師告訴我，除了copyPartArray之外，這裏的每個方法都是無效的。我不知道如何做到這一點，當我嘗試時，排序完全失敗。

public static ArrayList<String> mergeSortHelper(ArrayList<String> a) { 
    int mid = a.size()/2 - 1; 
    if (a.size() <= 1) 
     return a; 
    return merge(mergeSortHelper(copyPartArray(a, 0, mid)), 
      mergeSortHelper(copyPartArray(a, mid + 1, a.size() - 1))); 
} 

public static void mergeSort(ArrayList<String> a) { 
    ArrayList<String> x = mergeSortHelper(a); 
    for (int i = 0; i < a.size(); i++) { 
     a.set(i, x.get(i)); 
    } 
} 
    public static ArrayList<String> merge(ArrayList<String> a, 
     ArrayList<String> b) { 
    ArrayList<String> x = new ArrayList<String>(a.size() + b.size()); 
    int aCount = 0; 
    int bCount = 0; 
    for (int i = 0; i < a.size() + b.size(); i++) { 
     if (aCount > a.size() - 1) { 
      for (int j = bCount; j < b.size(); j++) { 
       x.add(b.get(j)); 
      } 
      break; 
     } 
     if (bCount > b.size() - 1) { 
      for (int j = aCount; j < a.size(); j++) { 
       x.add(a.get(j)); 
      } 
      break; 
     } 
     if ((a.get(aCount)).compareTo(b.get(bCount)) < 0) { 
      x.add(a.get(aCount)); 
      aCount++; 
     } else { 
      x.add(b.get(bCount)); 
      bCount++; 
     } 
    } 
    return x; 
} 

    public static ArrayList<String> copyPartArray(ArrayList<String> a, int s, 
     int e) { 
    ArrayList<String> x = new ArrayList<String>(); 
    for (int i = s; i <= e; i++) { 
     x.add(a.get(i)); 
    } 
    return x; 

我已經試過我的歸併更改爲：

public static void mergeSort(ArrayList<String> a) { 
    int mid = a.size()/2 - 1; 
    if (a.size() <= 1) 
     return; 
    mergeSort(copyPartArray(a, 0, mid)); 
    mergeSort(copyPartArray(a, mid + 1, a.size() - 1)); 
    merge(a, copyPartArray(a, 0, mid), 
      copyPartArray(a, mid + 1, a.size() - 1)); 
} 

和擺脫mergeSortHelper的一起。

現在我有：

public static void mergeSort(ArrayList<String> a, int start, int end) { 
    int mid = (start + end)/2; 
    if (a.size() <= 1) 
     return; 
    mergeSort(a, start, mid); 
    mergeSort(a, mid + 1, end); 

我如何將納入我的合併方法到這一點？

Answer 1

copyPartArray將要製作數組的副本，因此這是不好的，您的講師希望您通過引用傳遞數組，然後還傳遞開始/結束（或開始/長度）整數。試着做這樣的事情：

public static void mergeSort(ArrayList<String> a, int start, int length) { 
    // refer to 'the array' as a[start] to a[start + length] 
} 

a將參照這意味着你不需要一個返回值進行傳遞。

所以我會改變你的方法，採取一個start和length並擺脫copyPartArray所有在一起，你可以做一個陣列就地合併。我使用my blog post on Quicksort這個方法。