Curious George sees the world
 
氣泡排序 Bubble Sort
Python

氣泡排序 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

發表迴響