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

王朝vc·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

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个元素中,于是基于位置的边界条件就可以去掉。具体参看插入排序的算法。不再赘述。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航