ITPub博客

首页 > 应用开发 > IT综合 > STL的内观排序(introsort)算法学习笔记 (转)

STL的内观排序(introsort)算法学习笔记 (转)

原创 IT综合 作者:worldblog 时间:2007-12-04 13:16:46 0 删除 编辑
STL的内观排序(introsort)算法学习笔记 (转)[@more@]

 

STL(Standard Template Library)的算法据说是经过精心优化的。那么在它的排序算法方面做了哪些优化呢?


自从快速排序算法出世以后,从平均性能上来说,除了在数据量极少(<=20)的的情况下其性能不如插入排序外,快速算法的性能起码是其他同阶算法的2到3倍,这也已经是教科书里不争的事实。


一个最简单的混合算法就是在数据量少的时候(n<20),算法转入插入排序,而其它时候则仍然采用快速排序,比如


void quicksort(_RandomIterator __start, _RandomIterator __last)
{
  while (__last - __first > __stl_threshold) {
  _RandomIterator __pivot= partition(__first, __last, mean(*__first, *__last, *(__first + (__last-__first)/2));
  quicksort(__first, __pivot);
  __first = __pivot;
  }
  __insert_sort(__first, __last);
}

这里有一个选择,就是什么时候做插入排序:上面的算法是每次细分到数据量小于阈值就转入插入排序;另外一种算法是一旦细分到数据长度小于阈值就退出,最后汇总的时候再来一次总的插入排序。应该说这两种算法没有很大的区别,但是STL使用的是后者。原因最后再说。


STL真正出彩的地方是对快速排序算法的补充。快速 排序的特点是平均性能好,能达到O(NlgN)的性能,缺点是对于最坏情况性能会下降到O(N^2)。STL对此做的补充是引入一个递归计数,当递归深度超过一定阈值(STL设定的阈值是2lgN),则算法转入一个较慢的但是最坏情况也是O(NlgN)的算法,比如堆排序(STL把堆排序推广为partial_sort也就是部分排序)。这一算法监控自身的递归深度,具有一定的内观性,被称为内观排序(introsort--introspective sort),实际上是快速排序法的变种,是一种混合算法。在最坏情况下能近似达到O(NlgN)的性能。实际上在最坏情况下比堆排序要差点,但是比快速排序要好得多。而其平均性能和快速排序差不多。其算法如下:


void introsort_loop(RandomIterator __first, RandomIterator __last, int m)
{
 while (__last - __first > __stl_threshold) {
 if (0==m) {
 partial_sort(__first, __last, __last);
 return;
 }
 RandomIterator __pivot = mean(*__first, *__last, *(__first+(__last-__first)/2));
 introsort__loop(__first, __pivot);
 __first = __pivot+1;
 }
}
void introsort(RandomIterator __first, RandomIterator __last)
{
 introsort_loop(__first, __last, __lg(__last-__first)*2);
 __final_insert_sort(__first, __last);
}


STL在__final_inser_sort中玩了一个小小的加速trick。其算法如下:

void __final_insert_sort(__first, __last)
{
 if (__last - __first < __stl_threshold)
 __insert_sort(__first, __last);
 else {
 __insert_sort(__first, __first+__stl_threshold);
 __unguarded_insert_sort(__first+__std_threshold+1, __last);
 }
}

我当时不太明白为什么插入算法还要如此,后来自己尝试优化插入算法的时候才发现在__unguarded_insert_sort的循环中少了一个边界测试条件,这样边界测试条件从两个降为一个。原因就是经过“粗略的”快速排序后,最小元素已经能确定就在前__stl_threshold个元素中,于是基于位置的边界条件就可以去掉。具体参看插入排序的算法。不再赘述。
 


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10752043/viewspace-988340/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    6241
  • 访问量
    2410344