程序員的核心技能之一就是算法，談到算法砾省，似乎都是從排序開始混槐。對(duì)一組已知范圍的數(shù)據(jù)進(jìn)行排序，最快的算法是什么呢声登？快速排序？希爾排序件舵？非也脯厨，非也~是本文的主角“桶排序”！
來看一個(gè)實(shí)際例子吧：已知一組范圍在0~10的數(shù)據(jù)(如:9,5,2,7,7),你有沒有什么好方法編寫一段程序俄认，將數(shù)據(jù)從大到小輸出呢？
看到這樣的題目，相信很多人第一反應(yīng)跟我一樣壳澳，就是將這些數(shù)據(jù)進(jìn)行比較，然后進(jìn)行位置的交換萎津，最終實(shí)現(xiàn)排序抹镊。可桶排序徹底顛覆了這種想法——第一次看到桶排序時(shí)垮耳，確實(shí)被驚艷到了——還有這種操作遂黍？俊嗽！原來排序不一定非得老老實(shí)實(shí)對(duì)原有數(shù)據(jù)進(jìn)行位置調(diào)整绍豁！
好了，回到我們的題目竹揍。我們只需要借助一個(gè)一維數(shù)組就可以解決問題。首先驶拱，我們申請(qǐng)一個(gè)長(zhǎng)度為11的數(shù)組int a[11],因?yàn)槲覀兊臄?shù)據(jù)范圍是0~10晶衷，而int a[11]的元素正好是a[0]~a[10]。開始的時(shí)候晌纫，我們將所有元素都初始化為0，表示這些數(shù)都未出現(xiàn)過箭养。例如a[0]等于0哥牍，就表示待排序數(shù)據(jù)還未出現(xiàn)過0；同理嗅辣，若a[9]等于1，則表示待排數(shù)據(jù)中9出現(xiàn)過1次澡谭。
有了上面的說明，那接下來就非常簡(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)打印出來就實(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ì)將其按從大到小排序輸出碎连，如下圖：
接下來我們來看看時(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ù)顯示出來恐似。所以，整個(gè)排序算法一共執(zhí)行了m+n+m+n次葛闷。我們用大寫字母O來表示時(shí)間復(fù)雜度双藕，因此該算法的時(shí)間復(fù)雜度是O(m+n+m+n)即O(2*(m+n))。我們?cè)谡f時(shí)間復(fù)雜度的時(shí)候可以忽略較小的常數(shù)蔓彩，最終桶排序的時(shí)間復(fù)雜度為O(m+n)。還有一點(diǎn)，在表示時(shí)間復(fù)雜度的時(shí)候顺又，n和m通常用大寫字母即O(M+N),這是一個(gè)非常快的排序算法蹂空。
桶排序雖快，但其實(shí)它是用空間在換時(shí)間上枕。如果需要排序的數(shù)范圍非常寬，那我們就需要申請(qǐng)非常多的“桶”來存儲(chǔ)每一個(gè)數(shù)出現(xiàn)的次數(shù)棋恼。即使依然只是需要對(duì)5個(gè)數(shù)進(jìn)行排序锈玉，這太浪費(fèi)空間了！所以在選擇使用哪種排序算法之前师崎，還是需要根據(jù)實(shí)際情況椅棺，權(quán)衡好復(fù)雜度與空間的問題。
參考書籍：《啊哈两疚！算法》
說明：本文所提到的是簡(jiǎn)化版的桶排序算法，真正的同排序算法要復(fù)雜些顷窒，有興趣的朋友可以自行搜索學(xué)習(xí)源哩。
