冒泡排序&優化：Python實作（低級排序法）冒泡排序&優化：Python實作（低級排序法）

冒泡排序&優化：Python實作（低級排序法）

維基百科：

冒泡排序（英語：Bubble Sort）是一種簡單的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端，時間複雜度O(n²)。

說白了，步驟是這樣子的：

1. 清單每相鄰的兩個數若果前面的數比後面的數大(小),則交換兩個數
2. 一趟排序完成後，則無序區減少一個數，有序區增加一個數

3. 核心是：大數下沉，小數上冒。每一次總能找到一個最大的或者最小的

   不啰嗦了，上代碼

def bubble_sort(li):
    for i in range(len(li)-1):#外循環表示排序的趟數4
        for j in range (0,len(li)-1-i):#内循環表示每趟比較的次數
            if li[j] > li[j+1]:#由小到大排序
             li[j],li[j+1] = li[j+1],li[j]#這裡需要注意的兩輪循環的次數。在第一輪循環的時候，次數為數組長度減1。第二輪循環的次數為剩餘需要排序數量。這個是這個算法的精華
    return li
def scan(a = ",", b = "請輸入一組值",c = "w"):#收集使用者需要排序的資料
    d = input(b + "：")
    f = d.split(a)
    g = []
    for q in f:
        if c == "w":    #當輸入c="w"時，轉化為整數數值賦給清單
            g.append(int(q))
        elif c == "e":   #當c="e"時，轉化為浮點數付給清單
            g.append(float(q))
        elif c == "r":   #當c="e"時，把字元串值賦給清單
            g.append(q)
    return g
li = scan()
li = bubble_sort(li)
print(li)
           

冒泡排序代碼優化

如果清單中有一段是有序的，上面的代碼依然會樂此不疲的一趟一趟的比較，這大大減小了效率，根據這個思想我們對代碼進行優化：

若本次冒泡排序過程中沒有任何交換，說明序列已經有序，停止交換，說白了，就是如果一趟中沒有任何交換就說明這一趟中所有的資料是一個有序的，剩下的資料不需要再進行排序了

代碼如下

def bubble_sort(li):
    for i in range(len(li)-1):#外循環表示排序的趟數4
        exchange = False#設定一個是否進行交換的量，先假設設沒有發生交換
        for j in range (len(li)-1-i):#内循環表示每趟比較的次數
            if li[j] > li[j+1]:#由小到大排序
                li[j],li[j+1] = li[j+1],li[j]
                exchange = True#發生了交換
        if not exchange:# 在一趟過程中沒有發生交換，就認為已經排好序了，不需要交換，退出循環
            break
li = []
while 1:#收集使用者需要排序的資料
    a = input('請輸入您要查詢的數字，回車輸入選一個資料，#結束：')
    if a=='#':
        break
    a = int(a)
    li.append(a)
print(f'您要排序的清單是{li}')
bubble_sort(li)
print(f'冒泡排序完成後的清單是{li}')