什么是冒泡排序

冒泡排序：在原數組中通過相鄰兩項元素的比較，交換而完成的排序算法。

算法核心

數組中相鄰兩項比較、交換。

算法復雜度

1. 時間復雜度
   實現一次排序找到最大值需要遍歷 n-1次(n為數組長度)
   需要這樣的排序 n-1次。 需要 (n-1) * (n-1) —> O(n^2)
   時間復雜度： O(n^2)

算法實現原理

我們以一次排序為例，了解冒泡排序是如何完成排序過程的。
相鄰兩項比較交換：

1. 23 和 7 比較， 23和7 交換位置（23>7大泡泡上升）
2. 23 和 33 比較， 位置不變。
3. 33 和15 比較， 33 和15交換位置。
4. 33 和 34 比較， 位置不變。
5. 34 和 12 比較， 34和12交換位置。
6. 第一輪排序結束： 34 作為最大的泡泡上升的數組的lenght-1位置。
   

參考實現

 for(int i =0; i < a.length; i++){for(int j =0; j < a.length - i-1; j++){if(a[j] > [j+1] ){int tmp = a[j];a[j] = a[j+1];a[j+1] = tmp;}}}

擴展問題

對于已經有序的數組，例如a[] = {1,2,3,4,5,6,7}, 那么冒泡排序還需要進行大量的比較，這樣效率并不高。
[解決方案] 我們可以做一個標記flag = true, 如果進入比較條件則改變flag的值，如果一輪循環之后，發現flag沒有變化，那么說明數組是有序的，則不需要繼續遍歷了。

 for(int i =0; i < a.length; i++){boolean flag = true;for(int j =0; j < a.length - i-1; j++){if(a[j] > [j+1] ){flag = false;int tmp = a[j];a[j] = a[j+1];a[j+1] = tmp;}}if(flag) break;}