MergeSort算法 - java

Question

我在Java中使用MergeSort實現時遇到問題。我的代碼看起來像這樣，我不知道我犯了什麼錯誤。

public List sort(List list) { 
     return mergesort(list, 0, list.size() - 1); 
    } 

    private List mergesort(List list, int startIndex, int endIndex) { 
     if (startIndex == endIndex) { 
      List temp = new ArrayList(); 
      temp.add(list.get(0)); 
      return temp; 
     } 
     int splitIndex = ((startIndex + endIndex)/2); 
     List list1 = mergesort(list, startIndex, splitIndex); 
     List list2 = mergesort(list, (splitIndex + 1), endIndex); 
     return merge(list1, list2); 
    } 

    private List merge(List left, List right) { 
     List result = new ArrayList(); 
     ListIterator l = new ListIterator(left); 
     ListIterator r = new ListIterator(right); 
     l.first(); 
     r.first(); 
     while (!l.isDone() && !r.isDone()) { 
      if (comparator.compare(l.current(), r.current()) <= 0) { 
       result.add(l.current()); 
       l.next(); 
      } else { 
       result.add(r.current()); 
       r.next(); 
      } 
     } 
     while (!l.isDone()) { 
      result.add(l.current()); 
      l.next(); 
     } 
     while (!r.isDone()) { 
      result.add(r.current()); 
      r.next(); 
     } 
     return result; 

    } 

爲了測試我的算法我用的人名單和排序他們按年齡上升：

0. Jan, Kowalski, 60 
1. Jerzy, Adamczewski, 59 
2. Jan, Kowalski, 48 
3. Adam, Malysz, 40 
4. Bartosz, Tusk, 50 
5. Zygmunt, Jacewicz, 41 

和輸出是這樣的：

0. Adam, Malysz, 40 
1. Adam, Malysz, 40 
2. Adam, Malysz, 40 
3. Adam, Malysz, 40 
4. Adam, Malysz, 40 
5. Adam, Malysz, 40 

Answer 1

此塊不看對。

if (startIndex == endIndex) { 
    List temp = new ArrayList(); 
    temp.add(list.get(0)); 
    return temp; 
} 

也許，你的意思是temp.add(list.get(startIndex));？

Answer 2

似乎你合併函數總是採用相同的最小元素，直到列表爲空。這給我的印象是，您對「ListIterator :: current（）」和「ListIterator :: next（）」的使用存在問題。

我對ListIterators不太熟練，所以我的建議是直接在列表上操作。這也簡化其中的一個用完的元素加入後兩個列表的其餘元素：

private List merge(List left, List right) { 
    List result = new LinkedList(); 

    while (!left.isEmpty() && !right.isEmpty()) { 
     if (comparator.compare(left.get(0), right.get(0)) <= 0) { 
      result.add(left.remove(0)); 
     } else { 
      result.add(right.remove(0)); 
     } 
    } 

    // add what is left in the lists 
    result.addAll(left); 
    result.addAll(right); 

    return result; 
} 

PS：我沒有在我的IDE檢查這個代碼，所以請謹慎使用。理想情況下，你應該有測試準備好檢查你的代碼 - TDD是一個非常好的方法，每個軟件開發人員都應該遵循:)