面試官：手寫一個冒泡排序並對其改進（java實現）

前寫過一篇選擇排序，很多人把它和冒泡排序搞混了，這篇文章對冒泡排序進行一個分析，希望你能分清楚，也希望能在面試的時候能夠完美的回答出冒泡排序。

今年的工作據說是不好找，當然運氣佔很大一部分，但是實力越強運氣的成分就會相應降低吧。

一、認識冒泡排序

之前在學習排序算法的時候，冒泡排序往往都是第一個被介紹，就是因為其太簡單。冒泡排序很簡單：

依次比較相鄰的兩個數，將小數放在前面，大數放在後面。

注意：冒泡排序比較的是相鄰的兩個數，而選擇排序比較的整個隊列中最大或者是最小的數進行交換。

第一趟：首先比較第1個和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此繼續，直至比較最後兩個數，將小數放前，大數放後。（此時最後一個數一定是整個數組中的最大值）

第二趟：和第一趟一樣，不過最後一個數已經是最大值，比較到倒數第二個即可。（此時倒數第二個數一定是整個數組倒數第二大的數）

第三趟、第四趟以此類推即可。

我們來一張動圖演示一下：

上面的這張圖，你多看幾遍就理解了，每次排好都能選出來一哥當前數組的最大值。OK。如果你理解了之後，下面我們就開始寫代碼來實現一波。

二、代碼實現

1、基本實現

我們先來看一下基本的實現。

上面的這種寫法非常簡單，不過我們可能會發現，每一趟其實得到是一個值，這個值可能是當前數組的最大值又或者是最小值。

這樣做的缺點：

數組有一部分是本來就有序的，每一趟冒泡那麼將會在此部分浪費時間

2、改進

現在我們進行改進：如果我們換一種想法，每一趟掃描的時候，對那些有序的部分，設置一個標誌，如果為true表示發生了交換，如果為false，則沒有發生交換，那麼我們就可以直接跳過去了。

3、繼續改進

上面的這個雖然很好，必過還是有一定的侷限性，比如說數組的數據量很大有10000個，前面3000個雜亂無章，後面7000個都是排好的，而且還都比前3000個要大，這時候只需要比較前3000個即可。但是上面的改進算法，在對前3000個進行排序的時候，每次還都要和後7000個比較。這就顯得臃腫了。於是我們進行改進。

這個改進就是把flag變為具體的位置了，這樣我們就可以記錄末尾的邊界。這個邊界是排序與不排序的邊界。

三、總結

冒泡排序在筆試或者是面試的時候，涉及到的時間複雜度和空間複雜度都是第一種普通情況。因此它的時間複雜度是O(n^2)。雖然簡單，但是時間上確實是比較長。

我們一定要注意和選擇排序的區別，選擇排序是走一趟找出來一個最小的值和第一個同學交換位置。而冒泡排序是相鄰同學比較高低，這樣走一趟，最高個就沉到末尾了。