Quicksort與Arraylist故障排除的Java實現

我試圖用ArrayList實現quicksort算法，但似乎無法得到這個工作。它給我在sort（）函數中遞歸返回錯誤。請幫忙！Quicksort與Arraylist故障排除的Java實現

這是我的錯誤：在線程異常「主要」 java.lang.StackOverflowError的

public static void main(String[] args) { 

    List<Integer> l = new ArrayList<Integer>(); 
    l.add(10); l.add(7); l.add(13); l.add(22); l.add(9); 
    //l.get(2); 


    System.out.println(sort(l)); 


} 


public static List<Integer> sort(List<Integer> l) { 

    if (l.size() <= 1) { 
     return l; 
    } 

    int pivot = l.get(0); 
    List<Integer> left = new ArrayList<Integer>(); 
    List<Integer> right = new ArrayList<Integer>(); 

    for (int i = 0; i < l.size(); i++) { 
     if (l.get(i) < pivot) { 
      left.add(l.get(i)); 
      //System.out.println(left); 
     } else { 
      right.add(l.get(i)); 
     } 

    } 
    return join(sort(left), sort(right), pivot); 
} 

public static List<Integer> join(List<Integer> left, List<Integer> right, int pivot) { 

    List<Integer> l = new ArrayList<Integer>(); 

    for (int i = 0; i < left.size(); i++) { 
     l.add(left.get(i)); 
    } 

    l.add(pivot); 

    for (int i = l.size(); i < right.size(); i++) { 
     l.add(right.get(i)); 
    } 
    return l; 
}

}

來源

2014-02-09 rohstar

它給你什麼錯誤？ –

@CraigOtis線程「main」中的異常java.lang.StackOverflowError – rohstar

我認爲這是學習使用調試器的好機會！ –

這個問題可能是在這裏：

你選擇你的支點爲：

l.get(0);

然後再次添加您的數據透視表：

int i = 0; i < l.size(); i++

從零開始！

所以將其更改爲從1開始：

int i = 1; i < l.size(); i++

編輯： 另一個錯誤是在你的join()方法 - 你必須從0開始兩個的ArrayList：

for (int i = 0; i < right.size(); i++) { 
     l.add(right.get(i)); 
}

來源

2014-02-09 21:14:37

或者，在分配數據透視表時使用'l.remove（0）'，並讓循環獨立。（除非你不想改變提供的'List'。） –

我把計數器改爲1，結果我得到[7,10] – rohstar

@CraigOtis我不認爲這是更好的解決方案，因爲remove（）可能會有第一個元素的O（n）複雜性。 –

考慮一下如果你選擇最小的元素作爲你的支點，就會發生。兩個子列表中的一個將是空的，另一個將包含整個原始列表，導致無限遞歸。

來源

2014-02-09 21:16:23 NPE

Quicksort與Arraylist故障排除的Java實現

回答

相關問題