c++ - 快速排序错误 : stack around the variable was corrupted?

Question

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

我收到一个运行时错误，提示“Stack around the variable 'quickArray' was corrupted”

我试过调试器，但仍然无法弄清楚问题出在哪里。我认为这与我的 Partition() 函数有关，但我不确定。谁能帮忙？我在下面发布了 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);
}

Answer 1

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

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 ;

修复方法是从 main 调用 QuickSort，如下所示:

 QuickSort(quickArray,0,9);

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