【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;
}
作者:Eriktse原文地址:https://segmentfault.com/a/1190000043855842

%s 个评论

要回复文章请先登录注册