氣泡排序Bubble sort

Bubble sort 是最簡單的排序法之一，由於排序時每個元素會如同泡泡般，一個一個浮出序列頂部，因而得名。

由於其簡單好理解，名稱又有趣，常作為第一個學習的入門排序法 ... RustAlgorithmClub💡基礎概念漸進符號AsymptoticNotation🔍搜尋線性搜尋Linearsearch二元搜尋Binarysearch內插搜尋Interpolationsearch指數搜尋Exponentialsearch📚排序簡單排序插入排序Insertionsort選擇排序Selectionsort氣泡排序Bubblesort希爾排序Shellsort高效排序堆積排序Heapsort快速排序Quicksort合併排序Mergesort混合排序🚧內省排序Introsort🚧自適應合併排序Timsort🚧模式消除快速排序Pdqsort特殊排序計數排序Countingsort桶排序Bucketsort基數排序Radixsort🏠資料結構堆疊與佇列堆疊Stack佇列Queue雙端佇列Deque鏈結串列鏈結串列概述單向鏈結串列Singlylinkedlist🚧雙向鏈結串列Doublylinkedlist🚧循環鏈結串列Circularlinkedlist關聯容器關聯容器概述雜湊表Hashmap🚧有序映射表Orderedmap🚧多重映射表Multimap集合Set布隆過濾器Bloomfilter🧵字串處理漢明距離Hammingdistance萊文斯坦距離Levenshteindistance🚧最長共同子字串Longestcommonsubstring貢獻指南404 Light(default) Rust Coal Navy Ayu RustAlgorithmClub Bubblesort是最簡單的排序法之一，由於排序時每個元素會如同泡泡般，一個一個浮出序列頂部，因而得名。

由於其簡單好理解，名稱又有趣，常作為第一個學習的入門排序法。

不過其效率不彰，甚至不如同為quardratictime的insertionsort。

Bubblesort的原理很平凡，就是相鄰兩兩元素互相比較，如果大小順序錯了，就置換位置。

再往下一個pair比較。

Bubblesort的特性如下： 又稱為sinkingsort。

穩定排序：相同鍵值的元素，排序後相對位置不改變。

原地排序：不需額外花費儲存空間來排序。

比較兩個相鄰元素，若首個元素比次個元素大，置換兩者的位置。

依序對相鄰元素執行步驟一，直到抵達序列頂端，此時頂端元素排序完成。

重複步驟1-2的整個序列疊代，直到任何一次疊代沒有執行元素置換。

Swfung8-CCBY-SA3.0 給定一組序列[5,3,8,7,2]，以bubblesort遞增排序。

以ASCIIdiagram表示： 第一次疊代 **** [5,3,8,7,4]->[3,5,8,7,4]#置換3與5 **** [3,5,8,7,4]->[3,5,8,7,4]#不需置換 **** [3,5,8,7,4]->[3,5,7,8,4]#置換7與8 **** [3,5,7,8,4]->[3,5,7,4,8]#置換4與8，8已排好序 第二次疊代 **** [3,5,7,4,8]->[3,5,7,4,8]#不需置換 **** [3,5,7,4,8]->[3,5,7,4,8]#不需置換 **** [3,5,7,4,8]->[3,5,4,7,8]#置換4與7 **** [3,5,4,7,8]->[3,5,4,7,8]#不需置換 naïvebubblesort會跑完整個序列，即是已排序完成。

第三次疊代 **** [3,5,4,7,8]->[3,5,4,7,8]#不需置換 **** [3,5,4,7,8]->[3,4,5,7,8]#置換4與5 **** [3,5,4,7,8]->[3,4,5,7,8]#不需置換 **** [3,5,4,7,8]->[3,4,5,7,8]#不需置換 第四次疊代 **** [3,4,5,7,8]->[3,4,5,7,8]#不需置換 **** [3,4,5,7,8]->[3,4,5,7,8]#不需置換 **** [3,4,5,7,8]->[3,4,5,7,8]#不需置換 **** [3,4,5,7,8]->[3,4,5,7,8]#不需置換 很簡單的排序法！ Complexity Worst$O(n^2)$ Best$O(n)$ Average$O(n^2)$ Worstspace$O(1)$auxiliary Bubblesort總共需要$n-1$次疊代，每次疊代至少需要執行$n-1-i$置換（$i$為第幾次疊代），總共需要疊代 $$\sum_{i=0}^{n-1}(n-i-1)=n^2-\sum_{i=0}^{n-1}i-n=n^2-\frac{n(n-1)}{2}-n=\frac{n^2}{2}-\frac{n}{2}$$ 次，因此，時間複雜度為$O(n^2)$。

Bubblesort在已排序完成的序列上，只需要疊代序列一次，發現完全沒有置換任何元素，即停止排序，可達到最佳時間複雜度。

Bubblesort簡單實作如下： #![allow(unused)] fnmain(){ pubfnbubble_sort(arr:&mut[i32]){ letmutswapped=true;//1 whileswapped{ swapped=false; foriin1..arr.len(){//2 ifarr[i-1]>arr[i]{ arr.swap(i-1,i); swapped=true//3 } } } } } 建立一個旗標，標誌該次疊代是否有元素置換。

內層迴圈依序比較兩兩相鄰元素。

若有任何置換動作，將旗標標誌為「已置換（true）」。

倘若記錄已排好序的元素位置，雖然複雜度仍是$O(n^2)$，但如此以來，每次疊代都可少一次元素比較，對比較操作成本高的語言或實作來說，仍不失為最佳化的方法。

程式碼如下： #![allow(unused)] fnmain(){ pubfnbubble_sort_optimized(arr:&mut[i32]){ letmutnew_len:usize; letmutlen=arr.len();//1 loop{ new_len=0; foriin1..len{ ifarr[i-1]>arr[i]{ arr.swap(i-1,i); new_len=i;//2 } } ifnew_len==0{//3 break; } len=new_len;//4 } } } 將當前的序列長度記錄到len。

內層迴圈負責比較、置換，以及記錄未排序部分的序列長度到new_len。

若未排序部分new_len為零，代表排序完成。

外層迴圈將新長度值new_len賦予len，下一次疊代就可少做一次比較。

Wiki:Bubblesort SortingGIFwascreatedbySwfung8(Ownwork)CCBY-SA3.0viaWikimediaCommons.