實現QuickSort時StackOverflowError

我想在ArrayList上實現QuickSort算法。但是，我得到一個實現QuickSort時StackOverflowError

Exception in thread "main" java.lang.StackOverflowError 
    at sorting.QuickSort.quickSort(QuickSort.java:25) 
    at sorting.QuickSort.quickSort(QuickSort.java:36) 
    at sorting.QuickSort.quickSort(QuickSort.java:36) 
    at sorting.QuickSort.quickSort(QuickSort.java:36) 
    at sorting.QuickSort.quickSort(QuickSort.java:36) 
    ...

我不知道，爲什麼會出現溢出。下面是我的實現：

public static void quickSort(ArrayList<Integer> al, int fromIdx, int toIdx) { 
    int pivot, pivotIdx; 

    if (fromIdx < toIdx) { 
     pivot = al.get(fromIdx); 
     pivotIdx = fromIdx; 

     for (int i = 0; i != (fromIdx + 1); i++) { 
      if (al.get(i) <= pivot) { 
       pivotIdx += 1; 
       swap(al, pivotIdx, i); 
      } 
     } 

     swap(al, fromIdx, pivotIdx); 
     quickSort(al, fromIdx, pivotIdx - 1); 
     quickSort(al, pivotIdx + 1, toIdx); 
    } 
} 

public static void swap(ArrayList<Integer> al, int xIdx, int yIdx) { 
    Integer temp = al.get(xIdx); 
    al.set(xIdx, al.get(yIdx)); 
    al.set(yIdx, temp); 
}

來源

2013-10-27 Jonathan Ong

沒有看你的代碼，這聽起來像是計算遞歸的錯誤索引值。在調試器中運行，並確保你沒有被卡住的索引對絆倒。 – chrylis

它說第36行存在錯誤，但它沒有寫入也沒有寫出主要方法 – iShaalan

調用'quickSort'時'toIdx'的作用是什麼？遞歸排序的索引範圍是什麼？ for循環中'i'的值的範圍是多少？ – rici

如果你想從排序的fromIdx陣列來toIdx塊，你不應該看元素0，除非它在該塊。但是你的實現呢。

你在中間的索引技巧也是種類。我強烈建議您爲陣列裁剪小塊紙張，並在一張紙上寫下跟蹤信息，以便跟蹤算法。如果你在物理上做到這一點，你會發現它沒有任何意義，那麼它在計算機中也沒有任何意義。拿着實際紙張的行爲可能看起來很愚蠢，但對於準確顯示你正在做的事情有很大的幫助。（更精確地說，你可以直觀地看到你的代碼實際上做了什麼，你就越可能弄清楚它是否做錯了。）

來源

2013-10-27 05:46:02 btilly

實現QuickSort時StackOverflowError

回答

相關問題