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

C++使用 sort 实现自定义排序

1.sort 的基本用法

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

对一个数组进行排序

#include<iostream>
#include<algorithm> //使用sort库函数需要引入头文件algorithm

using namespace std; 

const int N = 100010;
int arr[N]; //定义全局变量数组arr

int 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

样例测试

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

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

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

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main()
{
    vector<int> arr = {5, 1, 3, 8, 2}; //直接将数据初始化传入arr
    
    sort(arr.begin(), arr.end(), [](const int &u, const int &v)
    {
        return u > v;
    }); //使用lambda表达式实现自定义排序
    
    for(auto i : arr)
        cout << i << " ";//迭代打印
        
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.结构体重载进行比较

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

struct Node
{
    int u, v;
    bool operator < (const Node & m)const
    {
        //以u为第一关键字，v为第二关键字排序
        return u == m.u ? v < m.v : u < m.u;
    }
}
1
2
3
4
5
6
7
8
9

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

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