排序算法
排序算法的特点是对容器的内容进行不同方式的排序，例如 Sort()。
| 函数 | 算法 |
|---|---|
| binary_search(first, last, val) | 二元搜索 |
| equal_range(first, last, val) | 判断是否相等，并返回一个区间 |
| includes(first, last, first2, last2) | 包含与 |
| lexicographical_compare(first, last, first2, last2) | 以字典排序方式做比较 |
| lower_bound(first, last, val) | 下限 |
| make_heap(first, last) | 制造一个 heap |
| max(val1, val2) | 最大值 |
| max_element(first, last) | 最大值所在位置 |
| merge(first, last, first2, last2, result) | 合并两个序列 |
| min(val1, val2) | 最小值 |
| min_element(first, last) | 最小值所在位置 |
| next_permutation(first, last) | 获得下一个排列组合 |
| nth_element(first, nth, last) | 重新排序列中第 n 个元素的左右两端 |
| partial_sort_copy(first, last, first2, last2) | 局部排序并复制到其他位置 |
| partial_sort(first, middle, last) | 局部排序 |
| pop_heap(first, last) | 从 heap 内取出一个元素 |
| prev_permutation(first, last) | 改变迭代器 first 和 last 指明范围内的元素排序，使新排列是下一个比原排列小的排列，此函数的另一个版本以谓词作为第 3 个实参 |
| push_heap(first, last) | 将一个元素压入 heap |
| set_difference(first, last, first2, last2, result) | 获得前一个排列组合 |
| set_intersection(first, last, first2, last2, result) | 交集 |
| set_symmetric_difference(first, last, first2, last2, result) | 差集 |
| set_union(first, last, first2, last2, result) | 联集 |
| sort(first, last) | 排序 |
| sort_heap(first, last) | 对 heap 排序 |
| stable_sort(first, last) | 排序并保持等值元素的相对次序 |
| upper_bound(first, last, val) | 上限 |
sort(first, last)
对迭代器 first 和 last 指明范围内的元素排序。此函数的另一个版本以谓词作为第 3 个参数。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Test_sort()
{
vector<int> int_vector;
for (size_t i = 0; i < 10; i++) int_vector.push_back(i);
random_shuffle(int_vector.begin(), int_vector.end());
cout << "Vector:";
for (int item : int_vector) cout << item << ' ';
cout << endl;
sort(int_vector.begin(), int_vector.end());
cout << "Vector:";
for (int item : int_vector) cout << item << ' ';
cout << endl;
}
| Output |
|---|
| Vector:8 1 9 2 0 5 7 3 4 6 Vector:0 1 2 3 4 5 6 7 8 9 |
partial_sort(first, middle, last)
对迭代器 first 和 last 指明范围内的元素进行排序，把排序后的前一部分元素放至序列的前一部分（由 first 和 middle 指明的范围），其余元素放在后一部分（由 middle 和 last 指明的范围）。此函数的另一版本以谓词作为第 4 个实参。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Test_partial_sort()
{
vector<int> int_vector;
for (size_t i = 0; i < 10; i++) int_vector.push_back(i);
random_shuffle(int_vector.begin(), int_vector.end());
cout << "Vector:";
for (int item : int_vector) cout << item << ' ';
cout << endl;
// 只替换排序后前5个元素
partial_sort(int_vector.begin(), int_vector.begin() + 5, int_vector.end());
cout << "Vector:";
for (int item : int_vector) cout << item << ' ';
cout << endl;
}
| Output |
|---|
| Vector:8 1 9 2 0 5 7 3 4 6 Vector:0 1 2 3 4 9 8 7 5 6 |
nth_element(first, nth, last)
在迭代器 first 和 last 指明范围的已排序元素中查找 val。如果找到值为 val 的元素，返回 true, 否则返回 false 值。此函数的另一个版本以谓词作为第 4 个实参。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Test_nth_element()
{
vector<int> int_vector;
for (size_t i = 0; i < 50; i++) int_vector.push_back(i);
random_shuffle(int_vector.begin(), int_vector.end());
cout << "Vector:";
for (int item : int_vector) cout << item << ' ';
cout << endl;
nth_element(int_vector.begin(), int_vector.begin() + 5, int_vector.end());
cout << "Vector:";
for (int item : int_vector) cout << item << ' ';
cout << endl;
}
| Output |
|---|
| Vector:34 49 17 26 21 44 35 32 20 33 41 19 48 45 3 5 6 22 14 13 23 29 39 28 46 8 2 10 25 36 4 38 27 9 7 40 1 31 47 18 11 37 24 30 0 15 12 16 42 43 Vector:0 1 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 41 33 32 40 44 49 47 34 46 37 39 35 45 36 48 38 42 43 |
merge(first, last, first2, last2, result)
把从 first 到 last 指明范围内的已排序元素与 first2 和 last2 指明范围内的已排序元素合并，并把重新排序后的元素放在从 result 开始的序列中。此函数的另一版本以谓词作为第 6 个实参。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Test_merge()
{
vector<int> int_vector;
for (size_t i = 0; i < 10; i++) int_vector.push_back(rand());
sort(int_vector.begin(), int_vector.end());
vector<int> int_vector2;
for (size_t i = 0; i < 10; i++) int_vector2.push_back(rand());
sort(int_vector2.begin(), int_vector2.end());
cout << "Vector1:";
for (int item : int_vector) cout << item << ' ';
cout << endl;
cout << "Vector2:";
for (int item : int_vector2) cout << item << ' ';
cout << endl;
vector<int> result(int_vector.size() + int_vector2.size());
// 合并必须是排序后的序列
merge(int_vector.begin(), int_vector.end(), int_vector2.begin(), int_vector2.end(), result.begin());
cout << "Vector3:";
for (int item : result) cout << item << ' ';
cout << endl;
}
| Output |
|---|
| Vector1:41 6334 11478 15724 18467 19169 24464 26500 26962 29358 Vector2:491 2995 4827 5436 5705 9961 11942 16827 23281 28145 Vector3:41 491 2995 4827 5436 5705 6334 9961 11478 11942 15724 16827 18467 19169 23281 24464 26500 26962 28145 29358 |
includes(first, last, first2, last2)
在迭代器 first 和 last 指明的范围内，如果含有一个用 first2 和 last2 指明范围的已排序序列，则返回 true 值。此函数的另一个版本以谓词作为第 5 个实参。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Test_includes()
{
vector<int> int_vector{ 2,5,12,1,53,13,23,21,3,6,7,8,8 };
sort(int_vector.begin(), int_vector.end());
vector<int> int_vector2{ 8,6,7,8 };
sort(int_vector2.begin(), int_vector2.end());
cout << "Vector:";
for (int item : int_vector) cout << item << ' ';
cout << endl;
cout << "是否包含:[6,7,8,8]" << endl;
// 必须是排序后的序列
bool is_includes = includes(int_vector.begin(), int_vector.end(), int_vector2.begin(), int_vector2.end());
cout << "结果:" << (is_includes ? "包含" : "不包含");
}
| Output |
|---|
| Vector:1 2 3 5 6 7 8 8 12 13 21 23 53 是否包含:[6,7,8,8] 结果:包含 |
