【C++修行之道】竞赛常用库函数（sort，min和max函数，min_element和max_element、nth_element）

2024-01-22 19:52
文章标签 c++ 函数 常用 竞赛 之道 库函数 element min sort 修行 max nth

本文主要是介绍【C++修行之道】竞赛常用库函数（sort，min和max函数，min_element和max_element、nth_element），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、sort

1.1sort简介

语法

参数

功能

适用容器

1.2sort的用法

1.3自定义比较函数 

示例

1265蓝桥题 —— 排序

二、min和max函数

三、min_element和max_element

 497蓝桥题 —— 成绩分析

四、nth_element

一、sort

1.1sort简介

  • sort函数包含在头文件<algorithm>中。
  • 在使用前需要#include <algorithm>或使用万能头文件。
  • sort是C++标准库中的一个函数模板，用于对指定范围内的元素进行排序。
  • sort算法使用的是快速排序 (QuickSort) 或者类似快速排序的改进算法，具有较好的平均时间复杂度，一般为O(nlogn)

语法

Sort(start,end,cmp)

参数

（1）start表示要排序数组的起始地址；

（2）end表示数组结束地址的下一位；

（3）cmp用于规定排序的方法，可不填，默认升序。

功能

sort函数用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。

一般是直接对数组进行排序，例如对数组a[10]排序，sort（a,a+10）。而sort函数的强大之处在可与cmp函数结合使用，即自定义排序：如果你想按照特定的顺序排序，可以传递一个自定义的比较函数或lambda表达式给sort()。这个函数应该接受两个参数，并返回一个布尔值，指示第一个参数是否应该在排序后位于第二个参数之前。

相对于普通的排序算法，sort（）函数在快速排序（详见C++快速排序）的基础上，又进行了优化，时间复杂度为n*log2(n)，执行效率较高。

适用容器

sort()函数适用于数组和提供了随机访问迭代器的大多数STL容器，如vector、deque等。对于不支持随机访问迭代器的容器（如list、forward_list），应使用list容器自己的sort()成员函数。

int main()
{//sort(起始地址,   结束地址的下一位, *比较函数);//   迭代器begin()  end()         默认用小于号<int a[1000];int n;//读取数组大小cin >> n;//读取数组元素for (int i = 1; i <= n; ++i)cin >> a[i];//对数组进行排序sort(a + 1, a + n + 1);//    a[1]    a[n+1]  [1,n+1) 左闭右开//输出for (int i = 1; i <= n; ++i)cout << a[i] << ' ';
}

1.2sort的用法

std::sort(begin, end);

begin和end是输入序列的起始迭代器和结束迭代器。需要注意的是，end迭代器指向的是序列尾部的"过去位置"，即最后一个有效元素之后的位置。

int main()
{//初始化vvector<int>v = { 5,1,3,9,11 };//        begin  v[0]    v[4]  end()//对数组进行排序sort(v.begin(), v.end());//输出//for (int i = 0; i < v.size(); ++i)cout << v[i] << ' ';for (auto& i : v)cout << i << ' ';return 0;
}

1.3自定义比较函数 

使用sort()我们不仅仅可以从大到小排或者从小到大排，还可以按照一定的准则进行排序。比如说我们按照每个数的个位进行从大到小排序，我们就可以根据自己的需求来写一个函数作为排序的准则传入到sort()中。

//sort默认使用小于号进行排序,如果想要自定义比较规则,
//可以传入第三个参数,可以是函数或lambda表达式(匿名函数)
bool cmp(const int& u, const int& v)
{return u > v;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//初始化vector<int> v = { 5,1,3,9,11 };//对数组进行排序,降序排序sort(v.begin(), v.end(),cmp);//输出/*for (int i = 0; i < v.size(); ++i)cout << v[i] << ' ';*/for (auto& i : v)//就是v中的数据{cout << i << ' ' ;}
}

 sort默认使用小于号进行排序，如果想要自定义比较规则
可以传入第三个参数，可以是函数或lambda表达式（匿名函数）。

int main()
{//初始化vvector<int>v = { 5,1,3,9,11 };//对数组进行排序,降序排序sort(v.begin(), v.end(), [](const int& u, const int& v){return u > v;});//输出//for (int i = 0; i < v.size(); ++i)cout << v[i] << ' ';for (auto& i : v)//就是v中的数据{cout << i << ' ' ;}return 0;
}

