QuickSort适用于小尺寸矢量，但不适用于大矢量

Question

我曾尝试编写QuickSort的实现，但是有一些我无法识别的错误。下面的代码在较小的矢量（如100）上运行良好，但是当我尝试从文件中提供10,000个数字时，程序不会停止运行。任何帮助都会很棒。

int Partition(vector<int> &nums, int low, int high, unsigned long &numIterations) {
  int paritionIndex = low;
  int paritionElement = nums.at(paritionIndex);
  int potentialPivotIndex = low + 1;
  for (int i = low + 1; i < high; ++i) {
    if (paritionElement > nums.at(i)) {
      std::swap(nums.at(potentialPivotIndex), nums.at(i));
      ++potentialPivotIndex;
    }
  }
  std::swap(nums.at(potentialPivotIndex - 1), nums.at(paritionIndex));
  //++numIterations;
  return potentialPivotIndex - 1;
}

void QuickSort(vector<int> &nums, int low, int high, unsigned long &numIterations) {
  int p;
  if ((high - low) > 0) {
    p = Partition(nums, low, high, numIterations);
    QuickSort(nums, 1, p - 1, numIterations);
    QuickSort(nums, p + 1, high, numIterations);
  }
}

Answer 1

您的分区功能不正确。即使它为较小尺寸的输入生成的输出也不正确。我已根据here给出的代码对它进行了更改，如下所示：

int Partition(vector<int> &nums, int low, int high, unsigned long &numIterations) {

    int pivot = nums.at(high);    // pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (nums.at(j) <= pivot)
        {
            i++;    // increment index of smaller element
            swap(nums.at(i), nums.at(j));
        }
    }
    swap(nums.at(i + 1), nums.at(high));
    return (i + 1);
}

Answer 2

经过大量调试后，我发现初始代码有两个问题。

1. 在QuickSort函数中，我应该将变量low赋予该函数，但我给它提供了常数值1。
2. 我将for loop功能的Partition更改为high]而不是high)的范围，并且将主要功能称为QuickSort功能，并带有size - 1

通过上面的修正确定了代码，我能够对向量进行排序。