概述
算法库提供大量用途的函数（例如查找、排序、计数、操作），它们在元素范围上操作。注意范围定义为 [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 | 在未指定类型的数组中搜索元素 (函数) |