STL algorithm算法partial_sort,partial_sort_copy(42)

partial_sort原型：

std::partial_sort

default (1)custom (2)

template <class RandomAccessIterator>
  void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
                     RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
  void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
                     RandomAccessIterator last, Compare comp);

该函数是的将范围内最小的(middle-frist)个元素放到最前面并且排序（也就是调用该函数之后first-middle之间的元素是有序的，但是middle-last的则不是）。

使用operator<进行比较。

该函数主要是找出前n个最值，并对其进行排序！

一个简单的例子：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	vector<int> vi{1,8,9,6,7,8,4,5,6,3,2};
	cout<<"vi=";
	for(int i:vi)
		cout<<i<<" ";
	cout<<endl;
	partial_sort(vi.begin(),vi.begin()+4,vi.end());
	cout<<"partial_sort(vi.begin(),vi.begin()+4,vi.end())"<<endl;
	cout<<"vi=";
	for(int i:vi)
		cout<<i<<" ";
	cout<<endl;
}

运行截图：

可以看到，前四个最小的进行了排序，后面的并没有排序，其原理是堆排序！

partial_sort_copy原型：

std::partial_sort_copy

default (1) custom (2)

template <class InputIterator, class RandomAccessIterator>
  RandomAccessIterator
    partial_sort_copy (InputIterator first,InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last);

template <class InputIterator, class RandomAccessIterator, class Compare>
  RandomAccessIterator
    partial_sort_copy (InputIterator first,InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last, Compare comp);

该函数是对first-last范围内的元素排序并存放到result_first,result_last里面。

first-last内的元素不会被改变。

result_first,result_last内的空间应足以容纳所有的元素，否则会发送类似截断的行为，即后面的会被丢弃。

一个简单的例子：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	vector<int> vi{1,8,9,6,7,8,4,5,6,3,2};
	vector<int> v2(15);
	cout<<"vi=";
	for(int i:vi)
		cout<<i<<" ";
	cout<<endl;
	partial_sort_copy(vi.begin(),vi.end(),v2.begin(),v2.end());
	cout<<"partial_sort_copy(vi.begin(),vi.end(),v2.begin(),v2.end())"<<endl;
	cout<<"vi=";
	for(int i:vi)
		cout<<i<<" ";
	cout<<endl;
	cout<<"v2=";
	for(int i:v2)
		cout<<i<<" ";
	cout<<endl;
	
}

运行截图：

——————————————————————————————————————————————————————————————————

//写的错误或者不好的地方请多多指导，可以在下面留言或者点击左上方邮件地址给我发邮件，指出我的错误以及不足，以便我修改，更好的分享给大家，谢谢。

转载请注明出处：http://blog.csdn.net/qq844352155

author:天下无双

Email:[e-mail]

2014-9-22

于GDUT

——————————————————————————————————————————————————————————————————