本文主要是介绍stl的sort和手写快排的运行效率哪个比较高？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
STL的sort必然要比你自己写的快排要快，因为你自己手写一个这么复杂的sort，那就太闲了。STL的sort是尽量让复杂度维持在O(N log N)的，因此就有了各种的Hybrid sort algorithm。题主你提到的先quicksort到一定深度之后就转为heapsort，这种是introsort。
每种STL实现使用的算法各有不同，GNU Standard C++ Library的实现就是先introsort，然后再来个insertion sort。
References:
- sort (C++)
- Introsort
- libstdc++: Sorting Algorithms
详情：
STL sort源码剖析
STL的sort()算法，数据量大时采用Quick Sort，分段递归排序，一旦分段后的数据量小于某个门槛，为避免Quick Sort的递归调用带来过大的额外负荷，就改用Insertion Sort。如果递归层次过深，还会改用Heap Sort。本文先分别介绍这个三个Sort，再整合分析STL sort算法(以上三种算法的综合) -- 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当指针一般使用。所以才在对vector排序时会比我自己写的introsort算法快那么多呢。
原来，microsoft的sort并没有比sgi的sort快。只是在排序vector时，microsoft把vector的本质数据“萃取”出来了。
即，取消了vector在++时的边界检查语句，把vector::iterator当指针一般使用。所以才在对vector排序时会比我自己写的introsort算法快那么多呢。
这篇关于stl的sort和手写快排的运行效率哪个比较高？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
