当对可被7整除的向量大小进行排序时，是否有什么东西会导致快速排序算法出错

Question

我有一个我认为是快速排序算法的东西，它在大约一半的时候产生一个segfault，尽管当对一个大小可以被7整除的向量执行时。它在其他尺寸上似乎正常工作，并产生正确的结果。这是一个正常的情况，还是只是一个错误，我看得太多了。

    /******************************************************************************
 * Function to do the quicksort by recursive call to the substep.
**/
void RecordArray::quicksort()
{
  comparisonsQuick = 0;
  swapsQuick = 0;
  quicksortSubstep(0, recs.size(), comparisonsQuick, swapsQuick);
}
/******************************************************************************
 * Function to do the quicksort.
**/
void RecordArray::quicksortSubstep(int leftBound, int rightBound,
                                   LONG& localComparisons, LONG& localSwaps)
{
  int i = leftBound;
  int j = rightBound;
  OneRecord temp;
  int pivotPoint = (leftBound + rightBound) / 2;
  cout << pivotPoint << endl;
  OneRecord pivot = recs[pivotPoint];;
  while(i <= j)
  {
    while(recs[i] < pivot)
    {
      i++;
      localComparisons++;
    }
    while(recs[j] > pivot)
    {
      j--;
      localComparisons++;
    }
    if(i <= j)
    {
      localComparisons++;
      localSwaps++;
      //cout << localSwaps << " = swaps" << endl;
      temp = recs[i];
      recs[i] = recs[j];
      recs[j] = temp;
      i++;
      j--;
    }
    //cout << localComparisons << " = comparisons" << endl;
  }
  if(leftBound < j)
  {
    //cout << leftBound << " , " << j << endl;
    //cout << "The top one" << endl;
    quicksortSubstep(leftBound, j, localComparisons, localSwaps);
  }
  if(i < rightBound)
  { 
    //cout << i << " , " << rightBound << endl;
    //cout << "The bottom one" << endl;
    quicksortSubstep(i, rightBound, localComparisons, localSwaps);
  }
}

该算法对记录的矢量进行排序，该矢量只是包含4个整数的另一个矢量。我已经重载了Record类中的运算符，当它第一次比较向量中的两个记录时，segfault发生在重载的less than类中。在segfault期间被排序的向量大小是511，它可以被7整除。while循环中正在比较的"rec"的两个值分别为182和225。两者都在0和510之间，我不确定其中一个怎么会为空。"recs[i]"（recs[182]）是在重载lessThan类中查看segfault时导致segfault的原因。

如果时间太长，我很抱歉，我只是想尽可能多地提供我认为有用的信息。下面的lessThan类是由实际的重载类调用的，只是为了使它稍微整洁一些。这在其他向量上进行了尝试，除非大小可以被7整除，否则一切似乎都很好。所有的cout语句都只是用于调试目的。

/******************************************************************************
 * Function 'lessThan' to return a boolean "recA < recB"
 *
 * Parameter:
 *   that - the 'OneRecord' to compare against.
**/
bool OneRecord::lessThan(const OneRecord& that) const
{
  for(unsigned int i = 0; i < theValues.size(); i++)
  {
    if(this->theValues[i] < that.getValues()[i])
    {
      //cout << "if " << this->theValues[i] << " is less than " << that.getValues()[i] << " return true;" << endl;
      return true;
    }
    if(this->theValues[i] > that.getValues()[i])
    {
      //cout << "if " << this->theValues[i] << " is less than " << that.getValues()[i] << " return false;" << endl;
      break;
    }
    if(this->theValues[i] == that.getValues()[i] && i == (theValues.size())-1)
    {
      //cout << "got to the last one";
      //cout << "if " << this->theValues[i] << " is less than " << that.getValues()[i] << " return false;" << endl;
      break;
    }
  }
  return false;
}

Answer 1

在行中：

while(recs[j] > pivot)

CCD_ 1以值CCD_。第一次呼叫中的CCD_ 3是CCD_。

因此，您可以访问recs[recs.size()]，它在recs的数组边界之外，并且是未定义的行为。

我认为您可以在第一次调用中传递recs.size()-1，但我还没有查看您的所有代码。