结构体可以将小于号重载后进行排序，当然，用前面的方法也是可行的 

struct Node
{int u, v;bool operator<(const Node& m)const//重载的operator<是一个成员函数，//它接受一个const Node&类型的参数（即对另一个Node对象的常量引用），//并返回一个bool类型的结果。{//以u为第一关键字,v为第二关键字排序return u == m.u ? v < m.v : u < m.u;}
};#include <iostream>
using namespace std;
int main()
{int n; cin >> n;return 0;
}

示例

#include<iostream>  
#include<string>  
#include<algorithm>  
using namespace std;  struct Student{  string name;  // 学生姓名  double score[4];  // 学生四门课的成绩  
};  // 比较函数，用于sort排序，按照平均成绩从高到低排序  
bool cmp_score(const Student &x, const Student &y){  double average_x = 0.0, average_y = 0.0;  for(int i = 0; i < 4; i++){  average_x += x.score[i];  average_y += y.score[i];  }  average_x /= 4;  average_y /= 4;  return average_x > average_y;  
}  int main(){  Student stu[3];  // 存储三个学生的信息  // 输入三个学生的姓名和四门课的成绩  for(int i = 0; i < 3; i++){  cin >> stu[i].name;  for(int j = 0; j < 4; j++){  cin >> stu[i].score[j];  }  }  // 使用sort函数，按照平均成绩从高到低排序  sort(stu, stu + 3, cmp_score);  // 输出排序后的学生信息  for(int i = 0; i < 3; i++){  cout << stu[i].name << " ";  for(int j = 0; j < 4; j++){  cout << stu[i].score[j] << " ";  }  cout << endl;  // 换行  }  return 0;  
}

1265蓝桥题 —— 排序

#include <bits/stdc++.h> // 包含了C++标准库中的大部分头文件  using namespace std; // 使用标准命名空间std  const int N = 5e5 + 3; // 定义一个常量N，其值为500003，作为数组a的最大可能大小  
int a[N]; // 定义一个全局数组a，大小为N  int main() 
{  int n; cin >> n; // 输入一个整数n，表示数组a中实际元素的数量  for (int i = 1; i <= n; ++i) cin >> a[i]; // 从a[1]开始（而不是通常的a[0]），输入n个整数到数组a中  sort(a + 1, a + 1 + n); // 对数组a中从a[1]到a[n]的元素进行排序  // 以升序打印数组a中的元素  for (int i = 1; i <= n; ++i)  cout << a[i] << " \n"[i == n]; // 打印每个元素和一个空格，如果i等于n（即最后一个元素），则打印换行符  // 这里使用了字符串字面量" \n"的数组索引技巧：// 当i==n时，[i==n]求值为[1]，选择'\n'；否则为[0]，选择' '  // 以降序打印数组a中的元素  for (int i = n; i >= 1; --i)  cout << a[i] << " \n"[i == 1];// 类似地，打印每个元素和一个空格，如果i等于1（即最后一个要打印的元素），则打印换行符  return 0; 
}

