排序算法之冒泡排序

一、思路

　　對一個序列中的元素，比較相鄰的元素。如果第一個比第二個大，就交換它們兩個，将大的元素放在右邊，此時右邊就稱為有序區，左邊就是無序區，不斷重複的對左邊區域相鄰元素進行比較，右邊有序區的元素不斷增加，最後完成排序。

具體看下面的例子：

• 遊标剛開始在第一個的位置，那麼就會比較3和5的值，3沒有5大，不換位置
• 遊标移動到第二個的位置，比較5和2，5比2大，更換位置，如圖右
• 遊标移動到第三個位置，比較5和9，不換位置

這樣循環一次叫做一趟（遊标不移動到最後一個位置，也就是第四個位置），最後的結果就是選出最大的值在右側，右側也就是有序區，然後再進行第二趟、第三趟。

二、實作

###range最右側不取
def bubble_sort(l):

    for i in range(len(l)-1): #循環的是趟數 i表示趟數
        for j in range(len(l)-i-1): #循環的是遊标 j表示的是遊标
            if l[j]>l[j+1]:
                l[j+1],l[j]=l[j],l[j+1] #調換順序
l=[3,5,2,9]
bubble_sort(l)
print(l) #[2, 3, 5, 9]      

分析：

　　i和j都是從0開始取值，當進行第0趟時，j的取值是2，但是使用的range函數，是以右側取不到，j的範圍是（0,3），當進行第1趟時，j的傳回是（0,2），一共可以進行（序列的長度-1）趟。

注意：

• 一共循環多少趟
• 無序區在左側
• 遊标的最大取值是無序區的倒數第二個值

三、優化

　　如果冒泡排序中執行一趟而沒有進行交換，則序列已經是有序的，可以直接結束算法。

###range最右側不取
def bubble_sort(l):

    for i in range(len(l)-1): #循環的是趟數 i表示趟數
        exchange=False
        for j in range(len(l)-i-1): #循環的是遊标 j表示的是遊标
            if l[j]>l[j+1]:
                l[j+1],l[j]=l[j],l[j+1] #調換順序
                exchange=True
        if not exchange:
            return 
l=[3,5,2,9]
bubble_sort(l)
print(l) #[2, 3, 5, 9]      

作者：iveBoy

出處：http://www.cnblogs.com/shenjianping/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須在文章頁面給出原文連接配接，否則保留追究法律責任的權利。