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是一个非常好的方法，每个软件开发人员都应该遵循:)