程序員的核心技能之一就是算法，談到算法，似乎都是從排序開(kāi)始。對(duì)一組已知范圍的數(shù)據(jù)進(jìn)行排序，最快的算法是什么呢？快速排序？希爾排序？非也，非也~是本文的主角“桶排序”！
來(lái)看一個(gè)實(shí)際例子吧：已知一組范圍在0~10的數(shù)據(jù)(如:9,5,2,7,7),你有沒(méi)有什么好方法編寫(xiě)一段程序，將數(shù)據(jù)從大到小輸出呢？
看到這樣的題目，相信很多人第一反應(yīng)跟我一樣，就是將這些數(shù)據(jù)進(jìn)行比較，然后進(jìn)行位置的交換，最終實(shí)現(xiàn)排序。可桶排序徹底顛覆了這種想法——第一次看到桶排序時(shí)，確實(shí)被驚艷到了——還有這種操作？！原來(lái)排序不一定非得老老實(shí)實(shí)對(duì)原有數(shù)據(jù)進(jìn)行位置調(diào)整！
好了，回到我們的題目。我們只需要借助一個(gè)一維數(shù)組就可以解決問(wèn)題。首先，我們申請(qǐng)一個(gè)長(zhǎng)度為11的數(shù)組int a[11],因?yàn)槲覀兊臄?shù)據(jù)范圍是0~10，而int a[11]的元素正好是a[0]~a[10]。開(kāi)始的時(shí)候，我們將所有元素都初始化為0，表示這些數(shù)都未出現(xiàn)過(guò)。例如a[0]等于0，就表示待排序數(shù)據(jù)還未出現(xiàn)過(guò)0；同理，若a[9]等于1，則表示待排數(shù)據(jù)中9出現(xiàn)過(guò)1次。
有了上面的說(shuō)明，那接下來(lái)就非常簡(jiǎn)單了，我們只需要遍歷待排數(shù)組，然后將每個(gè)數(shù)值對(duì)應(yīng)下標(biāo)的元素加1(比如第一個(gè)數(shù)是9，我們就將a[9]加1)。你會(huì)發(fā)現(xiàn)，待排數(shù)組遍歷完之后，a[0]~a[10]中的數(shù)值，其實(shí)就是0~10出現(xiàn)的次數(shù)，我們只需要按次數(shù)將下標(biāo)打印出來(lái)就實(shí)現(xiàn)排序了。代碼如下:
#include <stdio.h>
int main()
{
int a[11],i,j,t;
for(i=10; i>=0; i--)
{
a[i]=0;
}
for(i=1; i<=5; i++) //循環(huán)讀入5個(gè)待排數(shù)
{
scanf("%d",&t); //把每一個(gè)數(shù)讀到變量t中
a[t]++; //進(jìn)行計(jì)數(shù)
}
for(i=10; i>=0; i--)
{
for(j=1; j<=a[i];j++)
{
printf("%d ",i);
}
}
printf("\r\n");
getchar();
return 0;
}
執(zhí)行該程序，我們可以隨意輸入5個(gè)0~10的數(shù)字，然后程序會(huì)將其按從大到小排序輸出，如下圖：
接下來(lái)我們來(lái)看看時(shí)間復(fù)雜度。首先我們用了一個(gè)m次(m為桶的個(gè)數(shù))的循環(huán)把桶清空;然后再用一個(gè)n次(n為待排序數(shù)據(jù)的個(gè)數(shù))的循環(huán)，設(shè)置的數(shù)據(jù)的顯示次數(shù);最后又進(jìn)行了m+n次循環(huán)，把數(shù)據(jù)顯示出來(lái)。所以，整個(gè)排序算法一共執(zhí)行了m+n+m+n次。我們用大寫(xiě)字母O來(lái)表示時(shí)間復(fù)雜度，因此該算法的時(shí)間復(fù)雜度是O(m+n+m+n)即O(2*(m+n))。我們?cè)谡f(shuō)時(shí)間復(fù)雜度的時(shí)候可以忽略較小的常數(shù)，最終桶排序的時(shí)間復(fù)雜度為O(m+n)。還有一點(diǎn)，在表示時(shí)間復(fù)雜度的時(shí)候，n和m通常用大寫(xiě)字母即O(M+N),這是一個(gè)非?？斓呐判蛩惴?。
桶排序雖快，但其實(shí)它是用空間在換時(shí)間。如果需要排序的數(shù)范圍非常寬，那我們就需要申請(qǐng)非常多的“桶”來(lái)存儲(chǔ)每一個(gè)數(shù)出現(xiàn)的次數(shù)。即使依然只是需要對(duì)5個(gè)數(shù)進(jìn)行排序，這太浪費(fèi)空間了！所以在選擇使用哪種排序算法之前，還是需要根據(jù)實(shí)際情況，權(quán)衡好復(fù)雜度與空間的問(wèn)題。
參考書(shū)籍：《啊哈！算法》
說(shuō)明：本文所提到的是簡(jiǎn)化版的桶排序算法，真正的同排序算法要復(fù)雜些，有興趣的朋友可以自行搜索學(xué)習(xí)。
