冒泡排序 冒泡排序英語Bubble Sort又稱為泡式排序是一種簡單的排序算法它重複地走訪過要排序的數列一次比較兩個元素如果它們的順序錯誤就把它們交換過來走訪數列的工作是重複地進行直到沒有再需要交換也就是說該數列已經排序完成這個算法的名字由來是因為越小的元素會經由交換慢慢浮到數列的頂端 冒泡排序對 n displaystyle n 個項目需要O n  displaystyle n 的比較次數且可以原地排序儘管這個演算法是最簡單瞭解和實作的排序算法之一但它對於包含大量的元素的數列排序是很沒有效率的 冒泡排序是與插入排序擁有相等的漸近時間複雜度但是兩種算法在需要的交換次數卻很大地不同在最壞的情況冒泡排序需要 O  n   displaystyle On 次交換而插入排序只要最多 O  n  displaystyle On 交換冒泡排序的實現類似下面通常會對已經排序好的數列拙劣地執行 O  n   displaystyle On 而插入排序在這個例子只需要 O  n  displaystyle On 個運算因此很多現代的演算法教科書避免使用冒泡排序而用插入排序取代之冒泡排序如果能在內部迴圈第一次執行時使用一個旗標來表示有無需要交換的可能也可以把最優情況下的複雜度降低到 O  n  displaystyle On 在這個情況已經排序好的數列就無交換的需要若在每次走訪數列時把走訪順序反過來也可以稍微地改進效率有時候稱為雞尾酒排序因為演算法會從數列的一端到另一端之間穿梭往返 冒泡排序演算法的運作如下 比較相鄰的元素如果第一個比第二個大就交換它們兩個 對每一對相鄰元素作同樣的工作從開始第一對到結尾的最後一對這步做完後最後的元素會是最大的數 針對所有的元素重複以上的步驟除了最後一個 持續每次對越來越少的元素重複上面的步驟直到沒有任何一對數字需要比較 由於它的簡潔冒泡排序通常被用來對於程式設計入門的學生介紹演算法的概念