最近在招聘過程中，發現好多小伙伴最基礎的一些算法回答，接下來會做一個系列，把基礎的排序等算法采用動畫的形式做解析。
這是第一篇「冒泡排序」。
冒泡排序思想
冒泡排序(Bubble Sort)是一種交換排序，基本思想是「兩兩比較相鄰記錄，如果逆序則進行交換，直到沒有逆序的記錄為止」。
冒泡算法有很多種實現方式，我們在這里只列舉出來兩種實現方式來講解冒泡排序。
排序原理
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
- 對所有的元素重復以上的步驟，除了最后一個。
- 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
排序動畫
「冒泡排序示意動畫」
排序實現
「簡單的冒泡排序」
public static void sort(int[] arg) {
//冒泡排序
for (int i = 0; i < arg.length - 1; i++) {
for (int j = arg.length - 1; j > i; j--) {
if (arg[j] < arg[j - 1]) {//交換兩個數字
int temp = arg[j];
arg[j] = arg[j - 1];
arg[j - 1] = temp;
}
}
}
}
上面的代碼是根據動畫進行的實現，假設我們的數據為{7,5,1,3,2,6}，當i=0時，進行第一輪排序，變量j由5開始一直循環到1，逐個進行兩兩相鄰數字的比較，最后將數字最小的1排到第一位，當i=1時，進行第二輪排序，變量j由5開始一直循環到2，逐個進行兩兩相鄰數字的比較，最后將數字2排到第二位，依次進行i的下一輪比較，最終實現了數據的排序。
在這個過程中，由于數字像是浮起來的泡泡，所以稱之為冒泡排序。
排序優化
上面的算法還有優化的空間嗎？我們來看下面的這組數據，比如{6,5,4,3,1,2}，經過一輪排序已經變為了{6,5,4,3,2,1}，第二輪開始排序之后，還是{6,5,4,3,2,1}，數字的順序是沒有改變的，說明數字已經處于排序的狀態了，則沒有必要進行排序，所以還可以進行優化，代碼如下：
public void sort(int[] arg) {
//冒泡排序優化
for (int i = 0; i < arg.length - 1; i++) {
boolean isSorted = true;
for (int j = arg.length - 1; j > i; j--) {
if (arg[j] < arg[j - 1]) {//交換兩個數字
int temp = arg[j];
arg[j] = arg[j - 1];
arg[j - 1] = temp;
isSorted = false;//如果有數據交換，則isSorted為false
}
}
if (isSorted) {//isSorted為true，說明沒有進行數據交換，數據已經有序，則退出循環
break;
}
}
}
這樣經過上面的優化，冒泡排序會避免在數據已經有序的情況下繼續進行數據循環比較，性能得到了一定的提升。
冒泡排序的復雜度分析
數據正序的情況
比如數據為{6,5,4,3,2,1}，按照優化后的算法，只需要，只會進行5次比較，也就是n-1次的比較，所以時間復雜度為O{n}
數據逆序的情況
最壞的情況就是全部數據都是逆序，比如{6,5,4,3,2,1}，(n(n-1))/2次的數據操作和數據移動，所以總的時間復雜度為 (O(n2))
「綜合上面的情況，冒泡排序的時間復雜度為(O(n2))」
