前言

冒泡排序應該是很多小伙伴的最愛，簡單、直接、好理解；回顧以往參與和閱讀的項目，凡是牽涉自定義排序的算法，很大一部分都在用冒泡，其中很多都忽略了一個關鍵點；來，咱們細細品…

正文

1. 冒泡排序算法思想

冒泡排序（Bubble Sort）是屬于交換排序的一種，顧名思義，就是一個元素，依次和相鄰元素進行比較(升序或降序)，然后進行交換，這個過程就稱為冒泡。

算法思想

• 從前往后(或從后往前)依次比較待排序數據中相鄰的兩個元素的值，若符合交換條件，則進行交換，直到待排序數據比較完，這樣的過程就稱為“一趟”冒泡排序；最終完成排序，最多需要n-1趟排序;（n代表元素個數）。

• 每一趟排序都讓一個元素移動到最終的位置，在之后的冒泡排序中就無需再對比了。

• 如果在一趟排序過程中未發生“交換”，則算法可提前結束；?這是個關鍵，很多小伙伴會忽略。

2. 冒泡排序算法實現與解析

代碼實現(升序)：

實現

運行效果如下：

結果

步驟解析(升序)：

步驟

上圖步驟說明：

上圖中分三趟排序，每一趟的交換過程根據箭頭方向進行，其中每一行中的綠色方框代表的是當趟排序需要交互的數據。

第一趟中，對原始數據array開始遍歷，這里使用的是從往后的方式；

• 第一趟第一步，對比后面兩個元素9和3， 9大于3，所以9和3交換位置；

• 第一趟第二步，對比相鄰兩個元素1和3， 1小于3，不需要交換；

• 第一趟第三步，對比相鄰兩個元素6和1， 6大于1，所以6和1交換位置；

• 第一趟第四步，對比相鄰兩個元素5和1， 5大于1，所以5和1交換位置；

• 第一趟第五步，對比相鄰兩個元素2和1， 2大于1，所以2和1交換位置；遍歷完成，第一趟排序結束，得到結果1、2、5、6、3、9；這里確定了元素1的最終位置，后續不在需要對比了；代碼實現是這樣的，但為了好理解，畫圖的時候都體現了一下。

第二趟排序，接著第一趟的排序結果進行冒泡排序；

• 第二趟第一步，對比后面兩個元素3和9， 3小于9，不需要交換；

• 第二趟第二步，對比相鄰兩個元素6和3， 6大于3，所以6和3交換位置；

• 第二趟第三步，對比相鄰兩個元素5和3，5大于3，所以5和3交換位置；

• 第二趟第四步，對比相鄰兩個元素2和3， 2小于3，不需要交換；

• 第二趟第五步，對比相鄰兩個元素1和2， 1小于2，不需要交換；遍歷完成，第二趟排序結束，得到結果1、2、3、5、6、9；其實這步沒有，因為第一步已經確定了元素1的位置，可以不進行比對；這里只是便于理解虛擬出這一步。

第三趟排序，接著第二趟排序結果進行冒泡排序；

• 依次比較第二次結果的數據，最后發現沒有數據進行交互，則排序結束，數據已經排好序；不需要再遍歷，到此，整個冒泡排序完成；

3. 冒泡排序算法性能分析

時間復雜度

時間復雜度最壞情況就是待排序數據和要的結果完全逆序，則需要的比較的次數為：(n-1)+(n-2)+(n-3)+…+1，則最壞的時間復雜度為O(n²)。最好的時間復雜度就是待排序數據和要的結果完全一致，則比較n-1次即可，則最好的時間復雜度為O(n)；所以最后的平均時間復雜度為O(n²)。

空間復雜度
在算法核心部分只采用了固定的幾個中間變量(i,j,lengh,bChange)，所以算法過程中消耗的內存是一個常量，則空間復雜度為O(1)；

穩定性
由于在排序過程中是通過大于符號或小于符號進行比較，當等于時是不進行位置交換的，所以此算法是穩定的。

綜上所述，冒泡排序的時間復雜度為O(n²)，空間復雜度為O(1)，是不穩定算法；

總結

冒泡排序關鍵點一定要注意哦：

• 每趟排序會確定一個元素的最終位置，這個元素在下一趟排序中可以不進行比較了；

• 如果在一趟排序中沒有發生數據交換，則代表數據列表已經有序，可以終止排序啦；

從上面可以看出，冒泡排序雖然簡單，但需要依次遍歷元素進行比較，當數據元素過多時，比較次數就越多；那有沒有減少比較次數的解決方案呢；答案當然是肯定的，下期一起來聊聊快速排序。

感謝小伙伴的：點贊、收藏和評論，下期繼續~~~

一個被程序搞丑的帥小伙，關注"Code綜藝圈"，跟我一起學~~~

總結

以上是生活随笔為你收集整理的用得最多的冒泡排序是不是少了个关键点？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。