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