快速排序導致堆棧溢出

我已經實現整數數組的快速排序如下：快速排序導致堆棧溢出

public void Quicksort(int left, int right) 
{ 
    /* The recursive quicksort algorithm consists of four steps: 
    * 1. If there are one or less elements in the array to be sorted, return immediately. 
    * 2. Pick an element in the array to serve as a "pivot" point. (Usually the left-most element in the array is used.) 
    * 3. Split the array into two parts - one with elements larger than the pivot and the other with elements smaller than the pivot. 
    * 4. Recursively repeat the algorithm for both halves of the original array. 
    */ 

    int pivot = dataTable[left]; 

    int l_hold = left; 
    int r_hold = right; 

    while (left < right) 
    { 
     while ((dataTable[right] >= pivot) && (left < right)) 
      right--; 

     if (left != right) 
     { 
      dataTable[left] = dataTable[right]; 
      left++; 
     } 

     while ((dataTable[left] <= pivot) && (left < right)) 
      left++; 

     if (left != right) 
     { 
      dataTable[right] = dataTable[left]; 
      right--; 
     } 
    } 

    dataTable[left] = pivot; 
    pivot = left; 
    left = l_hold; 
    right = r_hold; 

    if (left < pivot) 
     Quicksort(left, pivot - 1); 

    if (right > pivot) 
     Quicksort(pivot + 1, right); 
}

它運行與沒關係的，比方說，500個000隨機產生的整數的數組。如果我用升序或降序整數填充數組，Quicksort會在大約8800個元素處導致StackOverflowException。

我用我的小眼睛間諜沒有明確的理由。你可以用大量的眼睛探查一個原因嗎？我可以去找到正在運行的quicksort的副本，但我寧願找到造成問題的原因。

該方法對作爲類的一部分的數組起作用，通常用（索引0，最後一個索引-1）調用該方法。成千上萬的感謝提前！

來源

2013-12-13 JKase

你正在遞歸太深。你只有大約1Mb的堆棧空間可用，並且在你使用它之後會出現這個錯誤。隨機數組可能會很快停止遞歸，因爲它會碰到相同的數字。由於您的設置方式，升序/降序會每次執行值的全部深度。這意味着您會深入級別。 – steveg89

您可能想要考慮從遞歸設計轉到迭代設計。我會建議看看這個線程：http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration – MrPaulch

您正在經歷尾遞歸。簡而言之，C＃編譯器並沒有對它做很好的工作。我讀過如果你在調試時遇到問題，你可以嘗試在發佈模式下進行優化編譯，這樣可以緩解這個問題。

還有更詳細的信息here。

來源

2013-12-13 18:13:14

您需要添加停止條件。

function() { 

if(value == 0) { 
break; 
} else { 
function()) 
}

您不能始終致電Quicksort。它需要停止/休息條件。

來源

2013-12-13 19:14:32 iefpw

快速排序導致堆棧溢出

回答

相關問題