STL之partial_sort排序

partial_sort(beg,mid,end)
partial_sort(beg,mid,end,comp)
对mid-beg个元素进行排序&＃xff0c;也就是说&＃xff0c;如果migd-beg等于42&＃xff0c;则该函数将有序次序中的最小值元素放在序列中
的前42个位置。partial_sort完成之后&＃xff0c;从beg到mid(但不包括mid)范围内的元素时有序的&＃xff0c;已排序范围内没有
元素大于mid之后的元素。未排序元素之间的次序是未指定的。
例如&＃xff1a;
有一个赛跑成绩的集合&＃xff0c;我们想知道前三名的成绩但并不关心其他名次的次序&＃xff0c;可以这样对这个序列进行排序。
partial_sort&＃xff08;scores.begin(),scores.begin()&＃43;3,scores.end());

那么paitical_sort的原理是什么呢&＃xff1f;是堆排序&＃xff01;
首先创建一个堆&＃xff0c;得到最大值。如果要得到次大值&＃xff0c;就将头结点去掉&＃xff0c;即调用pop_heap()&＃xff0c;此时的头结点就是
次大值&＃xff0c;可以这样依次得到最大或者最小的几个值&＃xff01;

#include
#include
#include
#include
#include
#include
#include
using namespace std;int rand_int()
{return rand()%100;
}void print(vector &v,const char* s)
{cout<(cout," "));cout<}
bool cmp(int &a, int &b)
{if(a>b)return true;return false;
}class compare{
public:bool operator()(const int &a,const int &b){if(a};
int main()
{srand(time(NULL));vector v;generate_n(back_inserter(v),10,rand_int);print(v,"产生10个随机数");partial_sort(v.begin(),v.begin()&＃43;4,v.end());print(v,"局部递增排序");partial_sort(v.begin(),v.begin()&＃43;4,v.end(),cmp);print(v,"局部递减排序");partial_sort(v.begin(),v.begin()&＃43;4,v.end(),compare());print(v,"局部递增排序");return 0;
}


通过程序可以看到两次局部递增排序并不相同&＃xff0c;因为partial_port不是稳定排序算法。在只需要最大或最小的几个值时&＃xff0c;partial_port比其他排序算法快。

partial_sort

接受三个参数&＃xff0c;分别是区间的头&＃xff0c;中间和结尾。执行后&＃xff0c;将前面M&＃xff08;M&＃61;中间&＃xff0d;头&＃xff09;个元素有序地放在前面&＃xff0c;后面的元素肯定是比前面的大&＃xff0c;但他

们内部的次序没有保证。有序序列不包括中间参数。

nth_element
这个函数只真正排序出一个元素来&＃xff0c;就是第n个。函数有三个迭代器的输入&＃xff08;当然还可以加上一个谓词&＃xff09;&＃xff0c;执行完毕后&＃xff0c;中间位置指向的元素保证和完全排序后

这个位置的元素一致&＃xff0c;前面区间的元素都小于&＃xff08;精确地说&＃xff0c;是不大于&＃xff09;后面区间的元素。

所以要得到最大或者最小的20个元素&＃xff0c;调用稍有不同。

partial_sort(v.begin(),v.begin()&＃43;20,v.end());

nth_element(v.begin(),v.begin()&＃43;19,v.end());

其他排序请参看http://blog.csdn.net/xiaoniba10631/article/details/6727045
————————————————
版权声明&＃xff1a;本文为CSDN博主「xiaoniba10631」的原创文章&＃xff0c;遵循CC 4.0 BY-SA版权协议&＃xff0c;转载请附上原文出处链接及本声明。
原文链接&＃xff1a;https://blog.csdn.net/xiaoniba10631/article/details/6726984