面試必考算法題之冒泡排序 (優化脫坑版)！
近期很多童鞋在討論大廠面試的算法題，有部分同學表示一臉懵逼，不知從何下手，還有一部分同學直接網上覆制的。
比如網上覆制冒泡排序算法，一不小心就複製了一個偽冒泡排序。
寫完了之後面試官問能優化嘛?
這個時候基本上都是一臉迷茫，不知道如何優化。
那麼接下來給大家來捋一捋冒泡排序的原理，只有搞懂排序的原理，才能更好的掌握，寫出真正的冒泡排序算法
一、冒泡排序原理
冒泡排序的規則,歸納幾點如下:
冒泡的規則：
◆ 每一輪獲取第一個數和後面的數據進行依次比較的過程，稱為一輪冒泡的過程
◆ 每一輪冒泡.都是先拿第一個數，依次比對相鄰的兩個數，如果前一個數比後一個數大，則交換他們的位置，這一輪比較完畢，會把最大的數放在最後面。
◆ 然後反覆重複上面的步驟（每一輪都能將前面數據中一個最大數，放到後面），直到一輪冒泡下來沒有任何數據需交互位置,此時數據已經為有序狀態
冒泡的次數：
◆ 假設列表的長度為n，冒泡排序是每次拿出來第一個元素，需要拿多少次呢？
應該是列表的長度減1，意味著每一個長度為n的列表，需要冒泡 n-1 次
每次冒泡比較的次數：
◆ 第一次冒泡，需要進行依次比較的次數為n-次，每一次冒泡，都能排好一個數據的順序，那麼隨著次的增加排好的數據也會越多，需要比較的數據就越少。
關係圖如下：
根據以上分析我們找出了冒泡次數和，比較次數的關係，接下來就可以通過代碼來實現了，實現代碼如下
二、Python實現冒泡排序
代碼實現：
注意：上面的代碼根據冒泡的思路,實現了排序，但是從嚴格意義上講還是由缺陷的，不能算是真正的冒泡排序，只是一個偽冒泡排序。
面試能夠把這個偽冒泡排序寫出來，大多數公司還是能過的。
三、代碼優化
眾所周知，進行冒泡排序的時候，當一輪冒泡下來，所有數據的順序都沒發生改變，那麼該數據就是一個有序列表了，這個時候就不會在進行下一輪冒泡了。
例如：
當我們使用一個有序列表來進行冒泡排序，那麼第一輪冒泡下來，所有的數據順序都不會發生改變。
那麼就不會再進行下一輪冒泡，這樣情況下時間複雜度為最優，只進行一輪冒泡，即O(n)。
1、缺陷分析
針對於時間複雜度最優的這種情況，在上面寫的偽冒泡排序算法中是不可能出現的，不管被排序的數據有沒有順序，都會進行n-1次冒泡，即最壞時間複雜度。
在這邊上面的偽冒泡只考慮了冒泡的過程，不管列表原來的順序，依次冒泡，全部去排一遍順序，沒有從時間複雜度的角度去做優化。
2、代碼優化
針對上述缺陷問題，接下來我們進行優化
代碼如下：
代碼解釋：上述代碼對之前的偽冒泡進行了優化，主要優化的點在於，我們每一次冒泡的時候，設置一個變量來記錄，當前這次冒泡數據的順序是否有發生改變，初始值設為False,當數據屬性發生改變時，就把這個值設為True。
一輪冒泡結束後 再去判斷，這個變量是否為False,如果為False則沒有發生改變，即數據有序，那麼接下來就可以直接返回數據，不需要再進行下一次冒泡。
提示：看完文章的小夥伴，以後面試遇到手撕冒泡排序的時候不要再寫偽冒泡啦！
閱讀更多 檸檬班軟件測試 的文章
