STL算法(Algorithms):排序

一、sort：对一定范围内的所有元素排序

原型：

template <class RandomAccessIterator>

void sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>

void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
例子代码：

// sort algorithm example

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

bool myfunction (int i,int j) { return (i<j); }

struct myclass {

bool operator() (int i,int j) { return (i<j);}

} myobject;

int main () {

int myints[] = {32,71,12,45,26,80,53,33};

vector<int> myvector (myints, myints+8);// 32 71 12 45 26 80 53 33

vector<int>::iterator it;

// using default comparison (operator <):

sort (myvector.begin(), myvector.begin()+4);//(12 32 45 71)26 80 53 33

// using function as comp

sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

// using object as comp

sort (myvector.begin(), myvector.end(), myobject);//(12 26 32 33 45 53 71 80)

// print out content:

cout << "myvector contains:";

for (it=myvector.begin(); it!=myvector.end(); ++it)

cout << " " << *it;

cout << endl;

return 0;

}

二、stable_sort：归并排序

原型：

template <class RandomAccessIterator>

void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>

void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,

Compare comp );
例子代码：

// stable_sort example

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

bool compare_as_ints (double i,double j)

{

return (int(i)<int(j));

}

int main () {

double mydoubles[] = {3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58};

vector<double> myvector;

vector<double>::iterator it;

myvector.assign(mydoubles,mydoubles+8);

cout << "using default comparison:";

stable_sort (myvector.begin(), myvector.end());

for (it=myvector.begin(); it!=myvector.end(); ++it)

cout << " " << *it;

myvector.assign(mydoubles,mydoubles+8);

cout << "\nusing 'compare_as_ints' :";

stable_sort (myvector.begin(), myvector.end(), compare_as_ints);

for (it=myvector.begin(); it!=myvector.end(); ++it)

cout << " " << *it;

cout << endl;

return 0;

}

三、partial_sort_copy：对序列中的某个范围的元素进行排序(部分排序)

原型：

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 );
示例代码：

// partial_sort example
#include <iostream>
#include <algorithm>
#include <vector>
usingnamespacestd;

boolmyfunction (inti,intj) {return(i<j); }

intmain () {
intmyints[] = {9,8,7,6,5,4,3,2,1};
vector<int> myvector (myints, myints+9);
vector<int>::iterator it;

// using default comparison (operator <):
partial_sort (myvector.begin(), myvector.begin()+5, myvector.end());

// using function as comp
partial_sort (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);

// print out content:
cout <<"myvector contains:";
for(it=myvector.begin(); it!=myvector.end(); ++it)
cout <<" "<< *it;

cout << endl;

return0;
}

四、partial_sort_copy：部分排序后拷贝
原型：

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 );

示例：

// partial_sort_copy example#include <iostream>#include <algorithm>#include <vector>using namespace std;bool myfunction (int i,int j) { return (i<j); }int main () {  int myints[] = {9,8,7,6,5,4,3,2,1};  vector<int> myvector (5);  vector<int>::iterator it;  // using default comparison (operator <):  partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end());  // using function as comp  partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end(), myfunction);  // print out content:  cout << "myvector contains:";  for (it=myvector.begin(); it!=myvector.end(); ++it)    cout << " " << *it;  cout << endl;  return 0;}
五、nth_element：使第n个元素处在序列中的第n个位置，并在这个元素前都是比这个元素小的，
这个元素后面都是比这个这元素大，但是这前后两个序列并不一定都是有序的(排过序)；
原型： 
template <class RandomAccessIterator>
 void nth_element ( RandomAccessIterator first, RandomAccessIterator nth,
 RandomAccessIterator last );
template <class RandomAccessIterator, class Compare>
 void nth_element ( RandomAccessIterator first, RandomAccessIterator nth,
 RandomAccessIterator last, Compare comp );
例子代码：

// nth_element example#include <iostream>#include <algorithm>#include <vector>using namespace std;bool myfunction (int i,int j) { return (i<j); }int main () {  vector<int> myvector;  vector<int>::iterator it;  // set some values:  for (int i=1; i<10; i++) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9  random_shuffle (myvector.begin(), myvector.end());  // using default comparison (operator <):  nth_element (myvector.begin(), myvector.begin()+5, myvector.end());  // using function as comp  nth_element (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);  // print out content:  cout << "myvector contains:";  for (it=myvector.begin(); it!=myvector.end(); ++it)    cout << " " << *it;  cout << endl;  return 0;}