关于c++:C算法基础1基于比较的排序与桶排序-不要只会写冒泡了

在算法比赛中，有两种排序较为常见，第一种是 $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;
}