函数声明:
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循环,对左半部分进行排序。