【C++算法基础】#1基于比较的排序与桶排序 – 不要只会写冒泡了！

在算法竞赛中，有两种排序较为常见，第一种是的排序，一般是基于比较的排序，第二种是桶排序。两种方法各有优劣，选取合适的排序方法对于解题非常重要。

本文主要讲解这两种排序方法，不要只会写冒泡排序了！

🎈 作者：Eriktse
 🎈 简介：19岁，211计算机在读，CCPC全国赛金牌，ICPC区域赛银牌退役选手🏆力争以通俗易懂的方式讲解编程和算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
 🎈欢迎加群一起玩耍~QQ群：600240150

基于比较的排序

这里不讲解快速排序的内部原理，我们只需要知道在什么场合使用即可。

在C++中，一般不需要自己写快速排序，用STL中的sort()函数即可（具体的实现方法不一定是快速排序），即时间复杂度为的排序方法。

使用sort()函数前需要引入头文件#include <algorithm>。

在vector中，使用sort(v.begin(), v.end())进行排序，在C数组中用sort(a, a + n)进行排序。

一般在数据范围以内可以用快速排序，且元素的大小一般很大。

桶排序

当元素的大小比较小的时候，可以采用桶排序，其时间复杂度为，是一个线性复杂度。

它利用的是值域小的特性，开一个数组记录数字出现的次数，然后下标自动就排序了。

在某些情况下，用桶的思想可以优化复杂度。

例题

luogu P1177 【模板】排序

链接：https://www.luogu.com.cn/problem/P1177

本题数据范围支持使用基于比较的排序，所以直接是使用即可。

<bits/stdc++.h>头文件包含了<algorithm>。

代码：

luogu P1271 【深基9.例1】选举学生会

链接：https://www.luogu.com.cn/problem/P1271

本题需要采用桶排序，因为基于比较的排序方法最小复杂度为，可能无法满足本题需求。

代码：