冒泡排序的基本思想是：每次比較兩個相鄰的元素，如果它們的順序錯誤就把它們交換過來莉御。

例如我們需要將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ù)就在最后一個了渣玲。就如同是一個氣泡，一步一步往后“翻滾”弟晚，直到最后一位忘衍。所以這個排序的方法有一個很好聽的名字“冒泡排序”。

說到這里其實我們的排序只將5 個數(shù)中最小的一個歸位了卿城。每將一個數(shù)歸位我們將其稱為“一趟”枚钓。下面我們將繼續(xù)重復(fù)剛才的過程，將剩下的4 個數(shù)一一歸位瑟押。

好搀捷，現(xiàn)在開始“第二趟”，目標是將第2 小的數(shù)歸位多望。首先還是先比較第1 位和第2 位指煎，如果第1 位比第2 位小蹋偏，則交換位置。交換之后這5 個數(shù)的順序是99 35 18 76 12至壤。接下來你應(yīng)該都會了威始，依次比較第2 位和第3 位，第3 位和第4 位像街。注意此時已經(jīng)不需要再比較第4位和第5 位黎棠。因為在第一趟結(jié)束后已經(jīng)可以確定第5 位上放的是最小的了。第二趟結(jié)束之后這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)匀皇?9 76 35 18 12绒怨。到此排 序完美結(jié)束了纯赎，5 個數(shù)已經(jīng)有4 個數(shù)歸位，那最后一個數(shù)也只能放在第1 位了南蹂。 最后我們總結(jié)一下：如果有n 個數(shù)進行排序犬金，只需將n?1 個數(shù)歸位，也就是說要進行n-1 趟操作。而“每一趟”都需要從第1 位開始進行相鄰兩個數(shù)的比較晚顷，將較小的一個數(shù)放在后面峰伙，比較完畢后向后挪一位繼續(xù)比較下面兩個相鄰數(shù)的大小，重復(fù)此步驟该默，直到最后一個尚未歸位的數(shù)瞳氓，已經(jīng)歸位的數(shù)則無需再進行比較（已經(jīng)歸位的數(shù)你還比較個啥，浪費表情）栓袖。這個算法是不是很強悍匣摘？記得我每次拍集體照的時候就總是被別人換來換去的，當時特別煩裹刮。不知道發(fā)明此算法的人當時的靈感是否來源于此音榜。啰里吧嗦地說了這么多，下面是代碼捧弃。建議先自己嘗試去實現(xiàn)一下看看赠叼，再來看我是如何實現(xiàn)的。

```

public class BubbleSort{

public static void main(String[] args){

int score[] = {67, 69, 75, 87, 89, 90, 99, 100};

for (int i = 0; i < score.length -1; i++){? ? //最多做n-1趟排序

for(int j = 0 ;j < score.length - i - 1; j++){? ? //對當前無序區(qū)間score[0......length-i-1]進行排序(j的范圍很關(guān)鍵违霞，這個范圍是在逐步縮小的)

if(score[j] < score[j + 1]){? ? //把小的值交換到后面

int temp = score[j];

score[j] = score[j + 1];

score[j + 1] = temp;

}

}

System.out.print("第" + (i + 1) + "次排序結(jié)果：");

for(int a = 0; a < score.length; a++){

System.out.print(score[a] + "\t");

}

System.out.println("");

}

System.out.print("最終排序結(jié)果：");

for(int a = 0; a < score.length; a++){

System.out.print(score[a] + "\t");

}

}

}

```

冒泡排序的核心部分是雙重嵌套循環(huán)嘴办。不難看出冒泡排序的時間復(fù)雜度是O(N2)。這是一個非常高的時間復(fù)雜度葛家。冒泡排序早在1956 年就有人開始研究户辞，之后有很多人都嘗試過對冒泡排序進行改進泌类，但結(jié)果卻令人失望癞谒。如Donald E. Knuth（中文名為高德納，1974 年圖靈獎獲得者）所說：“冒泡排序除了它迷人的名字和導(dǎo)致了某些有趣的理論問題這一事實之外刃榨，似乎沒有什么值得推薦的弹砚。”你可能要問：那還有沒有更好的排序算法呢枢希？不要走開桌吃，請看下節(jié)——快速排序。