合併排序列表java

Question

此代碼的輸出始終是輸入的最後一位數字。 找不到原因。我使用遞歸合併排序，結果是錯誤的。我想也許這個名單被重疊。

public class MergeSort { 
    public static List<Integer> Sort(List<Integer> list) { 
     if (list.size() <= 1) { 
      return list; 
     } 
     List<Integer> aList = new ArrayList<Integer>(); 
     aList = list.subList(0, list.size()/2); 

     List<Integer> bList = new ArrayList<Integer>(); 
     bList = list.subList(list.size()/2, list.size()); 

     Sort(aList); 
     Sort(bList); 

     merge(aList, bList, list); 
     return list; 
    } 

    private static List<Integer> merge(List<Integer> alist, 
     List<Integer> blist, List<Integer> list) { 
     int alistIndex = 0, blistIndex = 0, listIndex = 0; 
     while (alistIndex < alist.size() && blistIndex < blist.size()) { 
      if (alist.get(alistIndex) < blist.get(blistIndex)) { 
       list.set(listIndex, alist.get(alistIndex)); 
       alistIndex++; 
      } else { 
       list.set(listIndex, blist.get(blistIndex)); 
       blistIndex++; 
      } 
      listIndex++; 
     } 
     List<Integer> rest; 
     if (alistIndex == alist.size()) { 
      rest = blist.subList(blistIndex, blist.size()); 
      for(int c = blistIndex; c < rest.size(); c++){ 
       list.set(listIndex, blist.get(c)); 
       listIndex++; 
      } 
     } else { 
      rest = alist.subList(alistIndex, alist.size()); 
      for(int c = alistIndex; c < rest.size(); c++){ 
       list.set(listIndex, alist.get(c)); 
       listIndex++; 
      } 
     } 
     return list; 
    } 
} 

測試輸入是5,4，3，2，1。 但輸出爲1，1，1，1，1 因此，必須有一些錯這個合併方法

Answer 1

的快速解決您的問題正在取代：

List<Integer> aList = new ArrayList<Integer>(); 
aList = list.subList(0, list.size()/2); 

List<Integer> bList = new ArrayList<Integer>(); 
bList = list.subList(list.size()/2, list.size()); 

有：

List<Integer> aList = new ArrayList<Integer>(list.subList(0, list.size()/2)); 
List<Integer> bList = new ArrayList<Integer>(list.subList(list.size()/2, list.size())); 

您爲您的分區上創建新ArrayList當時的立即改變對原始列表視圖的引用。

---

列表的分區被正確，做，但是因爲你正在使用的視圖，而不是淺拷貝，你改變你的分區合併過程中。在最初的名單是不是

public class MergeSort { 
    public static void sort(List<Integer> list) { 
    if (list.size() < 2) { 
     return; 
    } 
    int mid = list.size()/2; 
    List<Integer> left = new ArrayList<Integer>(list.subList(0, mid)); 
    List<Integer> right = new ArrayList<Integer>(mid, list.size())); 

    sort(left); 
    sort(right); 
    merge(left, right, list); 
    } 

    private static void merge(
     List<Integer> left, List<Integer> right, List<Integer> list) { 
    int leftIndex = 0; 
    int rightIndex = 0; 
    int listIndex = 0; 

    while (leftIndex < left.size() && rightIndex < right.size()) { 
     if (left.get(leftIndex) < right.get(rightIndex)) { 
     list.set(listIndex++, left.get(leftIndex++)); 
     } else { 
     list.set(listIndex++, right.get(rightIndex++)); 
     } 
    } 
    while (leftIndex < left.size()) { 
     list.set(listIndex++, left.get(leftIndex++)); 
    } 
    while (rightIndex < right.size()) { 
     list.set(listIndex++, right.get(rightIndex++)); 
    } 
    } 
} 

---

另一種選擇：

通常，如果你正在做那種變異原始列表，你不從該方法返回任何東西，所以像突變可能是：

public class MergeSort { 
    public static List<Integer> sorted(List<Integer> list) { 
    if (list.size() < 2) { 
     return list; 
    } 
    int mid = list.size()/2; 
    return merged(
     sorted(list.subList(0, mid)), 
     sorted(list.subList(mid, list.size()))); 
    } 

    private static List<Integer> merged(List<Integer> left, List<Integer> right) { 
    int leftIndex = 0; 
    int rightIndex = 0; 
    List<Integer> merged = new ArrayList<Integer>(); 

    while (leftIndex < left.size() && rightIndex < right.size()) { 
     if (left.get(leftIndex) < right.get(rightIndex)) { 
     merged.add(left.get(leftIndex++)); 
     } else { 
     merged.add(right.get(rightIndex++)); 
     } 
    } 
    merged.addAll(left.subList(leftIndex, left.size())); 
    merged.addAll(right.subList(rightIndex, right.size())); 
    return merged; 
    } 
} 

Answer 2

subList方法從原始方法創建一個新列表，但仍保留對原始元素的引用，以便在第一個元素中進行的任何更改都會影響第二個元素，反之亦然。 在您的合併方法中，您將覆蓋原始列表，並同時更改子列表中未通過if條件的更大元素。請參考this post更多信息，對此事