1

我正在为类实现快速排序功能。我们必须按照她在课堂上用她的伪代码教我们的方式来做，否则我们不会得到学分。

我收到一个运行时错误，显示“变量 'quickArray' 周围的堆栈已损坏”

我玩了调试器，但仍然无法弄清楚问题所在。我认为这与我的 Partition() 函数有关，但我不确定。任何人都可以帮忙吗？Iv 在下面发布了 main()、QuickSort() 和 Partition() 函数。

int main()
{


int quickArray[10] = { 5 ,99, 32, 4, 1, 12, 15 , 8, 13, 55};
int P = quickArray[0];
int R =quickArray[9];

QuickSort(quickArray,P,R);
return 0;

}

..................................................... …………………………………………………………………………………………………………………………………………

void QuickSort(int ar2[],int P, int R)
{
int Q;

if( P < R )
{
    Q =  Partition(ar2,P,R);
    QuickSort(ar2,P,Q-1);
    QuickSort(ar2,Q+1,R);
}

}

..................................................... .........................................................

int Partition(int ar2[],int P, int R)
{
int x = ar2[R];
int i = P-1;
int temp;

for(int j = P; j <= R-1; j++)
{
    if( ar2[j] < x  )
    {
        i = i +1;
        temp = ar2[i];
        ar2[i] = ar2[j];
        ar2[j] = temp;
    }

    temp = ar2[R];
    ar2[R] = ar2[i+1];
    ar2[i+1] = temp;
}

return (i+1);
}
4

3 回答 3

2

您将错误的索引传递给 QuickSort 函数：

int P = quickArray[0];
int R =quickArray[9];

P 和 R 是数组索引，在这种情况下应该是 0 和 9，但是，你将第一个元素和最后一个元素作为索引传递给 QuickSort，55 (quickArray[9]) 超出了 quickArray 的索引范围，所以你得到了错误。

顺便说一句：最好使用描述性变量名称，P 和 R 在这种情况下不能很好地表达它们的含义。您可以使用 left、right 和 pivot 来分别替换 R、R 和 Q，如快速排序算法中所述。

于 2013-03-17T01:39:31.807 回答
2

您传递的是数组的实际元素而不是索引，调试它的一种快速方法是cout在顶部，QuickSort如下所示：

void QuickSort(int ar2[],int P, int R)
{
   std::cout << "P: " << P << " R: " << R << std::endl ;
   ...

以及通话cout后Partition：

  Q =  Partition(ar2,P,R);

  std::cout << "QS: Q= " << Q << std::endl ;

QuickSort解决方法是这样调用main：

 QuickSort(quickArray,0,9);

从长远来看，花一些时间使用调试器将帮助您更快地发现这些错误。

于 2013-03-17T01:42:16.340 回答
0

这

int P = quickArray[0];
int R = quickArray[9];

QuickSort(quickArray,P,R);

应该是这样的：

int arrStartIndex = 0;
int arrEndIndex   = 9;

QuickSort(quickArray, arrStartIndex , arrEndIndex);

正如其他人所指出的，您的代码应该使用更具描述性的名称。

于 2013-03-17T01:41:53.210 回答