簡(jiǎn)化版的<b>桶排序</b>不僅僅有上一節(jié)所遺留的問(wèn)題,更要命的是:它非常浪費(fèi)空間!例如需要排序數(shù)的范圍是 0~2100000000 之間,那你則需要申請(qǐng) 2100000001 個(gè)變量,也就是說(shuō)要寫(xiě)成 int a[2100000001]。因?yàn)槲覀冃枰?2100000001 個(gè)“桶”來(lái)存儲(chǔ) 0~2100000000 之間每一個(gè)數(shù)出現(xiàn)的次數(shù)。即便只給你 5 個(gè)數(shù)進(jìn)行排序(例如這 5 個(gè)數(shù)是 1、1912345678、2100000000、18000000 和 912345678),你也仍然需要 2100000001 個(gè)“桶”,這真是太浪費(fèi)空間了!還有,如果現(xiàn)在需要排序的不再是整數(shù)而是一些小數(shù),比如將 5.56789、2.12、1.1、3.123、4.1234這五個(gè)數(shù)進(jìn)行從小到大排序又該怎么辦呢?現(xiàn)在我們來(lái)學(xué)習(xí)另一種新的排序算法:<b>冒泡排序</b>。它可以很好地解決這兩個(gè)問(wèn)題。

<h5>冒泡排序的基本思想是:每次比較兩個(gè)相鄰的元素,如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。</h5>

1.例如我們需要將 12 35 99 18 76 這 5 個(gè)數(shù)進(jìn)行從大到小的排序。既然是從大到小排序,也就是說(shuō)越小的越靠后,你是不是覺(jué)得我在說(shuō)廢話,但是這句話很關(guān)鍵(∩_∩).
<br />2.首先比較第1位和第2位的大小,現(xiàn)在第1位是12,第2位是35。發(fā)現(xiàn)12比35要小,
<br />3.因?yàn)槲覀兿Ｍ叫≡娇亢舐?因此需要交換這兩個(gè)數(shù)的位置。交換之后這 5 個(gè)數(shù)的順序是35 12 99 18 76。
<br />4.按照剛才的方法,繼續(xù)比較第 2 位和第 3 位的大小,第 2 位是 12,第 3 位是 99。12 比99 要小,因此需要交換這兩個(gè)數(shù)的位置。交換之后這 5 個(gè)數(shù)的順序是 35 99 12 18 76。
<br />5.根據(jù)剛才的規(guī)則,繼續(xù)比較第 3 位和第 4 位的大小,如果第 3 位比第 4 位小,則交換位置。交換之后這 5 個(gè)數(shù)的順序是 35 99 18 12 76。
<br />6.最后,比較第 4 位和第 5 位。4 次比較之后 5 個(gè)數(shù)的順序是 35 99 18 76 12。
<br />7.經(jīng)過(guò) 4 次比較后我們發(fā)現(xiàn)最小的一個(gè)數(shù)已經(jīng)就位(已經(jīng)在最后一位,請(qǐng)注意 12 這個(gè)數(shù)的移動(dòng)過(guò)程),是不是很神奇?，F(xiàn)在再來(lái)回憶一下剛才比較的過(guò)程。每次都是比較相鄰的兩個(gè)數(shù),如果后面的數(shù)比前面的數(shù)大,則交換這兩個(gè)數(shù)的位置。一直比較下去直到最后兩個(gè)數(shù)比較完畢后,最小的數(shù)就在最后一個(gè)了。就如同是一個(gè)氣泡,一步一步往后“翻滾”,直到最后一位。所以這個(gè)排序的方法有一個(gè)很好 的名字“冒泡排序”。

Paste_Image.png

