冒泡排序及改進—Python實作

冒泡排序

冒泡排序的算法思路在于對無序表進行多趟比較交換，每趟包括了兩次兩兩相鄰比較，并将逆序的資料項交換位置，最終能将本趟的最大項就位，經過n-1趟比較，實作整表排序。圖表展示

代碼

def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp=alist[i]
                alist[i]=alist[i+1]
                alist[i+1]=temp
alist=[52,312,54,7,3,2,56,34,65]
bubbleSort(alist)
print(alist)
           

性能改進

如果某趟比對沒有發生任何交換，說明清單已經排好序，可以提前結束算法

def shortBubbleSort(alist):
    exchanges=True
    passnum=len(alist)-1
    while passnum >0 and exchanges:
        exchanges=False
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                exchanges=True
                temp=alist[i]
                alist[i]=alist[i+1]
                alist[i+1]=temp
        passnum-=1
alist=[52,312,54,7,3,2,56,34,65]
shortBubbleSort(alist)
print(alist)