冒泡排序（Bubble Sort）

基本描述：冒泡排序是一種簡單的排序算法伴找。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素兄纺，如果它們的順序錯誤就把它們交換過來大溜。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成估脆。這個算法的名字由來是因?yàn)樵叫〉脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端钦奋。

算法描述

1.比較相鄰的元素。如果第一個比第二個大疙赠，就交換它們兩個付材；
2.對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對圃阳，這樣在最后的元素應(yīng)該會是最大的數(shù)厌衔；
3.針對所有的元素重復(fù)以上的步驟，除了最后一個限佩；
4.重復(fù)步驟1-3葵诈，直到排序完成。

Bubble.gif

如圖：藍(lán)色柱子表示需要比較的序列祟同，黃色柱子表示已經(jīng)排好序的值作喘，綠色柱子表示正在比較的兩個數(shù)。

def bubble_sort(items):
    '''
    冒泡排序：
    ：param items： 亂序的列表
    ：return: 排序好的列表
    '''
    for i in range(len(items) - 1):   # 外輪循環(huán)遍歷列表晕城，len(items) - 1
        for j in range(len(items) - 1 - i):   # 內(nèi)輪循環(huán)遍歷比較泞坦， len(items) - 1 - i
            if items[j] > items[j + 1]:  # 如果前面的數(shù)大于后面的，交換位置
                items[j], items[j + 1] = items[j + 1], items[j]
    return items

例子

list = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(bubble_sort(list))

優(yōu)化方法（雞尾酒排序）

上面這種寫法還有一個問題砖顷，就是每次都是從左邊到右邊進(jìn)行比較贰锁，這樣效率不高，你要考慮當(dāng)最大值和最小值分別在兩端的情況滤蝠。寫成雙向排序提高效率豌熄，即當(dāng)一次從左向右的排序比較結(jié)束后，立馬從右向左來一次排序比較物咳。這種方法也稱之為雙向冒泡排序锣险。

算法描述

1.先對數(shù)組從左到右進(jìn)行冒泡排序（升序），則最大的元素去到最右端
2.再對數(shù)組從右到左進(jìn)行冒泡排序（降序）览闰，則最小的元素去到最左端
3.以此類推芯肤，依次改變冒泡的方向，并不斷縮小未排序元素的范圍压鉴，直到最后一個元素結(jié)束

Cocktail.gif

def bubble_sort2(items):
    '''
    雞尾酒排序：
    ：param items： 亂序的列表
    ：return: 排序好的列表
    '''
    for i in range(len(items) - 1):  # 外輪循環(huán)
        flag = False
        for j in range(len(items) - 1 - i):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                flag = True
        if flag:
            flag = False
            for j in range(len(items) - 2 - i, i, -1):
                if items[j - 1] > items[j]:
                    items[j], items[j - 1] = items[j - 1], items[j]
                    flag = True
        if not flag:
            break
    return items

例子

bubble_sort2(list)

總結(jié)

今天學(xué)習(xí)的是排序算法中最常見的冒泡算法崖咨。
冒泡排序算法的特點(diǎn)是將相鄰的兩個數(shù)排序找到最大的數(shù)，然后像氣泡一樣浮到頂端油吭，這個算法有一個缺點(diǎn)击蹲，不論先前排序如何署拟，每次只確定一個最大值。
雞尾酒排序是冒泡排序的一種改進(jìn)算法际邻，即芯丧，第一輪排序找最大值類似氣泡一樣浮到頂端，然后從頂端找最小值世曾，類似石頭一樣沉到底端缨恒。
在飛的小豬

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者