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:- sort (C++)
- Introsort
- libstdc++: Sorting Algorithms
详情：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秒】原创文章，转载请标明出处。