說(shuō)到這里其實(shí)我們的排序只將5個(gè)數(shù)中最小的一個(gè)歸位了。每將一個(gè)數(shù)歸位我們將其稱(chēng)為“一趟”。下面我們將繼續(xù)重復(fù)剛才的過(guò)程,將剩下的 4 個(gè)數(shù)一一歸位。
<br />好,現(xiàn)在開(kāi)始“第二趟”,目標(biāo)是將第 2 小的數(shù)歸位。首先還是先比較第 1 位和第 2 位,
<br />如果第 1 位比第 2 位小,則交換位置。交換之后這 5 個(gè)數(shù)的順序是 99 35 18 76 12。接下來(lái)你應(yīng)該都會(huì)了,依次比較第 2 位和第 3 位,第 3 位和第 4 位。注意此時(shí)已經(jīng)不需要再比較第 4位和第 5 位。因?yàn)樵诘谝惶私Y(jié)束后已經(jīng)可以確定第 5 位上放的是最小的了。第二趟結(jié)束之后這5個(gè)數(shù)的順序是99 35 76 18 12。
<br />“第三趟”也是一樣的。第三趟之后這 5 個(gè)數(shù)的順序是 99 76 35 18 12?，F(xiàn)在到了最后一趟“第四趟”。有的同學(xué)又要問(wèn)了,這不是已經(jīng)排好了嗎?還要繼續(xù)?當(dāng)然,這里純屬巧合,你若用別的數(shù)試一試可能就不是了。你能找出這樣的數(shù)據(jù)樣例來(lái)嗎?
請(qǐng)?jiān)囈辉嚒?br> <br />“冒泡排序”的原理是:每一趟只能確定將一個(gè)數(shù)歸位。即第一趟只能確定將末位上的數(shù)(即第 5 位)歸位,第二趟只能將倒數(shù)第 2 位上的數(shù)(即第 4 位)歸位,第三趟只能將倒數(shù)第 3 位上的數(shù)(即第 3 位)歸位,而現(xiàn)在前面還有兩個(gè)位置上的數(shù)沒(méi)有歸位,因此我們?nèi)匀恍枰M(jìn)行“第四趟”。
<br />“第四趟”只需要比較第 1 位和第 2 位的大小。因?yàn)楹竺嫒齻€(gè)位置上的數(shù)歸位了,現(xiàn)在第 1 位是 99,第 2 位是 76,無(wú)需交換。這 5 個(gè)數(shù)的順序不變?nèi)匀皇?99 76 35 18 12。到此排序完美結(jié)束了,5 個(gè)數(shù)已經(jīng)有 4 個(gè)數(shù)歸位,那最后一個(gè)數(shù)也只能放在第 1 位了。
<br />最后我們總結(jié)一下:如果有 n 個(gè)數(shù)進(jìn)行排序,只需將 n 1 個(gè)數(shù)歸位,也就是說(shuō)要進(jìn)行n-1 趟操作。而“每一趟”都需要從第 1 位開(kāi)始進(jìn)行相鄰兩個(gè)數(shù)的比較,將較小的一個(gè)數(shù)放在后面,比較完畢后向后挪一位繼續(xù)比較下面兩個(gè)相鄰數(shù)的大小,重復(fù)此步驟,直到最后一個(gè)尚未歸位的數(shù),已經(jīng)歸位的數(shù)則無(wú)需再進(jìn)行比較(已經(jīng)歸位的數(shù)你還比較個(gè)啥,浪費(fèi)表情)。
<br />這個(gè)算法是不是很強(qiáng)悍?記得我每次拍集體照的時(shí)候就總是被別人換來(lái)?yè)Q去的,當(dāng)時(shí)特別煩。不知道發(fā)明此算法的人當(dāng)時(shí)的靈感是否來(lái)源于此。啰里吧嗦地說(shuō)了這么多,下面是代碼。建議先自己嘗試去實(shí)現(xiàn)一下看看,再來(lái)看我是如何實(shí)現(xiàn)的。

 int a[100],i,j,n,t;
    
    scanf("%d",&n);         // 輸入一個(gè)數(shù) n 表示接下來(lái)有 n 個(gè)數(shù).
    for (i=0; i<n; i++) {
        scanf("%d",&a[i]);  // 循環(huán)讀入 n 個(gè)數(shù)到數(shù)組 a 中.
    }
    
    // 冒泡排序的核心部分
    for (i=1; i<=n-1; i++) {        // n個(gè)數(shù)排序, 只能進(jìn)行 n-1 趟.
        for (j=1; j<n-i; j++) {     // 從第1位開(kāi)始比較直到最后一個(gè)尚未歸位的數(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();

可以輸入以下數(shù)據(jù)進(jìn)行驗(yàn)證。

10
8 100 50 22 15 6 1 1000 999 0

運(yùn)行結(jié)果是:

0 1 6 8 15 22 50 100 999 1000

冒泡排序的核心部分是雙重嵌套循環(huán)。不難看出冒泡排序的時(shí)間復(fù)雜度是 O(N2)。這是一個(gè)非常高的時(shí)間復(fù)雜度。冒泡排序早在 1956 年就有人開(kāi)始研究,之后有很多人都嘗試過(guò)對(duì)冒泡排序進(jìn)行改進(jìn),但結(jié)果卻令人失望。如 Donald E. Knuth(中文名為高德納,1974 年圖靈獎(jiǎng)獲得者)所說(shuō):“冒泡排序除了它迷人的名字和導(dǎo)致了某些有趣的理論問(wèn)題這一事實(shí)之外,似乎沒(méi)有什么值得推薦的?！蹦憧赡芤獑?wèn):那還有沒(méi)有更好的排序算法呢?不要走開(kāi),請(qǐng)看下節(jié)——快速排序。