QuickSort能否堆棧溢出？

在我的代碼中，該方法將自己調用（遞歸）。我們知道，深度方法調用會導致堆棧溢出。那麼，當數據量很大時會發生堆棧溢出嗎？QuickSort能否堆棧溢出？

我的快速排序代碼：（內部類排序類）

private static class QuickSortor extends Sortor { 

    protected <E> void sort(E[] a, boolean isAsc) { 
     quickSort(a, 0, a.length - 1, isAsc); 
    } 

    private <E> void quickSort(E[] a, int left, int right, boolean isAsc) { 
     if (left >= right) 
      return; 
     int middle = left; 
     Comparable<E> cmp = (Comparable<E>) a[left]; 
     for (int i = left + 1; i <= right; i++) { 
      int result = cmp.compareTo(a[i]); 
      if (!isAsc) 
       result = -result; 
      if (result >= 0) 
       swap(a, ++middle, i); 
     } 
     swap(a, left, middle); 
     quickSort(a, left, middle - 1, isAsc); 
     quickSort(a, middle + 1, right, isAsc); 
    } 
}

來源

2012-06-20 King

您是否嘗試過分析堆棧深度複雜性？你會通過這樣做找到答案。 – nhahtdh

這幾乎肯定是無限遞歸。若要在正確的函數中導致堆棧溢出，將需要一個_massive_數組，因此聽起來不太可能。檢查一個錯誤，因爲這可能是原因。 – Oleksi

考慮樞軸（不幸）總是被選爲最小或最大元素的情況。然後你會有一個深度的O（n）調用... – Mysticial

你遞歸有多深，以及快速排序需要多長時間，取決於數據點的相對順序，以及對有多少是。如果樞軸點總是最後成爲數據的最大或最小成員，則您將對上面的代碼進行遞歸，這將隨着數據大小一樣遞增。

使用快速排序，您可以確保遞歸深度很小，即使它仍然需要很長時間。這被如下非常簡要地討論在http://en.wikipedia.org/wiki/Quicksort：

爲了確保至多爲O（log N）空間被使用的，遞歸第一到陣列中較小的一半，並用尾調用遞歸到另一個。

非常簡單，這意味着你是第一個改寫

f(...) 
{ 
    ... 
    f() 
    f() 
}

爲

f() 
{ 
    while (...) 
    { 
    ... 
    f() 
    ... 
} 
}

（使用while循環修改參數f，將第二遞歸調用對應於第二通圍繞while循環）。

然後，您將瞭解如何爲兩次遞歸調用拆分數組，並確保第二次遞歸調用 - 即轉換爲while循環 - 用於數組的較大一半。這意味着剩下的遞歸調用總是不超過數組的一半，這意味着你永遠不會比數組大小的兩個數據庫更深。

來源

2012-06-20 04:00:45 mcdowella

良好的優化建議！如果Java支持尾部呼叫優化，這將更加容易，在這種情況下，您只需按照正確的順序（最後一個）將兩個遞歸調用放在一起，但看起來它[很快就不會發生]（http：/ /stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations）。 –

你寫的算法總是選擇最左邊的元素作爲關鍵點。如果在一個已經排序的數組上執行，這將顯示QuickSort的病態O(n^2)行爲，這將導致堆棧溢出，並有相當小的數組。

你可以通過調用你對Integers的數組從0到15000之類的數字來排序。我得到一個StackOverflowError嘗試它。在15000個隨機Integer的數組上執行它不會導致堆棧溢出。

來源

2012-06-20 04:12:25 jimr

降低發生這種風險的一種常見方法是讀取陣列的第一個，中間和最後一個元素，並從三個元素中選出最好的元素。 –

你錯了，O（n²）是時間複雜度（我們不在乎這裏）而不是棧空間複雜度（在最壞的情況下是O（n））。 – Thomash

我沒有說這是堆棧空間的複雜性，只是病態可以使這個實現有一個小數組溢出溢出。 – jimr

QuickSort能否堆棧溢出？

回答

相關問題