python數據結構之冒泡排序

冒泡排序是一種基礎排序演算法，在python中，我們利用列表的的方式來完成，它對列表中的元素進行重覆的遍歷，在遍歷的同時進行比較，如果兩個數沒有按照我們規定的順序進行排列，就按照我們預先設定好的是順序或者逆序輸出，類似於燒開水時的氣泡，主要操作如下：

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

時間複雜度

• 最優時間複雜度：O(n) （表示遍歷一次發現沒有任何可以交換的元素，排序結束。）
• 最壞時間複雜度：O(n2)
• 穩定性：穩定

附上完整代碼：

def bubble_sort(list):
    for j in range(len(list)-1,0,-1):
        for i in range (j):
            if list[i]>list[i+1]:
                list[i],list[i+1]=list[i+1],list[i]
List=[1,3,2,8,4,6,9,7]
bubble_sort(List)
print(List)