在算法競(jìng)賽中，有兩種排序較為常見，第一種是的排序，一般是基于比較的排序，第二種是桶排序。兩種方法各有優(yōu)劣，選取合適的排序方法對(duì)于解題非常重要。

本文主要講解這兩種排序方法，不要只會(huì)寫冒泡排序了！

?? 作者：Eriktse
??? 簡(jiǎn)介：19歲，211計(jì)算機(jī)在讀，CCPC全國(guó)賽金牌，ICPC區(qū)域賽銀牌退役選手??力爭(zhēng)以通俗易懂的方式講解編程和算法！??歡迎關(guān)注我，一起交流C++/Python算法。（優(yōu)質(zhì)好文持續(xù)更新中……）??
???歡迎加群一起玩耍~QQ群：600240150

基于比較的排序

這里不講解快速排序的內(nèi)部原理，我們只需要知道在什么場(chǎng)合使用即可。

在C++中，一般不需要自己寫快速排序，用STL中的sort()函數(shù)即可（具體的實(shí)現(xiàn)方法不一定是快速排序），即時(shí)間復(fù)雜度為的排序方法。

使用sort()函數(shù)前需要引入頭文件#include <algorithm>。

在vector中，使用sort(v.begin(), v.end())進(jìn)行排序，在C數(shù)組中用sort(a, a + n)進(jìn)行排序。

一般在數(shù)據(jù)范圍以內(nèi)可以用快速排序，且元素的大小一般很大。

桶排序

當(dāng)元素的大小比較小的時(shí)候，可以采用桶排序，其時(shí)間復(fù)雜度為，是一個(gè)線性復(fù)雜度。

它利用的是值域小的特性，開一個(gè)數(shù)組記錄數(shù)字出現(xiàn)的次數(shù)，然后下標(biāo)自動(dòng)就排序了。

在某些情況下，用桶的思想可以優(yōu)化復(fù)雜度。

例題

luogu P1177 【模板】排序

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

本題數(shù)據(jù)范圍支持使用基于比較的排序，所以直接是使用即可。

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

代碼：

luogu P1271 【深基9.例1】選舉學(xué)生會(huì)

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

本題需要采用桶排序，因?yàn)榛诒容^的排序方法最小復(fù)雜度為，可能無(wú)法滿足本題需求。

代碼：