Std排序使std：：向量无效

Question

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

本质：

当元素小于16时，所有规范，因为std：：排序使用插入排序。

当有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

您必须在起始类中保存枢轴，如

void quickSort(int arr[]，int左，int右){ int i=左，j=右；int pivot=xleft；之后将工作。

Answer 2

我尝试了您的代码，问题似乎是用构造函数向量(n，val) (填充构造函数)创建的向量。当手动插入16、17、18和19个随机元素时，向量没有问题。