快速排序导致堆栈溢出

问题描述：

我已经实现整数数组的快速排序如下：快速排序导致堆栈溢出

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）调用该方法。成千上万的感谢提前！

你正在递归太深。你只有大约1Mb的堆栈空间可用，并且在你使用它之后会出现这个错误。随机数组可能会很快停止递归，因为它会碰到相同的数字。由于您的设置方式，升序/降序会每次执行值的全部深度。这意味着您会深入级别。 – steveg89

您可能想要考虑从递归设计转到迭代设计。我会建议看看这个线程：http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration – MrPaulch

答

您正在经历尾递归。简而言之，C＃编译器并没有对它做很好的工作。我读过如果你在调试时遇到问题，你可以尝试在发布模式下进行优化编译，这样可以缓解这个问题。

还有更详细的信息here。

答

您需要添加停止条件。

function() { 

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

您不能始终致电Quicksort。它需要停止/休息条件。

快速排序导致堆栈溢出

相关推荐