排序操作:
is_sorted C++11
|
检测指定范围是否已排序 |
is_sorted_until C++11
|
返回最大已排序子范围 |
nth_element
|
部份排序指定范围中的元素,使得范围按给定位置处的元素划分 |
partial_sort
|
部份排序 |
partial_sort_copy
|
拷贝部分排序的结果 |
sort
|
排序 |
stable_sort
|
稳定排序 |
is_sorted
检测指定范围是否已排序
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// is_sorted example
#include <iostream> // std::cout #include <algorithm> // std::is_sorted, std::prev_permutation #include <array> // std::array int main () { std::array<int,4> foo {2,4,1,3}; do { // try a new permutation: std::prev_permutation(foo.begin(),foo.end()); // print range: std::cout << "foo:"; for (int& x:foo) std::cout << ‘ ‘ << x; std::cout << ‘\n‘; } while (!std::is_sorted(foo.begin(),foo.end())); std::cout << "the range is sorted!\n"; return 0; } |
输出:
2 3 4 5 6 7 8 9 10 11 |
foo: 2 3 4 1
foo: 2 3 1 4 foo: 2 1 4 3 foo: 2 1 3 4 foo: 1 4 3 2 foo: 1 4 2 3 foo: 1 3 4 2 foo: 1 3 2 4 foo: 1 2 4 3 foo: 1 2 3 4 the range is sorted! |
is_sorted_until
返回最大已排序子范围
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// is_sorted_until example
#include <iostream> // std::cout #include <algorithm> // std::is_sorted_until, std::prev_permutation #include <array> // std::array int main () { std::array<int,4> foo {2,4,1,3}; std::array<int,4>::iterator it; do { // try a new permutation: std::prev_permutation(foo.begin(),foo.end()); // print range: std::cout << "foo:"; for (int& x:foo) std::cout << ‘ ‘ << x; it=std::is_sorted_until(foo.begin(),foo.end()); std::cout << " (" << (it-foo.begin()) << " elements sorted)\n"; } while (it!=foo.end()); std::cout << "the range is sorted!\n"; return 0; } |
输出:
2 3 4 5 6 7 8 9 10 11 |
foo: 2 3 4 1 (3 elements sorted)
foo: 2 3 1 4 (2 elements sorted) foo: 2 1 4 3 (1 elements sorted) foo: 2 1 3 4 (1 elements sorted) foo: 1 4 3 2 (2 elements sorted) foo: 1 4 2 3 (2 elements sorted) foo: 1 3 4 2 (3 elements sorted) foo: 1 3 2 4 (2 elements sorted) foo: 1 2 4 3 (3 elements sorted) foo: 1 2 3 4 (4 elements sorted) the range is sorted! |
nth_element
部份排序指定范围中的元素,使得范围按给定位置处的元素划分
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// 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; } |
输出:
|
myvector contains: 3 1 4 2 5 6 9 7 8
|
partial_sort
部份排序
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// 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; } |
输出:
|
myvector contains: 1 2 3 4 5 9 8 7 6
|
partial_sort_copy
拷贝部分排序的结果
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// 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; } |
输出:
|
myvector contains: 1 2 3 4 5
|
sort
排序
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// 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; } |
输出:
|
myvector contains: 12 26 32 33 45 53 71 80
|
stable_sort
稳定排序
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// 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; } |
输出:
2 |
using default comparison: 1.32 1.41 1.62 1.73 2.58 2.72 3.14 4.67
using ‘compare_as_ints‘ : 1.41 1.73 1.32 1.62 2.72 2.58 3.14 4.67 |
特别说明:函数的中文释义来自:http://classfoo.cn/cpp/head/76573_319/,例子来自:http://www.cplusplus.com/reference/algorithm/