冒泡排序
冒泡排序算法時間複雜度最壞的情況是，最好的，說明冒泡排序是可以優化的，就看你有沒有去發現。
冒泡排序算法的過程是兩個元素比較的大小，是典型的交換排序算法。快速排序算法和雞尾酒排序算法也屬于交換排序。
排序方法
比較相鄰的元素，判斷是否符合要求，如果不符合就交換位置來達到排序的目的。
對每一對相鄰元素做相同的工作，從開始第一對到結尾的最後一對，一次周遊之後，最後一個元素是最大（小）的數。
第二次周遊重複以上操作，因為最後一個元素已經确定位置，減少一次計算。以此類推。
示例
通過一個示例來了解基本的冒泡排序算法，假設目前我們有一個數組a，裡面元素是：5，6，1，7，2，4，3
初始狀态
視訊動畫
Code
Result
優化
可以發現，我們到第4次周遊的時候，發現已經排序完了，但是代碼還是會繼續判斷是否符合要求。
仔細看看，第4次周遊之前還有一次元數位置交換，第5次周遊之前已經沒有了交換。
是以我們可以設定一個标志位，用來表示目前i+1次是否還有交換，如果有就進行下一趟周遊，如果沒有，則說明目前數組已經排完序，沒有再進行比較的判斷了。
好了這是第一次的優化，減少了計算次數。看上面的執行過程，你覺得還有什麼辦法使得時間複雜度盡可能少一點呢？
優化，還能再繼續優化
我覺得還能再繼續優化，為了更直白一點，這次我們換一個數組，數組元素為：4, 3, 2, 1, 5, 6, 7
看到上面的結果可以看出一個問題，裡面的for循環明明已經歸位了，又增加了不必要的計算次數。問題是在于j
我們可以這樣解決，進行第1次周遊之前，記錄交換元素的最後一個位置lastPostion。交換後的元素後一個肯定要比前面一個元素大，lastPostion就記錄前面一個元素就可以了。
進行一次周遊之後，lastPostion的記錄有了，裡面的for循環進行下标0到lastPostion的數組就可以了，lastPostion後面的一串數組由于前面第一次循環驗證過了，沒有任何交換的元素，說明也是排好序的。
------End------
來源 | 算法無遺策
作者 | 我脫下短袖