冒泡排序

所謂冒泡,，就是將元素兩兩之間進(jìn)行比較,，誰大就往后移動,，直到將最大的元素排到最后面,，接著再循環(huán)一趟,，從頭開始進(jìn)行兩兩比較,，而上一趟已經(jīng)排好的那個元素就不用進(jìn)行比較了,。（圖中排好序的元素標(biāo)記為黃色柱子）

上python代碼：

def bubble_sort(items):
    for i in range(len(items) - 1):
        for j in range(len(items) - 1 - i):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
    return items
list1 = [2,1,9,11,10,8,7]
print(bubble_sort(list1))

輸出結(jié)果：

[1, 2, 7, 8, 9, 10, 11]

這是冒泡排序最普通的寫法,，但你會發(fā)現(xiàn)它有一些不足之處,，比如列表：[1,2,3,4,7,5,6]，第一次循環(huán)將最大的數(shù)排到最后,，此時列表已經(jīng)都排好序了,，就是不用再進(jìn)行第二次、第三次...

冒泡排序優(yōu)化一：

設(shè)定一個變量為False,，如果元素之間交換了位置,，將變量重新賦值為True,最后再判斷，在一次循環(huán)結(jié)束后,，變量如果還是為False,，則brak退出循環(huán)，結(jié)束排序,。

def bubble_sort(items):
    for i in range(len(items) - 1):
        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 not flag:
            break
    return items

冒泡排序優(yōu)化二：攪拌排序 / 雞尾酒排序

上面這種寫法還有一個問題,，就是每次都是從左邊到右邊進(jìn)行比較，這樣效率不高,，你要考慮當(dāng)最大值和最小值分別在兩端的情況,。寫成雙向排序提高效率，即當(dāng)一次從左向右的排序比較結(jié)束后,，立馬從右向左來一次排序比較,。

python代碼：

def bubble_sort(items):
    for i in range(len(items) - 1):
        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, 0, -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

冒泡排序優(yōu)化三：

最后要考慮的情況就是，如果給你的不是列表,，而是對象,，或者列表里面都是字符串，那么上述的代碼也就沒有用了,，這時候你就要自定義函數(shù)了,，并將其當(dāng)成參數(shù)傳入bubble_sort函數(shù)

python代碼：

def bubble_sort(items, comp=lambda x, y: x > y):
    for i in range(len(items) - 1):
        flag = False
        for j in range(len(items) - 1 - i):
            if comp(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, 0, -1):
                if comp(items[j - 1],items[j]):
                    items[j], items[j - 1] = items[j - 1], items[j]
                    flag = True
        if not flag:
            break
    return items
list2 = ['apple', 'watermelon', 'pitaya', 'waxberry', 'pear']
print(bubble_sort(list2,lambda s1,s2: len(s1) > len(s2)))  #按照字符串長度從小到大來排序

輸出結(jié)果：

['pear', 'apple', 'pitaya', 'waxberry', 'watermelon']

類似的，當(dāng)有人叫你給一個類對象排序時,，也可以傳入lambda 自定義函數(shù),。

class Student():
    """學(xué)生"""
    def __init__(self, name, age):
        self.name = name
        self.age = age
    def __repr__(self):
        return f'{self.name}: {self.age}'
items1 = [
        Student('Wang Dachui', 25),
        Student('Di ren jie', 38),
        Student('Zhang Sanfeng', 120),
        Student('Bai yuanfang', 18)
    ]
print(bubble_sort(items1, lambda s1, s2: s1.age > s2.age))

輸出結(jié)果：按照年齡從小到大排序

[Bai yuanfang: 18, Wang Dachui: 25, Di ren jie: 38, Zhang Sanfeng: 120]

以上就是關(guān)于冒泡排序的原理，以及一些優(yōu)化寫法