簡化版的桶排序不僅僅有上一節(jié)所遺留的問題，更要命的是：它非常浪費空間！例如需要排序數(shù)的范圍是 0~2100000000 之間，那你則需要申請 2100000001 個變量，也就是說要寫成 int a[2100000001]。因為我們需要用 2100000001 個“桶”來存儲 0~2100000000 之間每一個數(shù)出現(xiàn)的次數(shù)。即便只給你 5 個數(shù)進行排序（例如這 5 個數(shù)是 1，1912345678，2100000000，18000000 和 912345678），你也仍然需要 2100000001 個“桶”，這真是太浪費了空間了！還有，如果現(xiàn)在需要排序的不再是整數(shù)而是一些小數(shù)，比如將 5.56789，2.12，1.1，3.123，4.1234 這五個數(shù)進行從小大排序又該怎么辦呢？現(xiàn)在我們來學習另一種新的排序算法：冒泡排序。它可以很好的解決這兩個問題。
冒泡排序的基本思想是：每次比較兩個相鄰的元素，如果他們的順序錯誤就把他們交換過來。
例如我們需要將 12 35 99 18 76 這 5 個數(shù)進行從大到小進行排序。既然是從大到小排序也就是說越小的越靠后，你是不是覺得我在說廢話，但是這句話很關鍵(∩_∩)。
首先比較第 1 位和第 2 位的大小，現(xiàn)在第 1 位是 12，第 2 位是 35。發(fā)現(xiàn) 12 比 35 要小，因為我們希望越小越靠后嘛，因此需要交換這兩個數(shù)的位置。交換之后這 5 個數(shù)的順序是 35 12 99 18 76。
按照剛才的方法，繼續(xù)比較第 2 位和第 3 位的大小，第 2 位是 12，第 3 位是 99。12 比 99 要小，因此需要交換這兩個數(shù)的位置。交換之后這 5 個數(shù)的順序是 35 99 12 18 76。
根據(jù)剛才的規(guī)則，繼續(xù)比較第 3 位和第 4 位的大小，如果第 3 位比第 4 位小，則交換位置。交換之后這 5 個數(shù)的順序是 35 99 18 12 76。
最后，比較第 4 位和第 5 位。4 次比較之后 5 個數(shù)的順序是 35 99 18 76 12。
經(jīng)過 4 次比較后我們發(fā)現(xiàn)最小的一個數(shù)已經(jīng)就位（已經(jīng)在最后一位，請注意 12 這個數(shù)的移動過程），是不是很神奇。現(xiàn)在再來回憶一下剛才比較的過程。每次都是比較相鄰的兩個數(shù)，如果后面的數(shù)比前面的數(shù)大，則交換這兩個數(shù)的位置。一直比較下去直到最后兩個數(shù)比較完畢后，最小的數(shù)就在最后一個了。就如同是一個氣泡，一步一步往后“翻滾”，直到最后一位。所以這個排序的方法有一個很好聽的名字“冒泡排序”。
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/2.1.png" alt="picture2.1" />
說道這里其實我們的排序只將 5 個數(shù)中最小的一個歸位了。每將一個數(shù)歸位我們將其稱為“一趟”。下面我們將繼續(xù)重復剛才的過程，將剩下的 4 個數(shù)一一歸位。
好現(xiàn)在開始“第二趟”，目標是將第 2 小的數(shù)歸位。首先還是先比較第 1 位和第 2 位，如果第 1 位比第 2 位小，則交換位置。交換之后這 5 個數(shù)的順序是 99 35 18 76 12。接下來你應該都會了，依次比較第 2 位和第 3 位，第 3 位和第 4 位。注意此時已經(jīng)不需要再比較第 4 位和第 5 位。因為在第一趟結束后已經(jīng)可以確定第 5 位上放的是最小的了。第二趟結束之后這 5 個數(shù)的順序是 99 35 76 18 12。
“第三趟”也是一樣的。第三趟之后這 5 個數(shù)的順序是 99 76 35 18 12。
現(xiàn)在到了最后一趟“第四趟”。有的同學又要問了，這不是已經(jīng)排好了嗎？還要繼續(xù)？當然，這里純屬巧合，你可以用別的數(shù)試一試可能就不是了。你能找出這樣的數(shù)據(jù)樣例來嗎？請試一試。
“冒泡排序”原理是：每一趟只能確定將一個數(shù)歸位。即第一趟只能確定將末位上的數(shù)（既第 5 位）歸位，第二趟只能將倒數(shù)第 2 位上的數(shù)（既第 4 位）歸位，第三趟只能將倒數(shù)第 3 位上的數(shù)（既第 3 位）歸位，而現(xiàn)在前面還有兩個位置上的數(shù)沒有歸位，因此我們?nèi)匀恍枰M行“第四趟”。
“第四趟”只需要比較第 1 位和第 2 位的大小。因為后面三個位置上的數(shù)歸位了，現(xiàn)在第 1 位是 99，第 2 位是 76，無需交換。這 5 個數(shù)的順序不變?nèi)匀皇?99 76 35 18 12。到此排序完美結束了，5 個數(shù)已經(jīng)有 4 個數(shù)歸位，那最后一個數(shù)也只能放在第 1 位了。
最后我們總結一下：如果有 n 個數(shù)進行排序，只需將 n-1 個數(shù)歸位，也就是說要進行 n-1 趟操作。而“每一趟”都需要從第 1 位開始進行相鄰兩個數(shù)的比較，將較小的一個數(shù)放在后面，比較完畢后向后挪一位繼續(xù)比較下面兩個相鄰數(shù)的大小，重復此步驟，直到最后一個尚未歸位的數(shù)，已經(jīng)歸位的數(shù)則無需再進行比較（已經(jīng)歸位的數(shù)你還比較個啥，浪費表情）。
這個算法是不是很強悍。記得我每次拍集體照的時候就總是被別人換來換去的，當時特別煩。不知道發(fā)明此算法的人當時的靈感是否來源于此。羅里吧嗦地說了這么多，下面是代碼。建議先自己嘗試去實現(xiàn)一下看看，再來看我是如何實現(xiàn)的。
#include <stdio.h>
int main()
{
int a[100],i,j,t,n;
scanf("%d",&n); //輸入一個數(shù)n，表示接下來有n個數(shù)
for(i=1;i<=n;i++) //循環(huán)讀入n個數(shù)到數(shù)組a中
scanf("%d",&a[i]);
//冒泡排序的核心部分
for(i=1;i<=n-1;i++) //n個數(shù)排序，只用進行n-1趟
{
for(j=1;j<=n-i;j++) //從第1位開始比較直到最后一個尚未歸位的數(shù)，想一想為什么到n-i就可以了。
{
if(a[j]<a[j+1]) //比較大小并交換
{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; }
}
}
for(i=1;i<=n;i++) //輸出結果
printf("%d ",a[i]);
getchar();getchar();
return 0;
}
可以輸入以下數(shù)據(jù)進行驗證
1081005022156110009990運行結果是
01681522501009991000
將上面代碼稍加修改，就可以解決第 1 節(jié)遺留的問題，如下。
#include <stdio.h>
struct student
{
char name[21];
char score;
};//這里創(chuàng)建了一個結構體用來存儲姓名和分數(shù)
int main()
{
struct student a[100],t;
int i,j,n;
scanf("%d",&n); //輸入一個數(shù)n
for(i=1;i<=n;i++) //循環(huán)讀入n個人名和分數(shù)
scanf("%s %d",a[i].name,&a[i].score);
//按分數(shù)從高到低進行排序
for(i=1;i<=n-1;i++)
{
for(j=1;j<=n-i;j++)
{
if(a[j].score<a[j+1].score)//對分數(shù)進行比較
{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; }
}
}
for(i=1;i<=n;i++)//輸出人名
printf("%s\n",a[i].name);
getchar();getchar();
return 0;
}
可以輸入以下數(shù)據(jù)進行驗證
5
huhu 5
haha 3
xixi 5
hengheng 2
gaoshou 8運行結果是
gaoshou
huhu
xixi
haha
hengheng冒泡排序的核心部分是雙重嵌套循環(huán)。不難看出冒泡排序的時間復雜度是 O(N2)。這是一個非常高的時間復雜度。冒泡排序早在 1956 年就有人開始研究，之后有很多人都嘗試過對冒泡排序進行改進，但結果卻令人失望。如 Knuth（Donald E. Knuth 中文名為高德納，1974 年圖靈獎獲得者）所說：“冒泡排序除了它迷人的名字和導致了某些有趣的理論問題這一事實之外，似乎沒有什么值得推薦的。”你可能要問：那還有沒有更好的排序算法呢？請期待下周更新——快速排序。
【一周一算法】算法 2：鄰居好說話——冒泡排序
http://bbs.ahalei.com/thread-4400-1-1.html
掃碼關注鍍金池微信號
手機訂課，優(yōu)惠多多