在算法比赛中，有两种排序较为常见，第一种是$O(nlogn)$的排序，个别是基于比拟的排序，第二种是桶排序。两种办法各有优劣，选取适合的排序办法对于解题十分重要。
本文次要解说这两种排序办法，不要只会写冒泡排序了！
作者：Eriktse
简介：19岁，211计算机在读，CCPC全国赛金牌，ICPC区域赛银牌服役选手力争以通俗易懂的形式解说编程和算法！❤️欢送关注我，一起交换C++/Python算法。（优质好文继续更新中……）
欢送加群一起游玩~QQ群：600240150
基于比拟的排序
这里不解说疾速排序的外部原理，咱们只须要晓得在什么场合应用即可。
在C++中，个别不须要本人写疾速排序，用STL中的sort()函数即可（具体的实现办法不肯定是疾速排序），即工夫复杂度为$O(nlogn)$的排序办法。
应用sort()函数前须要引入头文件#include <algorithm>。在vector中，应用sort(v.begin(), v.end())进行排序，在C数组中用sort(a, a + n)进行排序。
个别在数据范畴$1 times 10 ^ 6$以内能够用疾速排序，且元素的大小个别很大。
桶排序
当元素的大小比拟小的时候，能够采纳桶排序，其工夫复杂度为$O(n)$，是一个线性复杂度。
它利用的是值域小的个性，开一个数组记录数字呈现的次数，而后下标主动就排序了。
在某些状况下，用桶的思维能够优化复杂度。
例题
luogu P1177 【模板】排序
链接：https://www.luogu.com.cn/problem/P1177
本题数据范畴反对应用基于比拟的排序，所以间接是应用即可。
<bits/stdc++.h>头文件蕴含了<algorithm>。
代码：
#include <bits/stdc++.h>using namespace std;signed main(){ ios::sync_with_stdio(0); int n;cin >> n; vector<int> a(n); for(int i = 0;i < n; ++ i)cin >> a[i]; sort(a.begin(), a.end()); //留神上面这句，前面这部分意思是 //当i的迭代器和a.back()迭代器雷同时就换行 for(auto &i : a)cout << i << " n"[&i == &a.back()]; return 0;}luogu P1271 【深基9.例1】选举学生会
链接：https://www.luogu.com.cn/problem/P1271
本题须要采纳桶排序，因为基于比拟的排序办法最小复杂度为$O(nlogn)$，可能无奈满足本题需要。
代码：
#include <bits/stdc++.h>using namespace std;const int N = 2e6 + 9;int a[N];//a[i]示意数字i呈现的次数signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m;cin >> n >> m; for(int i = 1;i <= m; ++ i) { int x;cin >> x; a[x] ++; } for(int i = 0;i <= n; ++ i) { for(int j = 1;j <= a[i]; ++ j) { cout << i << ' '; } } return 0;}