#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) 返回 5
  • max(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 相同