### **冒泡排序算法思想** 兩兩比較待排序記錄的關鍵字，發現兩個記錄的次序相反時即進行交換，直到沒有反序的記錄為止。按照從小到大或者從大到小的順序進行交換,這樣一趟過去后,最大或最小的數字被交換到了最后一位。 > 依次比較相鄰的兩個數，將小數放在前面，大數放在后面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放后。然后比較第2個數和第3個數，將小數放前，大數放后，如此繼續，直至比較最后兩個數，將小數放前，大數放后。重復第一趟步驟，直至全部排序完成。 > > 第一趟比較完成后，最后一個數一定是數組中最大的一個數，所以第二趟比較的時候最后一個數不參與比較； > > 第二趟比較完成后，倒數第二個數也一定是數組中第二大的數，所以第三趟比較的時候最后兩個數不參與比較； > > 依次類推，每一趟比較次數-1； > > …… 冒泡排序算法的運作過程：（從小到大排序） 設數組a\[0..n-1\]長度為n, * 1．比較相鄰的前后二個數據，如果前面數據大于后面的數據，就將二個數據交換。 * 2．這樣對數組的第0個數據到n-1個數據進行一次遍歷后，最大的一個數據就“沉”到數組第n-1個位置。 * 3．n=n-1，如果n不為0就重復前面二步，否則排序完成。 * * * 例子為從小到大排序,原始待排序數組| 7 | 2 | 4 | 1 | 5 | 第一趟排序(外循環) 第一次兩兩比較7 > 2交換(內循環) 交換前狀態| 7 | 2 | 4 | 1 | 5 | 交換后狀態| 2 | 7 | 4 | 1 | 5 | 第二次兩兩比較,7 > 4交換 交換前狀態| 2 | 7 | 4 | 1 | 5 | 交換后狀態| 2 | 4 | 7 | 1 | 5 | 第三次兩兩比較,7 > 1交換 交換前狀態| 2 | 4 | 7 | 1 | 5 | 交換后狀態| 2 | 4 | 1 | 7 | 5 | 第四次兩兩比較,7 > 5交換 交換前狀態| 2 | 4 | 1 | 7 | 5 | 交換后狀態| 2 | 4 | 1 | 5 | 7 | 第二趟排序(外循環) 第一次兩兩比較2 < 4不交換 交換前狀態| 2 | 4 | 1 | 5 | 7 | 交換后狀態| 2 | 4 | 1 | 5 | 7 | 第二次兩兩比較,4 > 1交換 交換前狀態| 2 | 4 | 1 | 5 | 7 | 交換后狀態| 2 | 1 | 4 | 5 | 7 | 第三趟排序(外循環) 第一次兩兩比較2 > 1交換 交換后狀態| 2 | 1 | 4 | 5 | 7 | 交換后狀態| 1 | 2 | 4 | 5 | 7 | 第二次兩兩比較,2 < 4不交換 交換后狀態| 1 | 2 | 4 | 5 | 7 | 交換后狀態| 1 | 2 | 4 | 5 | 7 | 排序完畢,輸出最終結果1 2 4 5 7 * * * 冒泡排序時間復雜度，最好情況：數組已有序O(n)；最壞情況:數組反序O(n^2)，平均時間復雜度：O(n^2)。空間復雜度，冒泡排序是原地排序，空間復雜度為O(1)。冒泡排序算法是穩定的排序算法。 （1）時間復雜度 冒泡排序算法的最壞情況、最優情況、平均情況下的時間復雜度都是O（n^2） （2）空間復雜度 空間復雜度就是在交換元素時那個臨時變量所占的內存空間；最優的空間復雜度就是開始元素順序已經排好了，則空間復雜度為：O(1)；最差的空間復雜度就是開始元素逆序排序了，則空間復雜度為：O(n)；平均的空間復雜度為：O(1)；