Std排序使Std:：vector无效

Question

我在std:：sort中发现了一个bug，特别是在一些QuickSort的实现中，我不知道问题是否出在一般的算法中。

精华：

当元素小于16时，所有的规范都被替换，因为std:：sort使用插入排序。

当有17个或更多的元素时，使用快速排序，并从元素数量的对数限制递归深度，但向量在第一次__introsort_loop迭代时有时间恶化。

当有许多相同的元素时，就会出现向量损坏。用无效迭代器替换有效迭代器时发生损坏。

其他容器也可能破裂，我没有检查。

对于更复杂的对象，使用类型为“int”的向量简化示例-排序时崩溃，因为无效对象被传递给比较函数：

#include <iostream>
#include <vector>
#include <algorithm>

void quickSort(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

  /* partition */

  while (i <= j) {
        while (arr[i] < pivot)
              i++;
        while (arr[j] > pivot)
              j--;
        if (i <= j) {
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
        }
  };

  /* recursion */

  if (left < j)
        quickSort(arr, left, j);

      if (i < right)
            quickSort(arr, i, right);
}

int main()
{
  for( int i = 0 ; i < 1 ; i++ )
  {
    //std::vector<int> v({5, 6, 1, 6, 2, 6, 3, 6, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 6});//reproducible with this
    std::vector<int> v(19, 6);//reproducible with this also
    std::sort(std::begin(v), std::end(v), [&v]( const int & left, const int & right )
                                          {
//                                          std::cout << " left=" << left << ", right=" << right << std::endl;
                                            bool b = left <= right;
                                            return b;
                                          }
              );
//    quickSort(v.data(), 0, v.size());
 for( const auto & result : v )
 {
    std::cout << "results: " << result << std::endl;
 }
  }

  std::cout << "Hello World!\n";
}

有人会遇到这种行为吗？

Answer 1

我试过你的代码，似乎问题出在用构造函数向量（n，val）（fill构造函数）创建的向量上。当手动插入16、17、18和19个随机元素时，向量显示没有问题。

Answer 2

你必须在开始上课时保存支点，比如

void快速排序（int-arr[]，int-left，int-right）{int i=left，j=right；int-pivot=x[left]；之后就可以工作了