STL之partial

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

1. #include <vector>  
2. #include <iterator>  
3. #include <iostream>  
4. #include <algorithm>  
5. #include <functional>  
6. #include <cstdlib>  
7. #include <time.h>  
8. using namespace std;  
9.   
10. int rand_int()  
11. {  
12.     return rand()%100;  
13. }  
14.   
15. void print(vector<int> &v,const char* s)  
16. {  
17.     cout<<s<<endl;  
18.     copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));  
19.     cout<<endl;  
20. }  
21.   
22. bool cmp(int &a, int &b)  
23. {  
24.     if(a>b)  
25.         return true;  
26.     return false;  
27. }  
28.   
29. class compare{  
30. public:  
31.     bool operator()(const int &a,const int &b)  
32.     {  
33.         if(a<b)  
34.             return true;  
35.         return false;  
36.     }  
37. };  
38.   
39. int main()  
40. {  
41.     srand(time(NULL));  
42.     vector<int> v;  
43.     generate_n(back_inserter(v),10,rand_int);  
44.     print(v,"产生10个随机数");  
45.   
46.     partial_sort(v.begin(),v.begin()+4,v.end());  
47.     print(v,"局部递增排序");  
48.   
49.     partial_sort(v.begin(),v.begin()+4,v.end(),cmp);  
50.     print(v,"局部递减排序");  
51.   
52.     partial_sort(v.begin(),v.begin()+4,v.end(),compare());  
53.     print(v,"局部递增排序");  
54.   
55.     return 0;  
56. }  

通过程序可以看到两次局部递增排序并不相同，因为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());

其他排序请参看