Simon 's Blog
» 做笔记做笔记
Toggle navigation
Simon 's Blog
HOME
总裁介绍
coper
zongcai
what
ARCH
TAGS
navigation
!!! SGI STL中的sort源码
? STL算法 ?
2019-07-31 18:56:44
488
0
0
simon88
? STL算法 ?
[TOC] # 实现原理 STL中的sort不是普通的快排,除了对普通的快速排序进行优化,它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况,能自动选用合适的排序方法。当数据量较大时采用快速排序,分段递归。一旦分段后的数据量小于某个阀值,为避免递归调用带来过大的额外负荷,便会改用插入排序;而如果递归层次过深,有出现最坏情况的倾向,还会改用堆排序。 # 内省式排序 `Introsort` 不当的基准选择会导致不当的分割,会使快速排序恶化为 O(n^2)。David R.Musser于1996年提出一种混合式排序算法:Introspective Sorting(内省式排序),简称IntroSort,其行为大部分与上面所说的median-of-three Quick Sort完全相同,但是当分割行为有恶化为二次方的倾向时,能够自我侦测,转而改用堆排序,使效率维持在堆排序的 O(nlgn),又比一开始就使用堆排序来得好。 # 代码 ``` template<typename RandomAccessIterator, typename Compate> inline void sort(RandomAccessIterator first, RandomAccessIterator last, Compate comp) { if (first != last) { __introsort_loop(first, last, __lg(last - first) * 2,comp); __final_insertion_sort(first, last,comp); } } ``` std::__introsort_loop 便是上面介绍的内省式排序,其第三个参数中所调用的函数 __lg() 便是用来控制分割恶化情况,具体功能类似求lg(n)(取下整),意味着快速排序的递归调用最多 2*lg(n) 层。 ## 内省式 __introsort_loop ``` template<typename _RandomAccessIterator,typename _Size, typename _Compare> void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp) { while (__last - __first > __stl_threshold) { if (__depth_limit == 0) { std::partial_sort(__first, __last, __last,__comp);//分割恶化,使用heap sort return; } --__depth_limit; //选择一个枢纽决定分割点,并且将分割点落到__cut身上。 _RandomAccessIterator __cut = __unguarded_partition( __first, __last, __median(*__first, *(__first + (__last - __first)/2), *(__last-1),__comp), __comp); //对右半部分进行递归sort __introsort_loop(__cut, __last, __depth_limit, __comp); __last = __cut; //现在回到while,准备对左半部分递归sort } } ``` - 首先判断元素规模是否大于阀值_S_threshold,_S_threshold是一个常整形的全局变量,值为16,表示若元素规模小于等于16,则结束内省式排序算法,返回sort函数,改用插入排序 __final_insertion_sort。 - 若元素规模大于_S_threshold,则判断递归调用深度是否超过限制。若已经到达最大限制层次的递归调用,则改用堆排序。代码中的 __partial_sort 即用堆排序实现。 - 若没有超过递归调用深度,则调用函数 __unguarded_partition_pivot 对当前元素做一趟快速排序,并返回基准位置。 - 快排之后,再递归对右半部分调用内省式排序算法。然后回到while循环,对左半部分进行排序。源码写法和我们一般的写法不同,但原理是一样的,这是很明显的尾递归优化,需要注意。 ## 快速排序(分区) ``` const int __stl_threshold = 16; template<typename _RandomAccessIterator, typename _T, typename _Compare> _RandomAccessIterator __unguarded_partition( _RandomAccessIterator __first, _RandomAccessIterator __last, _T __pivot, _Compare __comp) { while (true) { --__last; while (__comp(*__first, __pivot) && __first<__last) ++__first; while (__comp(__pivot, *__last) && __first<__last) --__last; if (!(__first < __last)) return __first; std::iter_swap(__first, __last); ++__first; } } //求lg(N),控制分割恶化的情况 template<typename Size> Size __lg(Size n) { Size k; for (k = 0; n > 1; n >>= 1) k++; return k; } ``` ## 三点中值 ``` //三值中值 template<typename T,typename Compare> T __median(T& a, T& b, T& c, Compare comp) { if (comp(a, b)) if (comp(b, c)) return b; else if (comp(a, c)) return c; else return a; else if (comp(a, c)) return a; else if (comp(b, c)) return c; else return b; } //template<typename _RandomAccessIterator,typename _Compare> //inline void __pop_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_RandomAccessIterator __result,) //template<typename _RandomAccessIterator,typename _Compare> //void __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator, _Compare __comp) //{ // std::make_heap(__first, __middle); // for (_RandomAccessIterator i = middle; i < __last; ++i) // { // if (*i < *first) // { // __pop_heap(__first, __middle,__comp); // } // std::sort_heap(__first, __middle,__comp); // } //} ``` ## 插入排序(__final_insertion_sort) ``` template<typename _RandomAccessIterator, typename T,typename _Compare> inline void __unguarded_linear_insert(_RandomAccessIterator __last, T __value,_Compare __comp) { _RandomAccessIterator next = __last; --next; //一旦不再出现逆转对,停止循环 while (__comp(__value, *next)) { *__last = *next; __last = next; --next; } *__last = __value; } template<typename _RandomAccessIterator, typename _Compare> inline void __linear_insert(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typename std::iterator_traits<_RandomAccessIterator>::value_type value = *__last; if (__comp(value, *__first)) //比头还要小 { std::copy_backward(__first, __last, __last + 1); *__first = value; } else __unguarded_linear_insert(__last, value,__comp); } template<typename _RandomAccessIterator, typename _Compare> inline void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { if (__first == __last) return; for (_RandomAccessIterator i = __first + 1; i != __last; ++i) { __linear_insert(__first, i, __comp); //[first,i)已排序的区间。 } } template<typename _RandomAccessIterator, typename _Compare> inline void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { for (_RandomAccessIterator i = __first; i != __last; ++i) { __unguarded_linear_insert(i, *i, __comp); } } template<typename _RandomAccessIterator,typename _Compare> inline void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare comp) { if (__last - __first > __stl_threshold) { __insertion_sort(__first,__first+__stl_threshold, comp); __unguarded_insertion_sort(__first + __stl_threshold, __last, comp); } else __insertion_sort(__first, __last, comp); } ``` # 测试例子 ``` void testIterSort() { std::function<void(int&)> print = [](int &x) { std::cout << x << " "; }; std::function<bool(int&, int&)> comp = [](const int& x, const int& y) {return x < y; }; int *a = SortTestHelper::generateRandomArray(10, 0, 10); std::vector<int> v(a,a+ 10); //for_each(v.begin(), v.end(), print); iter_sort::sort(v.begin(), v.end(), comp); std::cout << "\n"; //iter_sort::__unguarded_partition_pivot(v.begin(), v.end(),comp); //std::nth_element(v.begin(), v.begin() + 5, v.end(),std::greater<int>()); //不做全排序 for_each(v.begin(), v.end(), print); std::cout << "\n"; } ``` # 参考RW_STL sort算法 ``` namespace rw_sort { template<typename RandomAccessIterator, typename Compate> inline void __quick_sort_loop(RandomAccessIterator first, RandomAccessIterator last, Compate comp) { while (last - first > __stl_threshold) { //midian RandomAccessIterator cut = ::__unguarded_partition( first , last , sgi_sort::__median(*first, *(first + (last - first) / 2), *(last - 1),comp) , comp); if (cut - first >= last - cut) { __quick_sort_loop(cut, last,comp); last = cut; } else { __quick_sort_loop(first, cut,comp); first = cut; } } } template<typename RandomAccessIterator, typename Compate > inline void sort(RandomAccessIterator first, RandomAccessIterator last, Compate comp) { if (first != last) { __quick_sort_loop(first,last,comp); sgi_sort::__final_insertion_sort(first, last, comp); } } template<typename RandomAccessIterator> inline void sort(RandomAccessIterator first, RandomAccessIterator last) { if (first != last) { __quick_sort_loop(first, last, _comp); //sgi_sort::__final_insertion_sort(first, last, _comp); } } } ``` 本算法不包含sgi sort中的内省排序算法。 参考[STL::sort函数实现](https://www.cnblogs.com/AlvinZH/p/8682992.html)
上一篇:
C++11并发编程
下一篇:
以 boost::function 和 boost::bind 取代虚函数
0
赞
488 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
0
条评论
More...
<>