STL之partial"/>
STL之partial
分类: STL 2011-08-28 16:43 709人阅读 评论(0) 收藏 举报 算法 class null partial_sort(beg,mid,end)
partial_sort(beg,mid,end,comp)
对mid-beg个元素进行排序,也就是说,如果migd-beg等于42,则该函数将有序次序中的最小值元素放在序列中
的前42个位置。partial_sort完成之后,从beg到mid(但不包括mid)范围内的元素时有序的,已排序范围内没有
元素大于mid之后的元素。未排序元素之间的次序是未指定的。
例如:
有一个赛跑成绩的集合,我们想知道前三名的成绩但并不关心其他名次的次序,可以这样对这个序列进行排序。
partial_sort(scores.begin(),scores.begin()+3,scores.end());
那么paitical_sort的原理是什么呢?是堆排序!
首先创建一个堆,得到最大值。如果要得到次大值,就将头结点去掉,即调用pop_heap(),此时的头结点就是
次大值,可以这样依次得到最大或者最小的几个值!
[html] view plain copy
- #include <vector>
- #include <iterator>
- #include <iostream>
- #include <algorithm>
- #include <functional>
- #include <cstdlib>
- #include <time.h>
- using namespace std;
- int rand_int()
- {
- return rand()%100;
- }
- void print(vector<int> &v,const char* s)
- {
- cout<<s<<endl;
- copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
- cout<<endl;
- }
- 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<b)
- return true;
- return false;
- }
- };
- int main()
- {
- srand(time(NULL));
- vector<int> v;
- generate_n(back_inserter(v),10,rand_int);
- print(v,"产生10个随机数");
- partial_sort(v.begin(),v.begin()+4,v.end());
- print(v,"局部递增排序");
- partial_sort(v.begin(),v.begin()+4,v.end(),cmp);
- print(v,"局部递减排序");
- partial_sort(v.begin(),v.begin()+4,v.end(),compare());
- print(v,"局部递增排序");
- return 0;
- }
通过程序可以看到两次局部递增排序并不相同,因为partial_port不是稳定排序算法。在只需要最大或最小的几个值时,partial_port比其他排序算法快。
partial_sort
接受三个参数,分别是区间的头,中间和结尾。执行后,将前面M(M=中间-头)个元素有序地放在前面,后面的元素肯定是比前面的大,但他
们内部的次序没有保证。有序序列不包括中间参数。
nth_element
这个函数只真正排序出一个元素来,就是第n个。函数有三个迭代器的输入(当然还可以加上一个谓词),执行完毕后,中间位置指向的元素保证和完全排序后
这个位置的元素一致,前面区间的元素都小于(精确地说,是不大于)后面区间的元素。
所以要得到最大或者最小的20个元素,调用稍有不同。
partial_sort(v.begin(),v.begin()+20,v.end());
nth_element(v.begin(),v.begin()+19,v.end());
其他排序请参看
更多推荐
STL之partial
发布评论