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

　　……