STL中sort实现原理

函数声明：

    template< classRandomIt>

     voidsort(RandomItfirst,RandomItlast);

     template< classRandomIt,classCompare>

    voidsort(RandomItfirst,RandomItlast,Comparecomp);

STL提供了两种调用方式，一种使用默认的 < 操作符，一种是可以自己定义比较函数。

实现原理：

    STL中sort    内部使用三种排序方式，分别是 快排，堆排序 和插入排序，根据不同的数量级别自动选择合适的排序方法：数据量较大的时候，采用快速排序，分段递归。一旦分段后数据量小于某个阀值，改用插入排序。为避免递归调用带来的额外负荷，递归到达一定层次采用堆排序。

源码:

sort直接调用的是内省循环函数   (__introsort_loop), 

内省函数

    1.首先判读__stl_threshold这个值，__stl_threshold是一个常整型全局变量，值16，也就是说如果数量级少于16，则不会进行快排，返回上一层。进而进行插入排序。

    2.如果元素大于__stl_threshold，则判断递归调用深度是否超过限制，，如果达到最大层次的限制，改用堆排序partial_sort()；

    3.如果没有超过递归调用深度，调用__unguarded_partition(),对当前元素做一趟快速排序，返回枢纽位置。

    4.经过一次快排，在递归对右半部分进行内省排序算法，然后回到while循环，对左半部分进行排序。

插入排序 堆排序 插入排序