c++ - 快速排序/vector/分区问题

Question

我对以下代码有疑问:

class quicksort {
private:
  void _sort(double_it begin, double_it end)
  {
    if ( begin == end ) { return ; }
    double_it it = partition(begin, end, bind2nd(less<double>(), *begin)) ;
    iter_swap(begin, it-1);
    _sort(begin, it-1);
    _sort(it, end);
  }
public:
  quicksort  (){}
  void operator()(vector<double> & data)
  {
    double_it begin = data.begin();
    double_it end = data.end() ;
    _sort(begin, end);
  }
};

但是，这不适用于过多的元素(它适用于 10 000 个元素，但不适用于 100 000 个)。

示例代码:

int main()
{
  vector<double>v ;

  for(int i = n-1; i >= 0 ; --i)
    v.push_back(rand());  

  quicksort f;
  f(v);

  return 0;
}

STL 分区函数不适用于这样的大小吗？还是我遗漏了什么？

非常感谢您的帮助。

Answer 1

我看到了几个问题。我不会在您的分区中包括枢轴，所以我会改用这一行:

double_it it = partition(begin + 1, end, bind2nd(less<double>(), *begin)) ;

此外，我不会继续在您的 future 排序中包含枢轴，所以我会这样做

_sort(begin, it - 2);

相反，但你需要注意 it - 2 不小于 begin 所以检查 it - 1 != begin 首先。没有必要不断地对枢轴进行排序——它已经在正确的位置了。这只会增加很多额外的不必要的递归。

即使在更改之后，您肯定仍然会遇到此代码的堆栈溢出问题。例如，如果您使用此代码对已排序的数组进行排序，则性能将为 O(N^2)，如果 N 非常大，则会出现堆栈溢出。使用随机选择的枢轴将基本上消除排序数组问题，但如果数组都是相同的元素，你仍然会遇到问题。在这种情况下，您需要更改算法以使用 Bentley-McIlroy 分区等。或者，您可以将其更改为 introsort，并在递归深度变得非常深时更改为堆排序。