首页 > 代码库 > Cpp11_2 sort 排序函数
Cpp11_2 sort 排序函数
sort函数声明:
1 #include <algorithm> 2 3 template< class RandomIt > 4 void sort( RandomIt first, RandomIt last ); 5 6 template< class RandomIt, class Compare > 7 void sort( RandomIt first, RandomIt last, Compare comp );
一般,sort自带的排序算法比我们自己实现的要快。
实现原理:
STL
中的sort
并非只是普通的快速排序,除了对普通的快速排序进行优化,它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况,能自动选用合适的排序方法。当数据量较大时采用快速排序,分段递归。一旦分段后的数据量小于某个阀值,为避免递归调用带来过大的额外负荷,便会改用插入排序。而如果递归层次过深,有出现最坏情况的倾向,还会改用堆排序。
普通快速排序:
随机枢轴,分区排序
内省式排序 Introsort
普通快速排序最坏的情况 O(n2),而内省式排序,当分割行为有恶化为二次方的倾向时,能够自我侦测,转而改用堆排序,使效率维持在堆排序的 O(nlgn),又比一开始就使用堆排序来得好。
SGI STL sort:
1 template <class _RandomAccessIter> 2 inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) { 3 __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); 4 __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, 5 _LessThanComparable); 6 if (__first != __last) { 7 __introsort_loop(__first, __last, 8 __VALUE_TYPE(__first), 9 __lg(__last - __first) * 2); 10 __final_insertion_sort(__first, __last); 11 } 12 }
Cpp11_2 sort 排序函数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。