【STL源码剖析】Sort算法-蒲公英云

【STL源码剖析】Sort算法

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

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

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

介绍：

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

实现：

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

扩展：

qsort（）函数

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

sort函数的扩展函数

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