第1節(jié)　最快最簡(jiǎn)單的排序——桶排序
　　在我們生活的這個(gè)世界中到處都是被排序過(guò)的東東。站隊(duì)的時(shí)候會(huì)按照身高排序，考試的名次需要按照分?jǐn)?shù)排序，網(wǎng)上購(gòu)物的時(shí)候會(huì)按照價(jià)格排序，電子郵箱中的郵件按照時(shí)間排序……總之很多東東都需要排序，可以說(shuō)排序是無(wú)處不在�，F(xiàn)在我們舉個(gè)具體的例子來(lái)介紹一下排序算法。
　　首先出場(chǎng)的是我們的主人公小哼，上面這個(gè)可愛(ài)的娃就是啦。期末考試完了老師要將同學(xué)們的分?jǐn)?shù)按照從高到低排序。小哼的班上只有5個(gè)同學(xué)，這5個(gè)同學(xué)分別考了5分、3分、5分、2分和8分，哎，考得真是慘不忍睹（滿分是10分）。接下來(lái)將分?jǐn)?shù)進(jìn)行從大到小排序，排序后是8 5 5 3 2。你有沒(méi)有什么好方法編寫一段程序，讓計(jì)算機(jī)隨機(jī)讀入5個(gè)數(shù)然后將這5個(gè)數(shù)從大到小輸出？請(qǐng)先想一想，至少想15分鐘再往下看吧（*^__^*）。
　　我們這里只需借助一個(gè)一維數(shù)組就可以解決這個(gè)問(wèn)題。請(qǐng)確定你真的仔細(xì)想過(guò)再往下看哦。
　　首先我們需要申請(qǐng)一個(gè)大小為11的數(shù)組int a[11]。OK，現(xiàn)在你已經(jīng)有了11個(gè)變量，編號(hào)從a[0]~a[10]。剛開(kāi)始的時(shí)候，我們將a[0]~a[10]都初始化為0，表示這些分?jǐn)?shù)還都沒(méi)有人得過(guò)。例如a[0]等于0就表示目前還沒(méi)有人得過(guò)0分，同理a[1]等于0就表示目前還沒(méi)有人得過(guò)1分……a[10]等于0就表示目前還沒(méi)有人得過(guò)10分。
　　下面開(kāi)始處理每一個(gè)人的分?jǐn)?shù)，第一個(gè)人的分?jǐn)?shù)是5分，我們就將相對(duì)應(yīng)的a[5]的值在原來(lái)的基礎(chǔ)增加1，即將a[5]的值從0改為1，表示5分出現(xiàn)過(guò)了一次。
　　第二個(gè)人的分?jǐn)?shù)是3分，我們就把相對(duì)應(yīng)的a[3]的值在原來(lái)的基礎(chǔ)上增加1，即將a[3]的值從0改為1，表示3分出現(xiàn)過(guò)了一次。
　　注意啦！第三個(gè)人的分?jǐn)?shù)也是5分，所以a[5]的值需要在此基礎(chǔ)上再增加1，即將a[5]的值從1改為2，表示5分出現(xiàn)過(guò)了兩次。
　　按照剛才的方法處理第四個(gè)和第五個(gè)人的分?jǐn)?shù)。最終結(jié)果就是下面這個(gè)圖啦。
　　你發(fā)現(xiàn)沒(méi)有，a[0]~a[10]中的數(shù)值其實(shí)就是0分到10分每個(gè)分?jǐn)?shù)出現(xiàn)的次數(shù)。接下來(lái)，我們只需要將出現(xiàn)過(guò)的分?jǐn)?shù)打印出來(lái)就可以了，出現(xiàn)幾次就打印幾次，具體如下。
　　a[0]為0，表示“0”沒(méi)有出現(xiàn)過(guò)，不打印。
　　a[1]為0，表示“1”沒(méi)有出現(xiàn)過(guò)，不打印。
　　a[2]為1，表示“2”出現(xiàn)過(guò)1次，打印2。
　　a[3]為1，表示“3”出現(xiàn)過(guò)1次，打印3。
　　a[4]為0，表示“4”沒(méi)有出現(xiàn)過(guò)，不打印。
　　a[5]為2，表示“5”出現(xiàn)過(guò)2次，打印5 5。
　　a[6]為0，表示“6”沒(méi)有出現(xiàn)過(guò)，不打印。
　　a[7]為0，表示“7”沒(méi)有出現(xiàn)過(guò)，不打印。
　　a[8]為1，表示“8”出現(xiàn)過(guò)1次，打印8。
　　a[9]為0，表示“9”沒(méi)有出現(xiàn)過(guò)，不打印。
　　a[10]為0，表示“10”沒(méi)有出現(xiàn)過(guò)，不打印。
　　最終屏幕輸出“2 3 5 5 8”，完整的代碼如下。
　　#include 
　　int main()
　　{
　　int a[11],i,j,t;
　　for(i=0;i<=10;i++)
　　a[i]=0; //初始化為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=0;i<=10;i++) //依次判斷a[0]~a[10]
　　for(j=1;j<=a[i];j++) //出現(xiàn)了幾次就打印幾次
　　printf("%d ",i);
　　getchar();getchar();
　　//這里的getchar();用來(lái)暫停程序，以便查看程序輸出的內(nèi)容
　　//也可以用system("pause");等來(lái)代替
　　return 0;
　　}
　　輸入數(shù)據(jù)為：
　　5 3 5 2 8
　　仔細(xì)觀察的同學(xué)會(huì)發(fā)現(xiàn)，剛才實(shí)現(xiàn)的是從小到大排序。但是我們要求是從大到小排序，這該怎么辦呢？還是先自己想一想再往下看哦。
　　其實(shí)很簡(jiǎn)單。只需要將for(i=0;i<=10;i++)改為for(i=10;i>=0;i--)就OK啦，快去試一試吧。
　　這種排序方法我們暫且叫它“桶排序”。因?yàn)槠鋵?shí)真正的桶排序要比這個(gè)復(fù)雜一些，以后再詳細(xì)討論，目前此算法已經(jīng)能夠滿足我們的需求了。
　　這個(gè)算法就好比有11個(gè)桶，編號(hào)從0~10。每出現(xiàn)一個(gè)數(shù)，就在對(duì)應(yīng)編號(hào)的桶中放一個(gè)小旗子，最后只要數(shù)數(shù)每個(gè)桶中有幾個(gè)小旗子就OK了。例如2號(hào)桶中有1個(gè)小旗子，表示2出現(xiàn)了一次；3號(hào)桶中有1個(gè)小旗子，表示3出現(xiàn)了一次；5號(hào)桶中有2個(gè)小旗子，表示5出現(xiàn)了兩次；8號(hào)桶中有1個(gè)小旗子，表示8出現(xiàn)了一次。
　　現(xiàn)在你可以嘗試一下輸入n個(gè)0~1000之間的整數(shù)，將它們從大到小排序。提醒一下，如果需要對(duì)數(shù)據(jù)范圍在0~1000的整數(shù)進(jìn)行排序，我們需要1001個(gè)桶，來(lái)表示0~1000之間每一個(gè)數(shù)出現(xiàn)的次數(shù)，這一點(diǎn)一定要注意。另外，此處的每一個(gè)桶的作用其實(shí)就是“標(biāo)記”每個(gè)數(shù)出現(xiàn)的次數(shù)，因此我喜歡將之前的數(shù)組a換個(gè)更貼切的名字book（book這個(gè)單詞有記錄、標(biāo)記的意思），代碼實(shí)現(xiàn)如下。
　　#include 
　　int main()
　　{
　　int book[1001],i,j,t,n;
　　for(i=0;i<=1000;i++)
　　book[i]=0;
　　scanf("%d",&n);//輸入一個(gè)數(shù)n，表示接下來(lái)有n個(gè)數(shù)
　　for(i=1;i<=n;i++)//循環(huán)讀入n個(gè)數(shù)，并進(jìn)行桶排序
　　{
　　scanf("%d",&t); //把每一個(gè)數(shù)讀到變量t中
　　book[t]++; //進(jìn)行計(jì)數(shù)，對(duì)編號(hào)為t的桶放一個(gè)小旗子
　　}
　　for(i=1000;i>=0;i--) //依次判斷編號(hào)1000~0的桶
　　for(j=1;j<=book[i];j++) //出現(xiàn)了幾次就將桶的編號(hào)打印幾次
　　printf("%d ",i);
　　getchar();getchar();
　　return 0;
　　}
　　可以輸入以下數(shù)據(jù)進(jìn)行驗(yàn)證。
　　10
　　8 100 50 22 15 6 1 1000 999 0
　　運(yùn)行結(jié)果是：
　　1000 999 100 50 22 15 8 6 1 0
　　最后來(lái)說(shuō)下時(shí)間復(fù)雜度的問(wèn)題。代碼中第6行的循環(huán)一共循環(huán)了m次（m為桶的個(gè)數(shù)），第9行的代碼循環(huán)了n次（n為待排序數(shù)的個(gè)數(shù)），第14行和第15行一共循環(huán)了m+n次。所以整個(gè)排序算法一共執(zhí)行了m+n+m+n次。我們用大寫字母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通常用大寫字母即O(M+N)。
　　這是一個(gè)非�？斓呐判蛩惴�。桶排序從1956年就開(kāi)始被使用，該算法的基本思想是由E.J. Issac和R.C. Singleton提出來(lái)的。之前我說(shuō)過(guò)，其實(shí)這并不是真正的桶排序算法，真正的桶排序算法要比這個(gè)更加復(fù)雜。但是考慮到此處是算法講解的第一篇，我想還是越簡(jiǎn)單易懂越好，真正的桶排序留在以后再聊吧。需要說(shuō)明一點(diǎn)的是：我們目前學(xué)習(xí)的簡(jiǎn)化版桶排序算法，其本質(zhì)上還不能算是一個(gè)真正意義上的排序算法。為什么呢？例如遇到下面這個(gè)例子就沒(méi)轍了。
　　現(xiàn)在分別有5個(gè)人的名字和分?jǐn)?shù)：huhu 5分、haha 3分、xixi 5分、hengheng 2分和gaoshou 8分。請(qǐng)按照分?jǐn)?shù)從高到低，輸出他們的名字。即應(yīng)該輸出gaoshou、huhu、xixi、haha、hengheng。發(fā)現(xiàn)問(wèn)題了沒(méi)有？如果使用我們剛才簡(jiǎn)化版的桶排序算法僅僅是把分?jǐn)?shù)進(jìn)行了排序。最終輸出的也僅僅是分?jǐn)?shù)，但沒(méi)有對(duì)人本身進(jìn)行排序。也就是說(shuō)，我們現(xiàn)在并不知道排序后的分?jǐn)?shù)原本對(duì)應(yīng)著哪一個(gè)人！這該怎么辦呢？不要著急，請(qǐng)看下節(jié)——冒泡排序。

　　……