【STL源码剖析】Sort算法

亦凉 2022-08-09 03:18 189阅读 0赞

**前言：sort算法必须拿出来单独将，因为它是STL所有算法中最复杂最庞大的一个，就像我肯定会把copy算法单独列出来一样，这两个算法太重要了。**

提示：STL算法特点是，前两个形参变量都是迭代器指针。并且每个算法都有两个版本，一个是默认版本，另外一个是提供仿函数的版本。

## 介绍： ##

1.  sort算法接收两个随机存取迭代器(RandomAccessIterators),所以像list这种BidirectionaIterators双向的迭代器不能用sort算法，而应该用容器自己提供的sort算法。
2.  默认以递增的方式排列，可以通过另一个版本使用仿函数实现其他类型的排序。

## 实现： ##

1.  数据量大时采用快速排序，分段递归，一旦分段递归的数据小于某个门槛（早期定义的是16，不过一般5-20都比较好），就使用插入排序。如果快速排序过程中递归层次过深还会改用堆排序。
2.  快排的枢轴元素，采用三点取中值法获取，取序列的头、中、尾三个位置的元素，然后取这三个元素中间大小的元素作为枢轴元素。
3.  SGI STL 的sort算法其实是introsort算法的改进，除了取枢轴元素采用三点取中法外，其他相同。
4.  防止分割恶化的方法：找出2^k <= n 的最大值，只允许分割k\*2层。
5.  特别注意，如果元素数量一开始就小于\_\_stl\_threshold（16）,那么就直接采用插入排序。
6.  在插入排序中，有个鲁棒性处理，当元素数量大于16，就把前16个用插入排序，后面的元素只进行逆序对调整。
7.  注意RW版本只是简单的快排+插入排序。没有用到introsort。

## 使用： ##

1.默认递增

sort(array.begin(),array.end(),std::less<string>()); //从小到大，默认

sort(array.begin(),array.end(),std::greater<string>());  //从大到小

2.自定义仿函数

bool cmp(int a,int b)
    {
        return a>b;
    }
    //排序的时候就写 sort(a,a+100,cmp);

## 扩展： ##

1.  qsort（）函数

> 功 能： 使用快速排序例程进行排序  
> 头文件：stdlib.h  
> 用 法： void qsort(void *base,int nelem,int width,int (\*fcmp)(const void* ,const void \*));  
> 参数： 1 待排序数组首地址  
> 2数组中待排序元素数量  
> 3各元素的占用空间大小  
> 4指向函数的指针，用于确定排序的顺序

1.  sort函数的扩展函数

<table> 
 <thead> 
  <tr> 
   <th>函数名</th> 
   <th align="center">功能描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>sort</td> 
   <td align="center">对给定区间所有元素进行排序</td> 
  </tr> 
  <tr> 
   <td>stable_sort</td> 
   <td align="center">对给定区间所有元素进行稳定排序</td> 
  </tr> 
  <tr> 
   <td>partial_sort</td> 
   <td align="center">对给定区间所有元素部分排序</td> 
  </tr> 
  <tr> 
   <td>partial_sort_copy</td> 
   <td align="center">对给定区间复制并排序</td> 
  </tr> 
  <tr> 
   <td>nth_element</td> 
   <td align="center">找出给定区间的某个位置对应的元素</td> 
  </tr> 
  <tr> 
   <td>is_sorted</td> 
   <td align="center">判断一个区间是否已经排好序</td> 
  </tr> 
  <tr> 
   <td>partition</td> 
   <td align="center">使得符合某个条件的元素放在前面</td> 
  </tr> 
  <tr> 
   <td>stable_partition</td> 
   <td align="center">相对稳定的使得符合某个条件的元素放在前面</td> 
  </tr> 
 </tbody> 
</table>

## 总结 ##

这里的sort算法总结已经是非常全了，除了没有把代码copy过来。在我看来STL的算法是一种寻求最佳的折衷方案，在实际写排序算法应用当中我们应该学习STL这种思想，来写出最合适实际需求的算法。有兴趣还可以研究一下introsort算法，我觉得对于我们提示排序算法综合水平有帮助。