冒泡排序

• 簡介
• 代碼示例
• 排序過程
• 時間復雜度
• • 最差時間復雜度&平均時間復雜度
  • 最優時間復雜度
  • • 說明
    • 代碼示例
    • 動畫示例
• 空間復雜度
• 穩定性

簡介

????????冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序算法。以升序為例。順序輪序數組內元素。依次比較兩個相鄰的元素，如果順序錯誤就交換位置。比較過程最大值就像泡泡一樣從左往右慢慢浮到最右側。每輪遍歷后右側元素為最大值。
共進行n輪輪序，最終排序完成。

????????文章中使用的動畫網站地址，限 pc: 排序算法動畫http://www.donghuasuanfa.com/sort

????????算法一覽表：https://blog.csdn.net/ww753951/article/details/106862328

代碼示例

public static void bubbleSort(int arr[]) {for(int i =0 ; i<arr.length-1 ; i++) { for(int j=0 ; j<arr.length-1-i ; j++) { if(arr[j]>arr[j+1]) {int temp = arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp;}} }}

排序過程

????????下圖所示為升序排序。首先比較13和43，因為13小于43，所以無需更換位置。然后比較43和31，因為43大于31，所以更換位置，更換后滿足數組升序。最后再比較43和20，因為43大于20，所以更換位置。此過程為一輪比較，比較后保證最右側為最大值。
????????共需要重復上述n次比較，才能保證數組整體為升序。

時間復雜度

最差時間復雜度平均時間復雜度最優時間復雜度

$$O(N^2)$$	$$O(N^2)$$	$$O(N)$$

最差時間復雜度&平均時間復雜度

每輪比較的過程是比較相鄰的兩個元素。此過程的時間復雜度為N。每輪比較后找出最大的一個元素。然后共比較N輪。所以時間復雜度為：$$O(N^2)$$

最優時間復雜度

說明

最優時間復雜度為 O(N) 。算法需要優化。 設置一個全局變量是否交換過位置。在第一次循環后判斷如果沒有進行過交換處理，則跳出循環。

代碼示例

public static void bubbleSort(int arr[]) {boolean change = false;for(int i =0 ; i<arr.length-1 ; i++) { for(int j=0 ; j<arr.length-1-i ; j++) { if(arr[j]>arr[j+1]) {int temp = arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp;change = true;}} if(! change){break;}}}

其中 change 變量為變化變量。如果 交換過位置則設置為true。循環結束后判斷change變量是否為 false。如果為false，則未交換過位置，說明數組為已排序數組。可結束方法。

動畫示例

空間復雜度

空間復雜度: O(1) 。
冒泡排序為交換排序，當兩個元素大小不相同時，倆個元素交換位置，無需額外空間，所以空間復雜度為 O(1)。

穩定性

兩個元素的值相同時如果最終排序完成后位置不變，則為穩定排序，如果位置變更則為不穩定排序。
排序算法中，如果數字相同，則無需變更位置，避免額外的操作。
冒泡排序當兩個元素相等時，無需變更位置，也能達到排序效果，所以為穩定排序。

總結

以上是生活随笔為你收集整理的算法——排序——冒泡排序图解动画的全部內容，希望文章能夠幫你解決所遇到的問題。

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