- 论坛徽章:
- 0
|
5可用积分
STL的sort算法,实际调用的算法不管是哪一种,都应该让算法的复杂度保持最低,对吧。
VC的sort源代码实现是,当排序的个数小于8个的时间,直接插入排序,否则用快速排序。快速排序pivot如果递归层数太深,则余下的工作采用堆排序。这样就能达到算法的最优化结果,我贴了代码:
- template<class _RanIt,
- class _Diff,
- class _Pr> inline
- void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
- { // order [_First, _Last), using _Pred
- _Diff _Count;
- for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
- { // divide and conquer by quicksort
- _STD pair<_RanIt, _RanIt> _Mid =
- _Unguarded_partition(_First, _Last, _Pred);
- _Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions
- if (_Mid.first - _First < _Last - _Mid.second)
- { // loop on second half
- _Sort(_First, _Mid.first, _Ideal, _Pred);
- _First = _Mid.second;
- }
- else
- { // loop on first half
- _Sort(_Mid.second, _Last, _Ideal, _Pred);
- _Last = _Mid.first;
- }
- }
- if (_ISORT_MAX < _Count)
- { // heap sort if too many divisions
- _STD make_heap(_First, _Last, _Pred);
- _STD sort_heap(_First, _Last, _Pred);
- }
- else if (1 < _Count)
- _Insertion_sort(_First, _Last, _Pred); // small
- }
复制代码 但是GCC4.4里面的源代码,我看起来都是插入排序啊:
- template<typename _RandomAccessIterator>
- inline void
- sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
- {
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
- // concept requirements
- __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
- _RandomAccessIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- __glibcxx_requires_valid_range(__first, __last);
- if (__first != __last)
- {
- std::__introsort_loop(__first, __last,
- std::__lg(__last - __first) * 2);
- std::__final_insertion_sort(__first, __last);
- }
- }
复制代码 以及
- /// This is a helper function for the sort routine.
- template<typename _RandomAccessIterator>
- void
- __final_insertion_sort(_RandomAccessIterator __first,
- _RandomAccessIterator __last)
- {
- if (__last - __first > int(_S_threshold))
- {
- std::__insertion_sort(__first, __first + int(_S_threshold));
- std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
- }
- else
- std::__insertion_sort(__first, __last);
- }
复制代码 这岂不是会让sort算法的复杂度保持在o(n^2)? GCC的STL实现不该回这么傻吧 |
最佳答案
查看完整内容
注意std::__introsort_loop,相当于qsort的改进版。必须要看清楚的是,__final_insertion_sort()之前,经过__introsort_loop()的整个序列可以看成是一个个元素个数小于或等于16的子序列(注意子序列长度是不等的),且这些子序列不但内部有相当程度排序,且更重要的是以子序列与子序列之间也是“递增”的,意思是前一个子序列中的元素都是小于后一个子序列中的元素的,所以这个时候运用insertion_sort(),效率可是相当高的。 参见:h ...
|