#cspjc3. STL 通用算法函数(algorithm)
STL 通用算法函数(algorithm)
STL 通用算法函数(algorithm)
1.sort( 快速排序)
应用场景:对数组或容器进行排序。
int a[5] = {3,1,4,2,5};
sort(a, a+5); // 升序
例:关于 sort,正确的有( )?{{ multiselect(1) }}
sort默认升序排序,平均复杂度 O(n log n)- 可以传入自定义比较函数实现降序
sort支持int数组,也支持vector等容器sort的底层是快速排序,最坏情况 O(n²)(但实际经过优化)- 使用
sort前需包含<algorithm>
2.swap(交换值)
应用场景:交换两个变量的值。
int a=3, b=5;
swap(a, b); // a=5, b=3
例:关于 swap,正确的有( )?{{ multiselect(2) }}
swap(a, b)可以交换两个同类型变量- 不能直接交换两个数组(如
swap(arr1, arr2)不合法) swap在<algorithm>中定义,也在<utility>中swap通过临时变量实现,效率 O(1)swap可用于交换两个string对象
3.max / min (最值)
应用场景:取两个数中的较大/较小值。
int m = max(3, 5); // m=5
例:关于 max 和 min,正确的有( )?{{ multiselect(3) }}
max(3, 5)返回5max(3, 5.0)会编译出错(类型不一致)min和max可以用于任意可比较类型- 它们定义在
<algorithm>中 - 若想比较多个值,可以使用
max({a,b,c})(C++11)
4.reverse (反转序列)
应用场景:将数组或容器元素顺序颠倒。
int a[5] = {1,2,3,4,5};
reverse(a, a+5); // 变为 5,4,3,2,
例:关于 reverse,正确的有( )?{{ multiselect(4) }}
reverse接受两个迭代器/指针,反转区间内元素reverse可以用于vector的迭代器- 反转后元素顺序完全颠倒
reverse的复杂度是 O(n)reverse在<algorithm>中
5.binary_search (二分查找是否存在)
binary: [ˈbaɪnəri] 由两部分组成的
应用场景:在有序序列中快速判断某元素是否存在。
if (binary_search(a, a+n, target)) // 存在则 true
例:关于 binary_search,正确的有( )?{{ multiselect(5) }}
- 要求序列已按升序排列
- 返回
bool类型,表示是否存在 - 若序列无序,结果未定义
- 时间复杂度 O(log n)
- 若想获取位置,应使用
lower_bound或upper_bound
6.lower_bound (第一个 >= 目标的位置)
bound:[baʊnd] 边界
应用场景:在有序数组中找第一个不小于目标值的元素位置。
int pos = lower_bound(a, a+n, 6) - a; // 返回下标
例:关于 lower_bound,正确的有( )?{{ multiselect(6) }}
- 在有序序列中查找第一个 >= value 的元素
- 返回的是迭代器(指针),减去首地址得到下标
- 如果所有元素都小于 value,返回
end(即a+n) - 底层二分,复杂度 O(log n)
- 与
upper_bound的区别在于upper_bound查找第一个 > value
7.upper_bound (第一个 > 目标的位置)
应用场景:求大于某值的范围。
int pos = upper_bound(a, a+n, 6) - a; // 第一个 >6 的位置
例:关于 upper_bound,正确的有( )?{{ multiselect(7) }}
- 查找第一个 > value 的元素
- 如果所有元素都不大于 value,返回
end - 常用于查找重复值的右边界
- 使用前需确保序列有序
- 返回类型与
lower_bound相同