文章目录
一、什么是algorithm
二、常用函数一览
6.sort()
（1）使用sort函数
（2）实现cmp函数
基本数据类型数组的排序
结构体数组的排序
容器的排序
7.lower_bound() 和 upper_bound()
一、什么是algorithm
在algorithm中，有很多函数，这些函数是已经写好的，可以直接调用，十分的方便，可以精简代码量辅助我们思考
在使用algorithm的函数之前需要添加头文件#include <algorithm>
由于algorithm下的函数有很多，这里分为两篇博客去介绍，第一篇博客见：STL—algorithm（1）
二、常用函数一览
6.sort()
顾名思义，sort函数就是用来排序的函数，根据不同的情况可以有不同的排序方法
（1）使用sort函数
sort(首元素地址[必填], 尾元素地址的下一个地址[必填], 比较函数[选填]);
可以看到，sort函数一共有三个参数，前两个是必填的，而比较函数可以根据自己的需求选填，当我们不填写比较函数的时候，则默认单调递增的排序方式
#include <iostream> #include <algorithm> using namespace std; int main() { int a[5] = {8, 4, 6, 12, 1}; sort(a, a + 5); for (int i = 0; i < 5; i ++ ) cout << a[i] << ' '; return 0; }
输出结果为：1 4 6 8 12
如果是char类型的数据，我们在不写比较函数的时候默认字典序从小到大排序
#include <iostream> #include <algorithm> using namespace std; int main() { char a[5] = {'j', 'a', 'b', 'y', 'z'}; sort(a, a + 5); for (int i = 0; i < 5; i ++ ) cout << a[i] << ' '; return 0; }
输出结果为：a b j y z
（2）实现cmp函数
基本数据类型数组的排序
我们刚刚介绍了，如果什么都不填写的话，默认是从小到大进行排序，下面介绍如何实现从大到小排序
bool cmp(int a, int b) { return a > b; }
同样，如果是double或是char类型的数据，cmp函数就是：
bool cmp(double a, double b) { return a > b; }
bool cmp(char a, char b) { return a > b; }
下面给出样例和输出结果：
int类型
#include <iostream> #include <algorithm> using namespace std; bool cmp (int a, int b) { return a > b; } int main() { int a[5] = {7, 3, 1, 8, 6}; sort(a, a + 5, cmp); for (int i = 0; i < 5; i ++ ) cout << a[i] << ' '; return 0; }
输出结果为：8 7 6 3 1
double类型
#include <iostream> #include <algorithm> using namespace std; bool cmp (double a, double b) { return a > b; } int main() { double a[5] = {7.3, -3.1, 1, 8.7, 6.2}; sort(a, a + 5, cmp); for (int i = 0; i < 5; i ++ ) cout << a[i] << ' '; return 0; }
输出结果为：8.7 7.3 6.2 1 -3.1
char类型
#include <iostream> #include <algorithm> using namespace std; bool cmp (char a, char b) { return a > b; } int main() { char a[5] = {'j', 'a', 'b', 'y', 'z'}; sort(a, a + 5, cmp); for (int i = 0; i < 5; i ++ ) cout << a[i] << ' '; return 0; }
输出结果为：z y j b a
结构体数组的排序
如下定义结构体：
struct node { int x, y; }s[10];
如果想将x数组按照x从大到小进行排序，那么可以写成：
struct node { int x, y; bool operator < (const node w) const { return x > w.x; } }s[10];
示例如下：
#include <iostream> #include <algorithm> using namespace std; struct node { int x, y; bool operator < (const node w) const { return x > w.x; } }s[10]; int main() { s[0] = {2, 2}; s[1] = {1, 3}; s[2] = {3, 1}; sort(s, s + 3); for (int i = 0; i < 3; i ++ ) cout << s[i].x << ' ' << s[i].y << endl; return 0; }
输出结果为
3 1
2 2
1 3
如果想要先按x从大到小排序，但当x相等的情况下按照y的大小从小到大来排序，那么cmp的写法是：
struct node { int x, y; bool operator < (const node w) const { if (x != w.x) return x > w.x; else return y < w.y; } }s[10];
示例如下：
#include <iostream> #include <algorithm> using namespace std; struct node { int x, y; bool operator < (const node w) const { if (x != w.x) return x > w.x; else return y < w.y; } }s[10]; int main() { s[0] = {2, 2}; s[1] = {1, 3}; s[2] = {2, 1}; sort(s, s + 3); for (int i = 0; i < 3; i ++ ) cout << s[i].x << ' ' << s[i].y << endl; return 0; }
输出结果为
2 1
2 2
1 3
