情況是這樣子的，當時和面試官聊的感覺還可以，就在他覺得好像差不多快結束的時候，面試官給他扔了個題：“我這剛好有紙和筆，你來寫個冒泡排序吧。”

這位讀者心里一慌，為什么慌，倒并不是因為不會寫，因為作為一個程序員，冒泡排序基本上沒有不會寫的，而是事發突然，感覺不太妙。當時他是這么寫的：

public void bubbleSort(int[] source) {
    for(int i = source.length - 1; i > 0; i--) {
        for(int j = 0; j < i; j++) {
            if(a[j] > a[j+1])
                 //交換，具體實現略
                 swap(source, j, j+1); 
        }
    }
}

果不其然，他寫了之后，面試官就問他，這種寫法有沒有什么問題？能否繼續優化？結果還真沒答上來。（看到這里，讀者們不妨也先思考下如何優化。）

今天就這個冒泡排序，我們再多聊幾句，回歸一下經典。也希望以后有朋友實習也好，校招也罷，不要再栽在同樣的問題上了。

冒泡排序算法的時間復雜度高，如果不清楚算法復雜度如何計算，可以參考下這篇文章：循序漸進帶你學習時間復雜度和空間復雜度。但是冒泡排序簡單，基本流程是：每一輪從頭開始兩兩比較，將較大的項放在較小項的右邊，這樣每輪下來保證該輪最大的數在最右邊。如何實現？就如上面這位朋友所寫的那樣，基本上大家都會寫。

但是今天主要討論的是如何優化，有人可能會說，這是再簡單不過的算法了，還有什么好優化的？確實，上面這段代碼沒有毛病，但的確是有可優化之處的。

我們可以假設一種場景，比如 8 1 2 3 5 7，進行一次排序之后，結果就變成了 1 2 3 5 7 8，那我們還有必要再像上面代碼里那樣繼續循環下去嗎？肯定沒有必要了，因為這已經是最終結果了。

針對上面的代碼，我們優化的點主要在于：假如某一趟排序之后已經有序，我們需要減少排序的趟數。否則就做了很多無用功。

針對這個問題，我們可以考慮在算法中加入一個布爾變量，來標識該輪有沒有進行數據的交換，若在某一趟排序中未發現數據位置的交換，則說明待排序的無序區中所有的項均已滿足排序后的結果。那么就沒有必要再次排序下去了。可以如下改造：

public void bubbleSort(int[] source) {
    boolean exchange;
    for(int i = source.length - 1; i > 0; i--) {
        exchange = false;
        for(int j = 0; j < i; j++) {
            if(a[j] > a[j+1]) {
                swap(source, j, j+1);
               exchange = true;
            }
        }
        if(!exchange) return;
    }
}

這樣就優化完了，其實代碼邏輯很簡單，通過一個布爾變量即可監控一趟過程有沒有進行數據交換。

冒泡排序最好的情況是初始狀態是正序的，一次掃描即可完成排序，所以最好的時間復雜度為O(N)；最壞的情況是反序的，此時最壞的時間復雜度為O(N^2)。平均情況，每輪N/2次循環，N輪時間復雜度為O(N^2)。所以它并不是個好的排序算法。這個問題的討論就到此結束，如果有更好的優化算法也歡迎留言討論。

冒泡排序并不好，但為什么面試官還會去問？針對這件事情，我們需要注意什么呢？

1. 經典的東西，可能已經不用了，但是從經典的東西身上，我們能學到的還有很多，否則也不會成為經典。特別是那些面試經常被問到的，總有它存在的合理性。

2. 教科書上的東西不代表實戰，所以很多時候考慮到非理想情況下，就可能不那么適用了。面試官往往更加注重的是在不適用的情況下，面試者是如何應對的。面試官更加看重的是面試者的思路。

3. 應屆生不能浮躁，特別是在準備面試的時候，一定要步步為營，切忌好高騖遠，淺嘗輒止，多學習學習經典的數據結構和算法（最常用的經典數據結構和算法匯總），多做做算法題還是很有必要的。