algorithm算法库学习之——划分操作和排序操作

algorithm此头文件是算法库的一部分。本篇介绍划分操作和排序操作。

划分操作
is_partitioned (C++11)	判断范围是否已按给定的谓词划分 (函数模板)
partition	将范围中的元素分为两组 (函数模板)
partition_copy (C++11)	复制一个范围，将各元素分为两组 (函数模板)
stable_partition	将元素分为两组，同时保留其相对顺序 (函数模板)
partition_point (C++11)	定位已划分范围的划分点 (函数模板)
排序操作
is_sorted (C++11)	检查范围是否已按升序排列 (函数模板)
is_sorted_until (C++11)	找出最大的有序子范围 (函数模板)
sort	将范围按升序排序 (函数模板)
partial_sort	排序一个范围的前 N 个元素 (函数模板)
partial_sort_copy	对范围内的元素进行复制并部分排序 (函数模板)
stable_sort	将范围内的元素排序，同时保持相等的元素之间的顺序 (函数模板)
nth_element	将给定的范围部分排序，确保其按给定元素划分

示例代码：

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <utility>      // std::pair
#include <vector>
#include <array>
#include <cctype>       // std::tolower
#include <string>
#include <ctime>        // std::time
#include <cstdlib>      // std::rand, std::srand
#include <random>       // std::default_random_engine
#include <chrono>       // std::chrono::system_clockbool IsOdd5(int i) { return ((i % 2) == 1); }bool myfunction7(int i, int j) { return (i < j); }struct myclass10{bool operator() (int i, int j) { return (i < j); }
} myobject10;bool compare_as_ints(double i, double j)
{return (int(i) < int(j));
}int main()
{// is_partitioned algorithm examplestd::array<int, 7> foo{ 1,2,3,4,5,6,7 };// print contents:std::cout << "foo:"; for (int& x : foo) std::cout << ' ' << x;if (std::is_partitioned(foo.begin(), foo.end(), IsOdd5))std::cout << " (partitioned)\n";elsestd::cout << " (not partitioned)\n";// partition array:std::partition(foo.begin(), foo.end(), IsOdd5);// print contents again:std::cout << "foo:"; for (int& x : foo) std::cout << ' ' << x;if (std::is_partitioned(foo.begin(), foo.end(), IsOdd5))std::cout << " (partitioned)\n";elsestd::cout << " (not partitioned)\n";// partition algorithm examplestd::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 9std::vector<int>::iterator bound;bound = std::partition(myvector.begin(), myvector.end(), IsOdd5);// 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';// stable_partition examplestd::vector<int> myvector2;// set some values:for (int i = 1; i < 10; ++i) myvector2.push_back(i); // 1 2 3 4 5 6 7 8 9std::vector<int>::iterator bound2;bound2 = std::stable_partition(myvector2.begin(), myvector2.end(), IsOdd5);// print out content:std::cout << "odd elements:";for (std::vector<int>::iterator it = myvector2.begin(); it != bound2; ++it)std::cout << ' ' << *it;std::cout << '\n';std::cout << "even elements:";for (std::vector<int>::iterator it = bound2; it != myvector2.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';// partition_copy examplestd::vector<int> foo2{ 1,2,3,4,5,6,7,8,9 };std::vector<int> odd2, even2;// resize vectors to proper size:unsigned n = std::count_if(foo2.begin(), foo2.end(), IsOdd5);odd2.resize(n); even2.resize(foo2.size() - n);// partition:std::partition_copy(foo2.begin(), foo2.end(), odd2.begin(), even2.begin(), IsOdd5);// print contents:std::cout << "odd2: ";  for (int& x : odd2)  std::cout << ' ' << x; std::cout << '\n';std::cout << "even2: "; for (int& x : even2) std::cout << ' ' << x; std::cout << '\n';// partition_point examplestd::vector<int> foo3{ 1,2,3,4,5,6,7,8,9 };std::vector<int> odd3;std::partition(foo3.begin(), foo3.end(), IsOdd5);auto it = std::partition_point(foo3.begin(), foo3.end(), IsOdd5);odd3.assign(foo3.begin(), it);// print contents of odd3:std::cout << "odd3:";for (int& x : odd3) std::cout << ' ' << x;std::cout << '\n';// sort algorithm exampleint myints4[] = { 32,71,12,45,26,80,53,33 };std::vector<int> myvector4(myints4, myints4 + 8);               // 32 71 12 45 26 80 53 33// using default comparison (operator <):std::sort(myvector4.begin(), myvector4.begin() + 4);           //(12 32 45 71)26 80 53 33// using function as compstd::sort(myvector4.begin() + 4, myvector4.end(), myfunction7); // 12 32 45 71(26 33 53 80)// using object as compstd::sort(myvector4.begin(), myvector4.end(), myobject10);     //(12 26 32 33 45 53 71 80)// print out content:std::cout << "myvector4 contains:";for (std::vector<int>::iterator it = myvector4.begin(); it != myvector4.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';// stable_sort exampledouble mydoubles[] = { 3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58 };std::vector<double> myvector5;myvector5.assign(mydoubles, mydoubles + 8);std::cout << "using default comparison:";std::stable_sort(myvector5.begin(), myvector5.end());for (std::vector<double>::iterator it = myvector5.begin(); it != myvector5.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';myvector5.assign(mydoubles, mydoubles + 8);std::cout << "using 'compare_as_ints' :";std::stable_sort(myvector5.begin(), myvector5.end(), compare_as_ints);for (std::vector<double>::iterator it = myvector5.begin(); it != myvector5.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';// partial_sort exampleint myints6[] = { 9,8,7,6,5,4,3,2,1 };std::vector<int> myvector6(myints6, myints6 + 9);// using default comparison (operator <):std::partial_sort(myvector6.begin(), myvector6.begin() + 5, myvector6.end());// using function as compstd::partial_sort(myvector6.begin(), myvector6.begin() + 5, myvector6.end(), myfunction7);// print out content:std::cout << "myvector6 contains:";for (std::vector<int>::iterator it = myvector6.begin(); it != myvector6.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';// partial_sort_copy exampleint myints7[] = { 9,8,7,6,5,4,3,2,1 };std::vector<int> myvector7(5);// using default comparison (operator <):std::partial_sort_copy(myints7, myints7 + 9, myvector7.begin(), myvector7.end());// using function as compstd::partial_sort_copy(myints7, myints7 + 9, myvector7.begin(), myvector7.end(), myfunction7);// print out content:std::cout << "myvector7 contains:";for (std::vector<int>::iterator it = myvector7.begin(); it != myvector7.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';// is_sorted examplestd::array<int, 4> foo4{ 2,4,1,3 };do {// try a new permutation:std::prev_permutation(foo4.begin(), foo4.end());// print range:std::cout << "foo4:";for (int& x : foo4) std::cout << ' ' << x;std::cout << '\n';} while (!std::is_sorted(foo4.begin(), foo4.end()));std::cout << "the range is sorted!\n";// is_sorted_until examplestd::array<int, 4> foo5{ 2,4,1,3 };std::array<int, 4>::iterator it5;do {// try a new permutation:std::prev_permutation(foo5.begin(), foo5.end());// print range:std::cout << "foo5:";for (int& x : foo5) std::cout << ' ' << x;it5 = std::is_sorted_until(foo5.begin(), foo5.end());std::cout << " (" << (it5 - foo5.begin()) << " elements sorted)\n";} while (it5 != foo5.end());std::cout << "the range is sorted!\n";// nth_element examplestd::vector<int> myvector8;// set some values:for (int i = 1; i < 10; i++) myvector8.push_back(i);   // 1 2 3 4 5 6 7 8 9std::random_shuffle(myvector8.begin(), myvector8.end());// using default comparison (operator <):std::nth_element(myvector8.begin(), myvector8.begin() + 5, myvector8.end());// using function as compstd::nth_element(myvector8.begin(), myvector8.begin() + 5, myvector8.end(), myfunction7);// print out content:std::cout << "myvector8 contains:";for (std::vector<int>::iterator it = myvector8.begin(); it != myvector8.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

运行结果：

参考：

https://cplusplus.com/reference/algorithm/

标准库标头 <algorithm> - cppreference.com