歸併上鍊表

我的家庭作業 - 寫在Java中的歸併排序算法。我使用LinkedList來存儲我的數據。我嘗試將wikipedia（http://en.wikipedia.org/wiki/Merge_sort）中的僞代碼轉換爲java，但它不起作用。我不知道爲什麼，我需要你的幫助。歸併上鍊表

這是我的歸併類。

import java.util.Comparator; 

public class MergeSort { 
private final Comparator comparator; 

public MergeSort(Comparator comparator) { 
    this.comparator = comparator; 
} 

public LinkedList sort(LinkedList list) { 
    if(list.size() <= 1) { 
     return list; 
    } 

    LinkedList left = new LinkedList(); 
    LinkedList right = new LinkedList(); 

    int middle = list.size()/2; 
    for(int i = 0; i < middle; i++) { 
     left.add(list.get(i)); 
    } 

    for(int i = list.size(); i >= middle; i--) { 
     right.add(list.get(i)); 
    } 

    left = sort(left); 
    right = sort(right); 

    return merge(left, right); 
} 

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

    while(left.size() > 0 || right.size() > 0) { 
     if(left.size() > 0 && right.size() > 0) { 
      if(comparator.compare(left.get(0), right.get(0)) <= 0) { 
       result.add(left.delete(0)); 
      } 
      else { 
       result.add(right.delete(0)); 
      } 
     } 
     else if(left.size() > 0) { 
      result.add(left.delete(0)); 
     } 
     else if(right.size() > 0) { 
      result.add(right.delete(0)); 
     } 
    } 
    return result; 
}

}

在它是一個「StackOverflowError異常」。我嘗試刪除錯誤，但我不能。謝謝你的幫助。

P.S對不起，我可怕的語言。 :(

來源

2013-04-24 user2316721

我沒有立即看到任何導致堆棧溢出，但值得指出的是，對於一個LinkedList ，獲得大小和得到第i個元素都是「慢」操作（列表長度是線性的）。因此，你的排序算法，如寫入，將最終非常緩慢（即使你修復任何導致堆棧溢出）。到底有多大，你想進行排序？ – 2013-04-24 17:35:24

絕對不實現與linkedlists – durron597 2013-04-24 17:41:30

歸併與陣列運行在2N空間歸併排序名單，但linkedlists你歸併在正運行^ 2的空間，這是一個壞日荷蘭國際集團;如果您不想使用數組/列表列表，則可以使用insertionsort或selectionsort – 2013-04-24 17:42:41

第33行的上排索引需要在列表大小減去一個開始：

 for(int i = list.size()-1; i >= middle; i--) {

來源

2013-04-24 18:07:40 pmorken

回答

相關問題