STL源码：算法sort

迷南。 2022-08-05 14:25 180阅读 0赞

## sort算法适用范围    ##

sort算法接受两个RandomAccessIterators（随机存取迭代器），然后对区间内元素以渐增方式由小到大排序；另一个版本允许用户指定排序方式。

**STL的所有关联容器都拥有自动排序功能**（以为底层的RB-tree是自动排序的）因此，不需要使用sort算法。顺序容器中stack、queue、priority-queue都有特定的入口和出口，不允许用户对元素排序。剩下的vector、deque、list，其中**vector、deque适合使用sort算法**，因为其迭代器属于RandomAccessIterators。而list迭代器是Bidirectionalterators，slist属于ForwardIterators，都不适合sort算法；list、slist排序，应该使用它们自己提供的成员函数sort()。

## sort算法思想    ##

SGI STL sort算法的思想：数据量大采用快速排序，分段排序；一旦分段后的数量小于某个门槛，为了避免快速排序的递归调用带来过大的额外负荷，改用插入排序；如果递归层次过深，还会改用堆排序（参考文章《[堆排序][Link 1]》）。

其中，STL sort算法采用的快速排序是三数取中值法参考文章《[快速排序的几种常见实现][Link 2]》，该文章中快排的版本5就该方法且用到了插入排序。

当序列很小时，快速排序会产生大量的极小的子序列而产生大量的函数递归调用，因此采用插入排序，那么，究竟多小时采用插入排序？没有定论，5-20都可能差不多，实际最佳值因设备而异。在我的G++ 4.4版本中，该值定义为16，也就是元素少于16个就插入排序。

**有的版本的STL与SGI STL不同，它们直接使用快速排序，没有插入、堆等排序**。

## sort算法判断递归深度的函数 ##

上面已经提到，当递归层次过深时，要改用堆排序，如何判断递归层次呢，如下函数：

//有n个元素，那么每次除以2，知道n为0，那么除法次数就是递归深度了。
    //例如n = 20，那么递归深度为4
    template<typename _Size>
    inline _Size
    __lg(_Size __n)
    {
          _Size __k;
          for (__k = 0; __n != 0; __n >>= 1)
    	++__k;
          return __k - 1;
    }

在我的G++ 4.4版本中，该值也被定义为16。

## sort算法的稳定性 ##

关于基本算法的稳定性，参考文章《[基础排序算法总结][Link 3]》。

由于STL 用到了堆排序、快速排序等算法，而这两个算法都不稳定，因此，sort算法不稳定。

[Link 1]: http://blog.csdn.net/u013074465/article/details/42043697
[Link 2]: http://blog.csdn.net/u013074465/article/details/42083607
[Link 3]: http://blog.csdn.net/u013074465/article/details/44346135