零、前言

就这篇啊，现在是 2022/1/6 00:54，我在写这句话。

本来说函数篇应该去年就写完了，但是我老鸽子了，到今年才开始写。

参考资料：

1. cppreference
2. 百度百科
3. 必应词典

在这里表示感谢。

行吧，正片开始。

一、sort 和 stable_sort

所在头文件：<algorithm>。

1. 是什么

看这个名字就知道是干什么用的。

sort
US：[sɔrt]；UK：[sɔː(r)t]
n. 排序；分类；种类；类别
v. 整理；把……分类；妥善处理；安排妥当

排序昂，排序。

关于这个东西的原理，好家伙我也不知道，笑死根本看不懂，感兴趣的直接搜吧。

sort 和 stable_sort 的区别在于，stable_sort 可以保证相等元素的相对位置不变。

2. 为什么

废话文学奖，因为可以排序，只要一行。

方便也快，时间复杂度如下：

Complexity

\(O(N\cdot\log(N))\), where N = std::distance(first, last) comparisons on average. (until C++11)
\(O(N\cdot\log(N))\), where N = std::distance(first, last) comparisons. (since C++11)

来自 cppreference - std::sort。

注意这个“since C++11”，根据 CCF - 关于NOI系列活动中编程语言使用限制的补充说明 第一条：

除题面有明确要求外，C++程序编译默认采用的语言标准为C++14

所以在 NOI 系列比赛中，时间复杂度 \(O(n\log n)\)，大家放心使用。

3. 怎么做

这个东西要怎么用呢。

sort(begin, end, compare)

stable_sort(begin, end, compare)

用于一个连续的区间，从 begin 这个地址开始，到 end 这个地址结束。排序方法为 compare。

compare 这个东西同 priority_queue，这里就不多说了。

或者重载运算符 <，也在 priority_queue。

对于 C++ 本身有的，或者重载运算符 < 的数据类型，compare 可以不写。

主要是这个 begin 和 end，是左闭右开的，这个需要注意。

二、lower_bound 和 upper_bound

所在头文件：<algorithm>。

1. 是什么

这两个东西要一起说。

lower_bound 和 upper_bound 是二分查找，可以在 \(O(n\log n)\) 的时间内查找一个元素。

lower_bound 找大于等于。

upper_bound 找大于。

就是二分查找。

2. 为什么

因为懒，好写，所以用。

3. 怎么做

咋用？

lower_bound(begin, end, value, compare)

upper_bound(begin, end, value, compare)

同 sort - 怎么做，value 是判断相不相等。

对于 C++ 本身有的，或者重载运算符 < 的数据类型，compare 可以不写。

找到了，返回那个数的地址。

没找到，返回 end。

左闭右开。

三、max 和 min

所在头文件：<algorithm>。

1. 是什么

如其名。

maximum
US：[ˈmæksɪməm]；UK：['mæksɪməm]
n. 最大限度；最大量；最高限度
adj. 最高的；最多的；最大极限的

minimum
US：[ˈmɪnɪməm]；UK：['mɪnɪməm]
n. 最低限度；最小值；最少量；极小量
adj. 最低的；最小的；最低限度的

2. 为什么

同前。

3. 怎么做

max(A, B, compare)

min(A, B, compare)

对于 C++ 本身有的，或者重载运算符 < 的数据类型，compare 可以不写当且仅当A 和 B 的数据类型相同。

返回当中满足最大 / 最小的那一个。

四、swap

所在头文件：<algorithm>。

1. 是什么

swap
US：[swɑp]；UK：[swɒp]
v. 换；掉换；交换；替换
n. 〈非正式〉交换；〈非正式〉交换物；【商】互换信贷

交换。

2. 为什么

主要是因为这个东西可以适用于任何类型。

3. 怎么做

swap(A, B)

注意传入的是两个变量，使用引用。

template< class T >
void swap( T& a, T& b );

(until C++11)

这是 cppreference - swap 上，“until C++11” swap 的声明，后面的也差不多，很明显地看到有 & 引用符号，所以我们只能传入变量而不是变量的地址。

五、nth_element

所在头文件：<algorithm>。

1. 是什么

可以看到 洛谷 - P1923 【深基9.例4】求第 k 小的数 里面有这样一句话：

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

很明显地，我们就可以知道，nth_element 用来求第 \(k\) 小的数。

2. 为什么

我们平时所写的分治算法求第 \(k\) 小的数，时间复杂度是平均 \(O(n)\) 的，但是并没有达到 \(O(n)\)。

而 nth_element 达到了 \(O(n)\) 效率更高了。

3. 怎么做

nth_element(begin, nth, end, compare)

注意一下，这里都是地址，左闭右开。

nth_element 会使得 nth 上的元素为应该在的 nth 上的元素，但是除了那个数，其他数的顺序会乱。

对于 C++ 本身有的，或者重载运算符 < 的数据类型，compare 可以不写。

六、find

所在头文件：<algorithm>。

不想写了。

七、fill

不想写了。

八、is_permutation、next_permutation 和 prev_permutation

真不想写了。

九、is_heap、make_heap、push_heap 和 pop_heap

真的不想写了。

十、random_shuffle

我是真的不想写了。