2024.03.03蓝桥云课笔记——排序

sort简介

1. #include<algorithm>

2. 使用的是快速排序

3. 时间复杂度为O(nlogn)

sort使用(默认是从小到大)

1.sort(起始地址，结束地址的下一位，*比较函数）；

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{int a[1000];int n;cin>>n;for(int i=1;i<=n;++i)cin>>a[i];sort(a+1,a+n+1);for(int i=1;i<=n;++i)cout<<a[i]<<'\n';return 0;
}

2.sort(起始地址(对迭代器而言begin())，结束地址的下一位，*比较函数)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{vector<int>v={5,3,1,7,2};sort(v.begin(),v.end());for(int i=0;i<v.size();i++){cout<<v[i]<<" ";}return 0;
}

自定义比较函数

sort函数的第三个参数，可以是函数，也可以是lambda表达式

#include<bits/stdc++.h>
using namespace std;
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={4,2,7,120,35};sort(v.begin(),v.end(),cmp);//lambda表达式//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]<<" ";}return 0;
}

例题：1.排序 - 蓝桥云课 (lanqiao.cn)

题解1：

#include <bits/stdc++.h>
using namespace std;
​
const int N = 5e5 +3;
int a[N];
​
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}
​sort(a+1,a+1+n);for(int i=1;i<=n;i++){cout<<a[i]<<" ";}cout<<'\n';
​for(int i=n;i>=1;i--){cout<<a[i]<<" ";}return 0;
}

题解2：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+3;
int a[N];
​
int main()
{int n;cin>>n;
​for(int i=1;i<=n;i++){cin>>a[i];}
​sort(a+1,a+1+n);
​for(int i=1;i<=n;i++){cout<<a[i]<<" ";}cout<<'\n';
​sort(a+1,a+1+n,[](const int &u,const int &v){return u>v;});
​for(int i=1;i<=n;i++){cout<<a[i]<<" ";}return 0;
}