前言

绝大多数人在听到排序之后只会想到sort，当然，sort是一个优秀的算法，只是我们有时候不一定非要用它。

部分排序

假设当前我们只需要找出某堆Widget中前20个质量最好的,剩下的不用管它，那么这个时候执行全排无疑是不必要的，我们所需要的仅仅只是partial_sort:

bool qualityCompare(const Widget& lhs, const Widget& rhs){
    //返回lhs的质量是不是比rhs的质量好
}
...
//把质量最好的20个Widget按顺序放在容器前端
partial_sort(widgets.begin(), widgets.begin() + 20,widgets.end(),qualityCompare);

无需有序排列的部分排序

有时候需求比部分排序还要少，我们只需要找出前20个质量好的，根本不要求它们被找到后依次排好序，此时我们可以调用这个算法nth_element。
nth_element排序一个区间，在ri（用户指定）位置的元素是如果区间被完全排序会出现的元素，当nth_element返回时，在n以上的元素必然就是全排之后的前n个.具体使用如下：

1	nth_element(widgets.begin(), widgets.begin() + 19, widgets.end(), qualityCompare);

我怀疑partial_sort内部调用了nth_element，然后再对前n个进行了排序。

稳定性

这两种算法均不具备稳定，如果你需要稳定性，请使用stable_sort。STL并不包含partial_sort和nth_element的稳定版本。

nth_element的额外用途：查找

nth_element不仅仅能够帮我们找到区间顶部的n个元素，还能够轻易找出区间中值或者在指定百分点的元素：

vector<Widget>::iterator begin(widgets.begin()); 
vector<Widget>::iterator end(widgets.end());
vector<Widget>::iterator goalPosition;
goalPosition = begin + widgets.size() / 2;
nth_element(begin, goalPosition, end,qualityCompare);//此时goalPosition指向中值

原理很简单，上文已经提及：在调用算法后，在ri（用户指定）位置的元素是如果区间被完全排序会出现的元素。

分割容器

有时候我们并不需要排序，我们只需要简单粗暴的根据某一个判定依据，把元素分成一堆，和另外一堆，这个时候partition来了，它重排区间中的元素，使满足某个标准的元素都在区间的开头。

bool hasAcceptableQuality(const Widget& w){
    //返回w质量等级是否是2或更高;
}
//返回指向第一个不符合条件元素的迭代器
auto goodEnd =partition(widgets.begin(), widgets.end(), hasAcceptableQuality);

如果你需要稳定性，记得使用stable_partition.

上述算法对迭代器的要求

算法sort，partial_sort，stable_sort和nth_element需要随机访问迭代器，那也就是说只能用于vector、string、deque与array。
list的sort是稳定的，但如果想使用partial_sort或者nth_element，只能间接完成:

拷贝list到一个vector或者别的支持随机访问迭代器的容器中
建立一个list::iterator的容器，对该容器使用算法，通过迭代器访问元素。（算法谓词完成解引用)

partition与stable_partition只需要双向迭代器，所以可以在任何容器上使用。

算法性能比较

以上算法性能由高到低可以排序为：
partition>stable_partition>nth_element>partial_sort>sort>stable_sort