首页 > 代码库 > 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 排序函数