二、min和max函数

  • min和max函数
  • min(a，b)返回a和b中较小的那个值，只能传入两个值，或传入一个列表
  • 例如:
  • min(3, 5) = 3
  • min({1, 2, 3,4)) = 1
  • max(a，b)返回a和b中较大的那个值，只能传入两个值，或传入一个列表
  • 例如:
  • max(7，5)= 7
  • max([1, 2，3,4) = 4
  • 时间复杂度为O(1)，传入参数为数组时时间复杂度为O(n)，n为数组大小。
  • min，max函数是在取最值操作时最常用的操作。

三、min_element和max_element

min_element 和 max_element

头文件：#include<algorithm>

作用：返回容器中最小值和最大值的指针。max_element(first,end,cmp);其中cmp为可选择参数!

  • min_element(st,ed)返回地址[st,ed)中最小的那个值的下标(选代器)，传入参数为两个地址或迭代器。
  • max_element(st,ed)返回地址[st,ed)中最大的那个值的下标 (选代器)，传入参数为两个地址或迭代器。
  • 时间复杂度均为O(n)，n为数组大小(由传入的参数决定)。
int main()
{//初始化vector<int>v = { 5,1,3,9,11 };//			   [			)//输出最大的元素，*表示解引用，即通过地址（迭代器）得到值cout << *max_element(v.begin(), v.end()) << '\n';}

 497蓝桥题 —— 成绩分析



用户登录

#include <bits/stdc++.h> 
using namespace std;      const int N = 1e4 + 9;    
int a[N];                 int main() // 主函数  
{  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出流  int n; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; int mx = a[1], mi = a[1]; // 初始化最大值mx和最小值mi为数组的第一个元素a[1]  for (int i = 1; i <= n; ++i) // 遍历数组a中的所有元素  {  mx = max(mx, a[i]); // 更新最大值mx  mi = min(mi, a[i]); // 更新最小值mi  }  cout << mx << '\n' << mi << '\n'; // 输出最大值和最小值，每个值后面跟一个换行符  long long sum = 0; // 定义一个长整型变量sum，用于存储数组a中所有元素的总和  for (int i = 1; i <= n; ++i) sum += a[i]; // 遍历数组a，计算所有元素的总和  cout << fixed << setprecision(2) << 1.0 * sum / n << '\n'; // 输出平均值，保留两位小数  // 注意：这里使用1.0 * sum将sum转换为浮点数，以确保进行浮点数除法  return 0; // 程序执行成功，返回0  
}

四、nth_element

  • nth_element()进行部分排序，返回值为void()
  • 传入参数为三个地址或迭代器。其中第二个参数位置的元素将处于正确位置，其他位置元素的顺序可能是任意的，但前面的都比它小，后面的都比它大
  • nth_element()是c++的STL库中的函数，作用是将数组中第k小的整数放在区间第k个位置
  • 比如vector<int> nums = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
  • nth_element 会重新排列序列，使得第5小的元素位于正确的位置（索引为4的位置），且该元素之前的所有元素都不大于它，之后的元素都不小于它。
  • 使用一次nth_element()的时间复杂度为O ( n )。

int main()
{// 初始化一个包含7个整数的vector  vector<int> v = { 5,1,7,3,10,18,9 };// 使用nth_element进行部分排序  // 将v中的元素重新排列，使得v[3]位置上的元素位于排序后应在的位置  // v[0]到v[2]的元素都不大于v[3]，v[4]到v[6]的元素都不小于v[3]  nth_element(v.begin(), v.begin() + 3, v.end());// 输出vector中的元素  for (auto& i : v)cout << i << ' '; // 注意：这里应该使用' '空格而不是'\n'换行符  return 0;
}

今天就先到这了！！！

看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！

你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。

这篇关于【C++修行之道】竞赛常用库函数（sort，min和max函数，min_element和max_element、nth_element）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/634072。

相关文章

C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
shell编程之函数与数组的使用详解

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》：本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的
阅读更多...
springboot项目中常用的工具类和api详解

springboot项目中常用的工具类和api详解

《springboot项目中常用的工具类和api详解》在SpringBoot项目中,开发者通常会依赖一些工具类和API来简化开发、提高效率,以下是一些常用的工具类及其典型应用场景,涵盖Spring原生... 目录1. Spring Framework 自带工具类(1) StringUtils(2) Coll
阅读更多...
MySQL高级查询之JOIN、子查询、窗口函数实际案例

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》：本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN（连接查询）1.1 内连接（INNER JOIN）1.2 左连接（LEFT JOI
阅读更多...
C++ vector的常见用法超详细讲解

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》：本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve
阅读更多...
MySQL中FIND_IN_SET函数与INSTR函数用法解析

MySQL中FIND_IN_SET函数与INSTR函数用法解析

《MySQL中FIND_IN_SET函数与INSTR函数用法解析》：本文主要介绍MySQL中FIND_IN_SET函数与INSTR函数用法解析,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一... 目录一、功能定义与语法1、FIND_IN_SET函数2、INSTR函数二、本质区别对比三、实际场景案例分
阅读更多...
如何高效移除C++关联容器中的元素

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...
Python获取C++中返回的char*字段的两种思路

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串，目前我找到两种解决问题的思路，具体实现如下：
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2