1. 简介
| 函数 |
作用 |
文档 |
sort(beg,end) |
默认升序重新排列元素 |
sort() |
sort(beg,end,comp) |
使用函数comp代替比较操作符执行sort()。 |
sort() |
partition(beg,end,pred) |
元素重新排序，使用pred函数，把结果为true的元素放在结果为false的元素之前。 |
partition() |
stable_sort(beg,end) |
与sort()类似，保留相等元素之间的顺序关系。 |
stable_sort() |
stable_sort(beg,end,pred) |
使用函数pred代替比较操作符执行stable_sort()。 |
stable_sort() |
stable_partition(beg,end) |
与partition()类似，保留容器中的相对顺序。 |
stable_partition() |
stable_partition(beg,end,pred) |
使用函数pred代替比较操作符执行stable_partition()。 |
stable_partition() |
partial_sort(beg,mid,end) |
部分排序，被排序元素个数放到[beg,end)内。 |
partial_sort() |
partial_sort(beg,mid,end,comp) |
使用函数comp代替比较操作符执行partial_sort()。 |
partial_sort() |
partial_sort_copy(beg1,end1,beg2,end2) |
与partial_sort()类似，只是将[beg1,end1)排序的序列复制到[beg2,end2)。 |
partial_sort_copy() |
partial_sort_copy(beg1,end1,beg2,end2,comp) |
使用函数comp代替比较操作符执行partial_sort_copy()。 |
partial_sort_copy() |
nth_element(beg,nth,end) |
单个元素序列重新排序，使所有小于第n个元素的元素都出现在它前面，而大于它的都出现在后面。 |
nth_element() |
nth_element(beg,nth,end,comp) |
使用函数comp代替比较操作符执行nth_element()。 |
nth_element() |
2. 示例代码
// sort algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::sort
#include <vector> // std::vector
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};
std::vector<int> myvector (myints, myints+8); // 32 71 12 45 26 80 53 33
// using default comparison (operator <):
std::sort (myvector.begin(), myvector.begin()+4); //(12 32 45 71)26 80 53 33
// using function as comp
std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)
// using object as comp
std::sort (myvector.begin(), myvector.end(), myobject); //(12 26 32 33 45 53 71 80)
// print out content:
std::cout << "myvector contains:";
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
// partition algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::partition
#include <vector> // std::vector
bool IsOdd (int i) { return (i%2)==1; }
int main () {
std::vector<int> myvector;
// set some values:
for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
std::vector<int>::iterator bound;
bound = std::partition (myvector.begin(), myvector.end(), IsOdd);
// print out content:
std::cout << "odd elements:";
for (std::vector<int>::iterator it=myvector.begin(); it!=bound; ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "even elements:";
for (std::vector<int>::iterator it=bound; it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
// stable_sort example
#include <iostream> // std::cout
#include <algorithm> // std::stable_sort
#include <vector> // std::vector
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};
std::vector<double> myvector;
myvector.assign(mydoubles,mydoubles+8);
std::cout << "using default comparison:";
std::stable_sort (myvector.begin(), myvector.end());
for (std::vector<double>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
myvector.assign(mydoubles,mydoubles+8);
std::cout << "using 'compare_as_ints' :";
std::stable_sort (myvector.begin(), myvector.end(), compare_as_ints);
for (std::vector<double>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
// stable_partition example
#include <iostream> // std::cout
#include <algorithm> // std::stable_partition
#include <vector> // std::vector
bool IsOdd (int i) { return (i%2)==1; }
int main () {
std::vector<int> myvector;
// set some values:
for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
std::vector<int>::iterator bound;
bound = std::stable_partition (myvector.begin(), myvector.end(), IsOdd);
// print out content:
std::cout << "odd elements:";
for (std::vector<int>::iterator it=myvector.begin(); it!=bound; ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "even elements:";
for (std::vector<int>::iterator it=bound; it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
// partial_sort example
#include <iostream> // std::cout
#include <algorithm> // std::partial_sort
#include <vector> // std::vector
bool myfunction (int i,int j) { return (i<j); }
int main () {
int myints[] = {9,8,7,6,5,4,3,2,1};
std::vector<int> myvector (myints, myints+9);
// using default comparison (operator <):
std::partial_sort (myvector.begin(), myvector.begin()+5, myvector.end());
// using function as comp
std::partial_sort (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);
// print out content:
std::cout << "myvector contains:";
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
// partial_sort_copy example
#include <iostream> // std::cout
#include <algorithm> // std::partial_sort_copy
#include <vector> // std::vector
bool myfunction (int i,int j) { return (i<j); }
int main () {
int myints[] = {9,8,7,6,5,4,3,2,1};
std::vector<int> myvector (5);
// using default comparison (operator <):
std::partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end());
// using function as comp
std::partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end(), myfunction);
// print out content:
std::cout << "myvector contains:";
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
// nth_element example
#include <iostream> // std::cout
#include <algorithm> // std::nth_element, std::random_shuffle
#include <vector> // std::vector
bool myfunction (int i,int j) { return (i<j); }
int main () {
std::vector<int> myvector;
// set some values:
for (int i=1; i<10; i++) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
std::random_shuffle (myvector.begin(), myvector.end());
// using default comparison (operator <):
std::nth_element (myvector.begin(), myvector.begin()+5, myvector.end());
// using function as comp
std::nth_element (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);
// print out content:
std::cout << "myvector contains:";
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
3. 练习
- 使用
nth_element()实现快速排序。
template<class RandomAccessIt>
void quicksort(RandomAccessIt first,RandomAccessIt last);
