概述
算法库提供大量用途的函数(例如查找、排序、计数、操作),它们在元素范围上操作。注意范围定义为 [first, last) ,其中 last 指代要查询或修改的最后元素的后一个元素。
大部分操作定义于头文件 <algorithm>
排序
参考:排序算法
排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 |
---|---|---|---|---|
冒泡排序 | O(n2) | O(n2) | O(1) | 稳定 |
选择排序 | O(n2) | O(n2) | O(1) | 数组不稳定、链表稳定 |
插入排序 | O(n2) | O(n2) | O(1) | 稳定 |
快速排序 | O(n*log2n) | O(n2) | O(log2n) | 不稳定 |
堆排序 | O(n*log2n) | O(n*log2n) | O(1) | 不稳定 |
归并排序 | O(n*log2n) | O(n*log2n) | O(n) | 稳定 |
希尔排序 | O(n*log2n) | O(n2) | O(1) | 不稳定 |
计数排序 | O(n+m) | O(n+m) | O(n+m) | 稳定 |
桶排序 | O(n) | O(n) | O(m) | 稳定 |
基数排序 | O(k*n) | O(n2) | 稳定 |
- k:代表数值中的 “数位” 个数
- n:代表数据规模
- m:代表数据的最大值减最小值
查找
查找算法 | 平均时间复杂度 | 空间复杂度 | 查找条件 |
---|---|---|---|
顺序查找 | O(n) | O(1) | 无序或有序 |
二分查找(折半查找) | O(log2n) | O(1) | 有序 |
插值查找 | O(log2(log2n)) | O(1) | 有序 |
斐波那契查找 | O(log2n) | O(1) | 有序 |
哈希查找 | O(1) | O(n) | 无序或有序 |
二叉查找树(二叉搜索树查找) | O(log2n) | ||
红黑树 | O(log2n) | ||
2-3树 | O(log2n - log3n) | ||
B树/B+树 | O(log2n) |
图搜索算法
图搜索算法 | 数据结构 | 遍历时间复杂度 | 空间复杂度 |
---|---|---|---|
BFS广度优先搜索 | 邻接矩阵 邻接链表 |
O(|v|2) O(|v|+|E|) |
O(|v|2) O(|v|+|E|) |
DFS深度优先搜索 | 邻接矩阵 邻接链表 |
O(|v|2) O(|v|+|E|) |
O(|v|2) O(|v|+|E|) |
其他算法
算法 | 思想 | 应用 |
---|---|---|
分治法 | 把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并 | 循环赛日程安排问题、排序算法(快速排序、归并排序) |
动态规划 | 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法,适用于有重叠子问题和最优子结构性质的问题 | 背包问题、斐波那契数列 |
贪心法 | 一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法 | 旅行推销员问题(最短路径问题)、最小生成树、哈夫曼编码 |
不修改序列的操作
不修改序列的操作 | 说明 |
---|---|
all_of(C++11) any_of(C++11) none_of(C++11) |
检查一定范围之内,是否全部、存在或不存在元素使得谓词为true (函数模板) |
for_each | 将一个函数应用于某一范围的元素 (函数模板) |
for_each_n(C++17) | 应用函数对象到序列的首 n 个元素 (函数模板) |
count count_if |
返回满足指定判别的元素数 (函数模板) |
mismatch | 查找两个范围第一个不同元素的位置 (函数模板) |
find find_if find_if_not(C++11) |
查找满足特定条件的第一个元素 (函数模板) |
find_end | 查找一定范围内最后出现的元素序列 (函数模板) |
find_first_of | 查找元素集合中的任意元素 (函数模板) |
adjacent_find | 查找彼此相邻的两个相同(或其它的关系)的元素 (函数模板) |
search | 查找一个元素区间 (函数模板) |
search_n | 在区间中搜索连续一定数目次出现的元素 (函数模板) |
修改序列的操作
修改序列的操作 | 说明 |
---|---|
copycopy_if(C++11) | 将某一范围的元素复制到一个新的位置 (函数模板) |
copy_n(C++11) | 复制一定数目的元素到新的位置 (函数模板) |
copy_backward | 按从后往前的顺序复制一个范围内的元素 (函数模板) |
move(C++11) | 将某一范围的元素移动到一个新的位置 (函数模板) |
move_backward(C++11) | 按从后往前的顺序移动某一范围的元素到新的位置 (函数模板) |
fill | 将一个值赋给一个范围内的元素 (函数模板) |
fill_n | 将一个值赋给一定数目的元素 (函数模板) |
transform | 将一个函数应用于某一范围的元素 (函数模板) |
generate | 赋值相继的函数调用结果给范围中的每个元素 (函数模板) |
generate_n | 赋值相继的函数调用结果给范围中的 N 个元素 (函数模板) |
removeremove_if | 移除满足特定标准的元素 (函数模板) |
remove_copy remove_copy_if |
复制一个范围内不满足特定条件的元素 (函数模板) |
replace replace_if |
将所有满足特定条件的元素替换为另一个值 (函数模板) |
replace_copy replace_copy_if |
复制一个范围内的元素,并将满足特定条件的元素替换为另一个值 (函数模板) |
swap | 交换两个对象的值 (函数模板) |
swap_ranges | 交换两个范围的元素 (函数模板) |
iter_swap | 交换两个迭代器所指向的元素 (函数模板) |
reverse | 将区间内的元素颠倒顺序 (函数模板) |
reverse_copy | 将区间内的元素颠倒顺序并复制 (函数模板) |
shift_left shift_right(C++20) |
迁移范围中的元素 (函数模板) |
rotate | 将区间内的元素旋转 (函数模板) |
rotate_copy | 将区间内的元素旋转并复制 (函数模板) |
random_shuffle | 将范围内的元素随机重新排序 (函数模板) |
sample(C++17) | 从一个序列中随机选择 n 个元素 (函数模板) |
unique | 删除区间内连续重复的元素 (函数模板) |
unique_copy | 删除区间内连续重复的元素并复制 (函数模板) |
划分操作
划分操作 | 说明 |
---|---|
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 | 将给定的区间部分排序,确保区间被给定的元素划分 (函数模板) |
二分搜索操作(在已排序范围上)
二分搜索操作(在已排序范围上) | 说明 |
---|---|
lower_bound | 返回指向第一个不小于给定值的元素的迭代器 (函数模板) |
upper_bound | 返回指向第一个大于给定值的元素的迭代器 (函数模板) |
binary_search | 判断一个元素是否在区间内 (函数模板) |
equal_range | 返回匹配特定键值的元素区间 (函数模板) |
集合操作(在已排序范围上)
集合操作(在已排序范围上) | 说明 |
---|---|
merge | 合并两个已排序的区间 (函数模板) |
inplace_merge | 就地合并两个有序的区间 (函数模板) |
includes | 如果一个集合是另外一个集合的子集则返回true (函数模板) |
set_difference | 计算两个集合的差集 (函数模板) |
set_intersection | 计算两个集合的交集 (函数模板) |
set_symmetric_difference | 计算两个集合的对称差 (函数模板) |
set_union | 计算两个集合的并集 (函数模板) |
堆操作
堆操作 | 说明 |
---|---|
is_heap | 检查给定的区间是否为一个堆 (函数模板) |
is_heap_until(C++11) | 查找区间中为堆的最大子区间 (函数模板) |
make_heap | 根据区间内的元素创建出一个堆 (函数模板) |
push_heap | 将元素加入到堆 (函数模板) |
pop_heap | 将堆中的最大元素删除 (函数模板) |
sort_heap | 将堆变成一个排好序的区间 (函数模板) |
最小/最大操作
最小/最大操作 | 说明 |
---|---|
max | 返回两个元素中的较大者 (函数模板) |
max_element | 返回区间内的最大元素 (函数模板) |
min | 返回两个元素中的较小者 (函数模板) |
min_element | 返回区间内的最小元素 (函数模板) |
minmax(C++11) | 返回两个元素中的的较大者和较小者 (函数模板) |
minmax_element(C++11) | 返回区间内的最小元素和最大元素 (函数模板) |
clamp(C++17) | 在一对边界值间夹住一个值 (函数模板) |
比较操作
比较操作 | 说明 |
---|---|
equal | 确定两个元素集合是否是相同的 (函数模板) |
lexicographical_compare | 如果按字典顺序一个区间小于另一个区间,返回true (函数模板) |
compare_3way(C++20) | 用三路比较比较二个值 (函数模板) |
lexicographical_compare_3way(C++20) | 用三路比较比价二个范围 (函数模板) |
排列操作
排列操作 | 说明 |
---|---|
is_permutation(C++11) | 判断一个序列是否为另一个序列的排列组合 (函数模板) |
next_permutation | 按字典顺序产生区间内元素下一个较大的排列组合 (函数模板) |
prev_permutation | 按字典顺序产生区间内元素下一个较小的排列组合 (函数模板) |
数值运算
数值运算 | 说明 |
---|---|
iota(C++11) | 用从起始值开始连续递增的值填充区间 (函数模板) |
accumulate | 计算区间内元素的和 (函数模板) |
inner_product | 计算两个区间元素的内积 (函数模板) |
adjacent_difference | 计算区间内相邻元素之间的差 (函数模板) |
partial_sum | 计算区间内元素的部分和 (函数模板) |
reduce(C++17) | 类似 std::accumulate ,除了以乱序 (函数模板) |
exclusive_scan(C++17) | 类似 std::partial_sum ,第 i 个和中排除第 i 个输入 (函数模板) |
inclusive_scan(C++17) | 类似 std::partial_sum ,第 i 个和中包含第 i 个输入 (函数模板) |
transform_reduce(C++17) | 应用函数对象,然后以乱序规约 (函数模板) |
transform_exclusive_scan(C++17) | 应用函数对象,然后进行排除扫描 (函数模板) |
transform_inclusive_scan(C++17) | 应用函数对象,然后进行包含扫描 (函数模板) |
未初始化内存上的操作
未初始化内存上的操作 | 说明 |
---|---|
uninitialized_copy | 将范围内的对象复制到未初始化的内存区域 (函数模板) |
uninitialized_copy_n(C++11) | 将指定数量的对象复制到未初始化的内存区域 (函数模板) |
uninitialized_fill | 复制一个对象到以范围定义的未初始化内存区域 (函数模板) |
uninitialized_fill_n | 复制一个对象到以起点和计数定义的未初始化内存区域 (函数模板) |
uninitialized_move(C++17) | 移动一个范围的对象到未初始化的内存区域 (函数模板) |
uninitialized_move_n(C++17) | 移动一定数量对象到未初始化内存区域 (函数模板) |
uninitialized_default_construct(C++17) | 在范围所定义的未初始化的内存区域以默认初始化构造对象 (函数模板) |
uninitialized_default_construct_n(C++17) | 在起始和计数所定义的未初始化内存区域用默认初始化构造对象 (函数模板) |
uninitialized_value_construct(C++17) | 在范围所定义的未初始化内存中用值初始化构造对象 (函数模板) |
uninitialized_value_construct_n(C++17) | 在起始和计数所定义的未初始化内存区域以值初始化构造对象 (函数模板) |
destroy_at(C++17) | 销毁在给定地址的对象 (函数模板) |
destroy(C++17) | 销毁一个范围中的对象 (函数模板) |
destroy_n(C++17) | 销毁范围中一定数量的对象 (函数模板) |
C 库
C 库 | 说明 |
---|---|
定义于头文件 |
说明 |
qsort | 排序类型未指定的元素的范围 (函数) |
bsearch | 在未指定类型的数组中搜索元素 (函数) |