c++ - 在将 vector 大小除以7时，是否有某些东西会导致快速排序算法出现段错误？

我有一个快速排序算法，当对一个大小可被7整除的向量执行时，它会在大约一半的时间内产生一个segfault。它似乎在其他尺寸上正常工作，并产生正确的结果。这是正常现象还是只是我看过头了的一个错误。

    /******************************************************************************
 * 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类中的运算符，当segfult第一次比较向量中的两个记录时，它出现在重载的小于类中在segfault期间被排序的向量大小是511，它可以被7整除。while循环中正在比较的“recs”的两个值分别为182和225。两者都在0和510之内，我不确定其中一个怎么可能为空“recs[i]”（recs[182]）是在重载的lessthan类中查看segfult时导致它的原因。
抱歉，如果时间太长，只想尽量提供我认为有用的信息。下面的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;
}

最佳答案

在这一行中：

while(recs[j] > pivot)

j从值rightBound开始。rightBound在第一个调用中是recs.size()。
因此，您具有访问recs[recs.size()]的等价物，它位于recs的数组边界之外，并且是未定义的行为。
我认为您可以在第一次调用中传入recs.size()-1，但我没有查看您的所有代码。

关于c++ - 在将 vector 大小除以7时，是否有某些东西会导致快速排序算法出现段错误？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33491702/