1

我对以下代码有疑问:

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 分区功能不适用于这样的大小吗?还是我错过了什么?

非常感谢您的帮助。

4

3 回答 3

2

我看到了几个问题。我不会在你的分区中包含枢轴,所以我会使用这条线:

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

另外,我不会继续在你未来的分类中包含枢轴,所以我会这样做

_sort(begin, it - 2);

取而代之的是,但您需要小心,it - 2至少要先begin检查一下it - 1 != begin。无需不断地对枢轴进行排序 - 它已经在正确的位置。这只会增加很多额外的不必要的递归。

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

于 2010-05-26T13:57:54.520 回答
1

您是否检查过您的doublt_it it值没有被设置为begin' 值?那会导致线路出现问题iter_swap(begin, it-1);

不是?

好的,猜测#2 是堆栈溢出,因为您要进行太多递归。某些编译器无法处理许多递归循环。100k 可以解决问题,而 10k 可以处理。

于 2010-05-26T13:36:58.063 回答
0

检查以下代码。我写得很快,没有模板和使用迭代器,但想法是证明快速排序可以对巨大的数组进行排序(这很明显,嘿嘿)

因此,您的快速排序在算法方面存在问题,而不是在堆栈溢出/其他编译器方面。我的意思是,您应该始终尝试了解是什么原因导致的,并消除“深层”问题,而不是“浅层”问题。

请注意,我的代码可以使用与代码中相同的迭代器方法轻松重写(可能需要一些额外的检查,但无论如何,它很容易实现)。

#include <vector>
#include <algorithm>
#include <utility>
#include <functional>

class sorter {
public:
   sorter(std::vector<int>& data) : data(data) { }

   void quicksort(int p, int r) {
      if (p < r) {
         int q = std::partition(data.begin() + p, data.begin() + r, std::bind2nd(std::less<int>(), data[r])) - data.begin();
         std::swap(data[q], data[r]);
         quicksort(p, q - 1);
         quicksort(q + 1, r);
      }
   }

   void sort() {
      quicksort(0, data.size() - 1);
   }

private:
   std::vector<int>& data;
};

int main() {
   size_t n = 1000000;
   std::vector<int> v;

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

   sorter s(v);
   s.sort();

   return 0;
}

#编辑

迭代器的东西意味着类似

class sorter {
public:
   typedef std::vector<int> data_type;
   sorter(std::vector<int>& data) : data(data) { }

   void quicksort(data_type::iterator p, data_type::iterator r) {
      data_type::iterator q = std::partition(p, r, std::bind2nd(std::less<int>(), *r));
      std::iter_swap(q, r);

      if (q != p)
         quicksort(p, q - 1);
      if (q != r)
         quicksort(q + 1, r);
   }

   void sort() {
      quicksort(data.begin(), data.end() - 1);
   }

private:
   std::vector<int>& data;
};
于 2010-05-26T14:57:04.283 回答