stl的sort和手写快排的运行效率哪个比较高？
发布时间：2020-12-13 21:05:42 所属栏目：PHP教程 来源：网络整理
导读：STL的sort必定要比你自己写的快排要快，由于你自己手写1个这么复杂的sort，那就太闲了。STL的sort是尽可能让复杂度保持在O(N log N)的，因此就有了各种的Hybrid sort algorithm。 题主你提到的先quicksort到1定深度以后就转为heapsort，这类是introsort。 每
|
STL的sort必定要比你自己写的快排要快，由于你自己手写1个这么复杂的sort，那就太闲了。STL的sort是尽可能让复杂度保持在O(N log N)的，因此就有了各种的Hybrid sort algorithm。 题主你提到的先quicksort到1定深度以后就转为heapsort，这类是introsort。 每种STL实现使用的算法各有不同，GNU Standard C++ Library的实现就是先introsort，然后再来个insertion sort。 References:
详情：
STL sort源码剖析STL的sort()算法，数据量大时采取Quick Sort，分段递归排序，1旦分段后的数据量小于某个门坎，为避免Quick Sort的递归调用带来过大的额外负荷，就改用Insertion Sort。如果递归层次过深，还会改用Heap Sort。本文先分别介绍这个3个Sort，再整合分析STL sort算法(以上3种算法的综合) -- Introspective Sorting(内省式排序)。。。。。 VS2010版STL中的sort竟比我自己写的快这么多？ 首先，上文实现的这个Introsort是参照SGI STL写的，因而，我大胆在VS2010中拿他与std:sort比了比快慢。因而就随机产生两个百万数据的vector用来测试。结果发现，VS中sort的速度竟是我的10倍以上的效力。顿时对微软萌发敬意，可是当我仔细翻看源码时..... 原来，microsoft的sort并没有比sgi的sort快。只是在排序vector时，microsoft把vector的本质数据“萃取”出来了。 即，取消了vector在++时的边界检查语句，把vector::iterator当指针1般使用。所以才在对vector排序时会比我自己写的introsort算法快那末多呢。 版权声明：本文为【借你1秒】原创文章，转载请标明出处。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |