氣泡排序 Bubble Sort

下文是維基百科對Bubble Sort的定義

『氣泡排序英語:Bubble Sort)又稱為泡沫排序,是一種簡單的排序演算法。它重複地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換,也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

氣泡排序對{\displaystyle n}個項目需要O({\displaystyle n^{2}})的比較次數,且可以原地排序。儘管這個演算法是最簡單瞭解和實作的排序演算法之一,但它對於包含大量的元素的數列排序是很沒有效率的。

氣泡排序是與插入排序擁有相等的執行時間,但是兩種演算法在需要的交換次數卻很大地不同。在最壞的情況,氣泡排序需要{\displaystyle O(n^{2})}次交換,而插入排序只要最多{\displaystyle O(n)}交換。氣泡排序的實現(類似下面)通常會對已經排序好的數列拙劣地執行({\displaystyle O(n^{2})}),而插入排序在這個例子只需要{\displaystyle O(n)}個運算。因此很多現代的演算法教科書避免使用氣泡排序,而用插入排序取代之。氣泡排序如果能在內部迴圈第一次執行時,使用一個旗標來表示有無需要交換的可能,也可以把最優情況下的複雜度降低到{\displaystyle O(n)}。在這個情況,已經排序好的數列就無交換的需要。若在每次走訪數列時,把走訪順序反過來,也可以稍微地改進效率。有時候稱為雞尾酒排序,因為演算法會從數列的一端到另一端之間穿梭往返。

氣泡排序演算法的運作如下:

  1. 比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
  2. 對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。這步做完後,最後的元素會是最大的數。
  3. 針對所有的元素重複以上的步驟,除了最後一個。
  4. 持續每次對越來越少的元素重複上面的步驟,直到沒有任何一對數字需要比較。

由於它的簡潔,氣泡排序通常被用來對於程式設計入門的學生介紹演算法的概念。』

python 程式碼完成氣泡排序:

my_list= [16,62,93,94,65,96]
for i in range (len(my_list) -1):
    for j in range(len(my_list)-1):
        if my_list[j] < my_list[j+1]:
            my_list[j],my_list[j+1] =my_list[j+1],my_list[j]
print (my_list)>

但是,還有一個更快的方法,這是 python 內建的函數 sorted():

sorted( [16,62,93,94,65,96],reverse=True)
#reverse=True 是降幂排序

兩種方法,第一個可以讓初學者練習一下程式的寫法,第二個方法記下來,可以加快程式撰寫的速度。

程式碼在GitHub

發表迴響