sort实现自定义排序方法详解

使用 sort 实现自定义排序

1.sort 的基本用法

sort 库函数需要引入头文件algorithm,是一种排序算法，使用的排序逻辑可以看成是效率很高的快速排序或其的改进版本。平均时间复杂度为 $nlogn$ 。下面介绍 sort 的基本用法。

对一个数组进行排序

#include<iostream>
#include<algorithm> //使用sort库函数需要引入头文件algorithmusing namespace std; const int N = 100010;
int arr[N]; //定义全局变量数组arrint main()
{int n; //n代表数组长度cin >> n; for(int i = 1; i <= n; i ++)cin >> arr[i]; //输入n个数sort(arr + 1, arr + n + 1);//sort(初位置，末位置的下一位) 由于我们读入时是从arr[1]开始储存的，所以初位置是arr + 1//待排序的区间为左闭右开区间，[i, j）for(int i = 1; i <= n; i ++)cout << arr[i] << " ";//打印排序后数组return 0;
}

样例测试

对容器进行排序，迭代器排序

#include<algorithm>
#include<iostream>
#include <vector>using namespace std;vector<int> arr; //使用vector<int>容器int main()
{int n;cin >> n;//arr的长度for(int i = 1; i <= n; i ++){int x;cin >> x;arr.push_back(x);//将x插入arr容器末尾}sort(arr.begin(), arr.end());//使用迭代器进行排序for(auto i : arr)//迭代遍历cout << i << " ";return 0;
}

2.sort 实现自定义排序

sort 默认使用小于号 < 进行排序，一般进行的都是升序排序，通过自定义比较规则，可以传入第三个参数，可以是函数或 lambda 表达式。
使用函数实现自定义排序

#include<iostream>
#include<algorithm>using namespace std;const int N = 100010;
int arr[N];//待排序数组bool cmp(const int &u, const int &v)//自定义排序函数
{return u > v;
}int main()
{int n;cin >> n;//数组长度for(int i = 1; i <= n; i ++)cin >> arr[i];//输入数组中的数sort(arr + 1, arr + n + 1, cmp);//引入了第三个参数，只写函数名for(int i = 1; i <= n; i ++)cout << arr[i] << " ";//打印输出return 0;
}

这里将升序排序通过自定义函数改成了降序排序

使用lambda表达式实现自定义排序

#include<iostream>
#include<algorithm>
#include<vector>using namespace std;int main()
{vector<int> arr = {5, 1, 3, 8, 2}; //直接将数据初始化传入arrsort(arr.begin(), arr.end(), [](const int &u, const int &v){return u > v;}); //使用lambda表达式实现自定义排序for(auto i : arr)cout << i << " ";//迭代打印return 0;
}

3.结构体重载进行比较

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

struct Node
{int u, v;bool operator < (const Node & m)const{//以u为第一关键字，v为第二关键字排序return u == m.u ? v < m.v : u < m.u;}
}

重载完成的结构体在使用sort时可以直接使用，会默认按重载的小于号逻辑进行排序。

这就是全部的内容了，喜欢可以点个赞，寒假会持续更新。