Chinaunix

标题: STL的sort算法,为什么VC的实现选择了用3中不同的实现,而GCC只用了插入排序? [打印本页]
作者: ejeker    时间: 2013-07-07 12:43
标题: STL的sort算法,为什么VC的实现选择了用3中不同的实现,而GCC只用了插入排序?
STL的sort算法，实际调用的算法不管是哪一种，都应该让算法的复杂度保持最低，对吧。
VC的sort源代码实现是，当排序的个数小于8个的时间，直接插入排序，否则用快速排序。快速排序pivot如果递归层数太深，则余下的工作采用堆排序。这样就能达到算法的最优化结果，我贴了代码:

  2. template<class _RanIt,
  3.         class _Diff,
  4.         class _Pr> inline
  5.         void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
  6.         {        // order [_First, _Last), using _Pred
  7.         _Diff _Count;
  8.         for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
  9.                 {        // divide and conquer by quicksort
  10.                 _STD pair<_RanIt, _RanIt> _Mid =
  11.                         _Unguarded_partition(_First, _Last, _Pred);
  12.                 _Ideal /= 2, _Ideal += _Ideal / 2;        // allow 1.5 log2(N) divisions

  14.                 if (_Mid.first - _First < _Last - _Mid.second)
  15.                         {        // loop on second half
  16.                         _Sort(_First, _Mid.first, _Ideal, _Pred);
  17.                         _First = _Mid.second;
  18.                         }
  19.                 else
  20.                         {        // loop on first half
  21.                         _Sort(_Mid.second, _Last, _Ideal, _Pred);
  22.                         _Last = _Mid.first;
  23.                         }
  24.                 }

  26.         if (_ISORT_MAX < _Count)
  27.                 {        // heap sort if too many divisions
  28.                 _STD make_heap(_First, _Last, _Pred);
  29.                 _STD sort_heap(_First, _Last, _Pred);
  30.                 }
  31.         else if (1 < _Count)
  32.                 _Insertion_sort(_First, _Last, _Pred);        // small
  33.         }
复制代码
但是GCC4.4里面的源代码，我看起来都是插入排序啊:


  3.   template<typename _RandomAccessIterator>
  4.     inline void
  5.     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
  6.     {
  7.       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  8.         _ValueType;

  10.       // concept requirements
  11.       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
  12.             _RandomAccessIterator>)
  13.       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
  14.       __glibcxx_requires_valid_range(__first, __last);

  16.       if (__first != __last)
  17.         {
  18.           std::__introsort_loop(__first, __last,
  19.                                 std::__lg(__last - __first) * 2);
  20.           std::__final_insertion_sort(__first, __last);
  21.         }
  22.     }
复制代码
以及

  2.   /// This is a helper function for the sort routine.
  3.   template<typename _RandomAccessIterator>
  4.     void
  5.     __final_insertion_sort(_RandomAccessIterator __first,
  6.                            _RandomAccessIterator __last)
  7.     {
  8.       if (__last - __first > int(_S_threshold))
  9.         {
  10.           std::__insertion_sort(__first, __first + int(_S_threshold));
  11.           std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
  12.         }
  13.       else
  14.         std::__insertion_sort(__first, __last);
  15.     }
复制代码
这岂不是会让sort算法的复杂度保持在o(n^2)? GCC的STL实现不该回这么傻吧
作者: myworkstation    时间: 2013-07-07 12:43
注意std::__introsort_loop，相当于qsort的改进版。必须要看清楚的是，__final_insertion_sort()之前，经过__introsort_loop()的整个序列可以看成是一个个元素个数小于或等于16的子序列(注意子序列长度是不等的)，且这些子序列不但内部有相当程度排序，且更重要的是以子序列与子序列之间也是“递增”的，意思是前一个子序列中的元素都是小于后一个子序列中的元素的，所以这个时候运用insertion_sort()，效率可是相当高的。

参见：http://blog.sina.com.cn/s/blog_9d987af501014zlj.html
作者: rosynirvana    时间: 2013-07-07 13:12
sort还可能调用 std::__introsort_loop
std::__introsort_loop还可能调用  __partial_sort
上面俩函数定义在std_algo.h中





欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2