這是我通過(guò)極客專欄《數(shù)據(jù)結(jié)構(gòu)與算法之美》學(xué)習(xí)后的思考，分享一下，希望對(duì)你有所幫助。上一篇文章 工作后，為什么還要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法 的思維導(dǎo)圖展現(xiàn)了這個(gè)專欄的內(nèi)容。

說(shuō)到算法中的排序，冒泡排序是最簡(jiǎn)單的一種排序算法了，甚至不學(xué)數(shù)據(jù)結(jié)構(gòu)與算法的同學(xué)都會(huì)使用它。但是你有沒(méi)有想過(guò)可以怎么優(yōu)化？

什么是冒泡排序：就像水慢慢燒開，氣泡從下往上越來(lái)越大那樣，第一次循環(huán)都把n個(gè)元素中最大的元素移動(dòng)至最后位置，第二次從前 n-1 個(gè)位置中找出最大元素放在最后，重復(fù)執(zhí)行，直到最后結(jié)果全部有序。

最基本的算法實(shí)現(xiàn)，無(wú)優(yōu)化版：

  def bubble_sort(collection):
    """
    無(wú)任何優(yōu)化版
    """
    compare_count=0
    length = len(collection)
    for i in range(length-1):
        print(collection) #方便查看數(shù)組的排序過(guò)程
        for j in range(length-1-i):
            compare_count+=1
            if collection[j] > collection[j+1]:
                tmp = collection[j]
                collection[j] = collection[j+1]
                collection[j+1] = tmp
    print(f"總循環(huán)次數(shù){compare_count}")
    return collection

下面來(lái)執(zhí)行一下，看看執(zhí)行的過(guò)程，及總循環(huán)次數(shù)：

    print("bubble_sort begin.")
    unsorted = [3,4,2,1,5,6,7,8]
    print("bubble_sort end: ",*bubble_sort(unsorted))

執(zhí)行結(jié)果如下：

bubble_sort begin.
[3, 4, 2, 1, 5, 6, 7, 8]
[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
總循環(huán)次數(shù)28
bubble_sort end:  1 2 3 4 5 6 7 8

通過(guò)排序的過(guò)程可以發(fā)現(xiàn)，在第 4 次冒泡時(shí)，數(shù)據(jù)已經(jīng)有序，因此可以加入判斷，如果本次循環(huán)沒(méi)有冒泡（交換），說(shuō)明數(shù)據(jù)已經(jīng)有序，可以直接退出，優(yōu)化后的代碼如下：

優(yōu)化一

def bubble_sort2(collection):
    """
    如果沒(méi)有元素交換，說(shuō)明數(shù)據(jù)在排序過(guò)程中已經(jīng)有序，直接退出循環(huán)
    """
    compare_count=0
    length = len(collection)
    for i in range(length-1):
        swapped = False
        print(collection)
        for j in range(length-1-i):
            compare_count+=1
            if collection[j] > collection[j+1]:
                swapped = True
                tmp = collection[j]
                collection[j] = collection[j+1]
                collection[j+1] = tmp
        if not swapped: break  # Stop iteration if the collection is sorted.
    print(f"總循環(huán)次數(shù){compare_count}")
    return collection

下面來(lái)執(zhí)行一下，看看執(zhí)行的過(guò)程，及總循環(huán)次數(shù)：

    print("bubble_sort2 begin.")
    unsorted = [3,4,2,1,5,6,7,8]
    print("bubble_sort2 end:",*bubble_sort2(unsorted))

執(zhí)行結(jié)果如下：

bubble_sort2 begin.
[3, 4, 2, 1, 5, 6, 7, 8]
[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
總循環(huán)次數(shù)22
bubble_sort2 end: 1 2 3 4 5 6 7 8

至此，還有沒(méi)有其他優(yōu)化方法呢？ 聰明的你可能看到了，總循環(huán)次數(shù)是比較多的，僅比未優(yōu)化版少了 6 次循環(huán)次數(shù)。有沒(méi)有辦法減少總循環(huán)次數(shù)呢？

觀察數(shù)據(jù)可以發(fā)現(xiàn)，數(shù)據(jù)已經(jīng)初始有序，可以分為兩部分，無(wú)序部分 3 4 2 1 和有序部分 5 6 7 8 ，每次循環(huán)如果能夠發(fā)現(xiàn)無(wú)序和有序的邊界，然后下次冒泡僅對(duì)無(wú)序部分進(jìn)行比較和冒泡，可大大減少比較次數(shù)（循環(huán)次數(shù)），從而加快速度。

問(wèn)題是，怎么發(fā)現(xiàn)這個(gè)邊界呢？
第一次冒泡的過(guò)程中，第一個(gè)元素 4 被移動(dòng)到下標(biāo)為【3】的位置（python 列表索引從 0 開始），位置 【3】就是有序部分的開始位置。

第二次冒泡的過(guò)程中，第一個(gè)元素 3 被移動(dòng)到下標(biāo)為【2】的位置（python 列表索引從 0 開始），位置 【2】就是有序部分的開始位置。
...
可以推斷出，一次冒泡的過(guò)程中，最后一個(gè)被交換的元素下標(biāo)即為無(wú)序和有序的邊界，因而下次冒泡，僅對(duì) 0 ~ 邊界 的元素冒泡即可大大減少循環(huán)次數(shù)。

優(yōu)化二：

def bubble_sort3(collection):
    """
    bubble_sort2的基礎(chǔ)上再優(yōu)化。
    優(yōu)化思路：在排序的過(guò)程中，數(shù)據(jù)可以從中間分為兩段，一段是無(wú)序狀態(tài)，另一段是有序狀態(tài)。
    每一次循環(huán)的過(guò)程中，記錄最后一個(gè)交換元素的公交車，它便是有序和無(wú)序狀態(tài)的邊界
    下一次僅循環(huán)到邊界即可，從而減少循環(huán)次數(shù)，達(dá)到優(yōu)化。
    """
    compare_count=0
    length = len(collection)
    last_change_index = 0 #最后一個(gè)交換的位置
    border = length-1 #有序和無(wú)序的分界線
    for i in range(length-1):
        swapped = False
        print(collection)
        
        for j in range(0,border):
            compare_count+=1
            if collection[j] > collection[j+1]:
                swapped = True
                collection[j], collection[j+1] = collection[j+1], collection[j]
                last_change_index = j
        if not swapped: break  # Stop iteration if the collection is sorted.

        border = last_change_index # 最后一個(gè)交換的位置就是邊界

    print(f"總循環(huán)次數(shù){compare_count}")
    return collection

下面來(lái)執(zhí)行一下，看看執(zhí)行的過(guò)程，及總循環(huán)次數(shù)：

    print("bubble_sort3 begin.")
    unsorted = [3,4,2,1,5,6,7,8]
    print("bubble_sort3 end:",*bubble_sort3(unsorted))

執(zhí)行結(jié)果如下：

bubble_sort3 begin.
[3, 4, 2, 1, 5, 6, 7, 8]
[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
總循環(huán)次數(shù)10
bubble_sort3 end: 1 2 3 4 5 6 7 8

可以看到結(jié)果的總循環(huán)次數(shù)為 10 ，與第二版相比，循環(huán)次數(shù)減少了一倍。

冒泡排序算法的性能分析：

1、執(zhí)行效率

最小時(shí)間復(fù)雜度：很好計(jì)算，最好的情況就是數(shù)據(jù)一開始就是有序的，因此一次冒泡即可完成，時(shí)間復(fù)雜度為 O(n)

最大時(shí)間復(fù)雜度：也很好計(jì)算，最壞的情況就是數(shù)據(jù)一開始就是倒序的，因此進(jìn)行 n-1 次冒泡即可完成，時(shí)間復(fù)雜度為 O(n^2)

平均時(shí)間復(fù)雜度，嚴(yán)格來(lái)說(shuō)平均時(shí)間復(fù)雜度就是加權(quán)平均期望時(shí)間復(fù)雜度，分析的時(shí)候要結(jié)合概率認(rèn)的知識(shí)，對(duì)于包含 n 個(gè)數(shù)據(jù)的數(shù)組，有 n! 種排序方式，不同的排列方式，冒泡排序的執(zhí)行時(shí)間肯定是不同的，如果要用概率認(rèn)的方法定量分析平均時(shí)間復(fù)雜度，涉及的數(shù)據(jù)推理會(huì)很復(fù)雜，這里有一種思路，通過(guò)有序度和逆序度這兩個(gè)概念來(lái)分析。有序度就是有順序的元素的個(gè)數(shù)，比如 3，1 ，2 這三個(gè)數(shù)據(jù)有有序度為1 即 （1，2） 一個(gè)，相反，逆序度為 2，即（3，2）（3，1）這兩個(gè)， 1， 2， 3 這三個(gè)數(shù)據(jù)的有序度為 3：（1，2）（1，3）（2，3），逆序度為 0，完全有序的數(shù)據(jù)序列的有序度也叫滿有序度。
有個(gè)公式

逆序度 = 滿有序度 - 有序度

排序的過(guò)程就是增加有序度，減少逆序度，最后達(dá)到滿有序度，說(shuō)明排序完成。逆序度也主濁元素的交換次數(shù)，最壞情況，初始狀態(tài)的有序度為 0 ，逆序度為 n*(n-1)/2 , 所以要進(jìn)行 n*(n-1)/2 次交換操作，最好情況，補(bǔ)充狀態(tài)完全有序，逆序度為 0 不需要進(jìn)行交換，這里平均交換次數(shù)我們可以取個(gè)平均值即 n*(n-1)/4。

而比較次數(shù)肯定比交換次數(shù)要多，因而平均情況下，無(wú)論算法怎么優(yōu)化，時(shí)間復(fù)雜度不會(huì)低于 n*(n-1)/4，也就是 O(n^2)。

2、內(nèi)存消耗

算法的內(nèi)存消耗可以通過(guò)空間復(fù)雜度來(lái)衡量，冒泡排序僅需要一個(gè)變量
tmp 來(lái)儲(chǔ)存交換的數(shù)據(jù)，因此空間復(fù)雜度為 O(1)，空間復(fù)雜度為 O(1) 的排序算法，也叫 原地排序算法

3、排序算法的穩(wěn)定性

針對(duì)排序算法，有一個(gè)重要的衡量指標(biāo)，就是穩(wěn)定性，這個(gè)概念是說(shuō)，如果待排序的序列中存在值相等的元素，經(jīng)過(guò)排序之后，相等元素之間原有的先后順序不變。假如有序列 4，1，2，2，我們把第一個(gè) 2 叫 2'，第二個(gè)2 叫 2''，如果排序之后，為1，2'，2''，4 那么這個(gè)排序算法就是穩(wěn)定的，否則就是不穩(wěn)定的。穩(wěn)不穩(wěn)定有什么用嗎，值都是一樣的？當(dāng)然有用，因?yàn)樵谲浖_發(fā)中，要排序的數(shù)據(jù)不單單是一個(gè)屬性的數(shù)據(jù)，而是有多個(gè)屬性的對(duì)象，假如對(duì)訂單排序，要求金額排序，訂單金額相同的情況下，按時(shí)間排序。最先想到的方法就是先對(duì)金額排序，在金額相同的訂單區(qū)間內(nèi)按時(shí)間排序，理解起來(lái)不難，有沒(méi)有想過(guò)，實(shí)現(xiàn)起來(lái)很復(fù)雜。

但是借助穩(wěn)定的排序算法，就很簡(jiǎn)單了，先按訂單時(shí)間排一次序，再按金額排一次序就可以了。

小結(jié)

對(duì)排序算法的分析無(wú)外乎時(shí)間復(fù)雜度（最好，最壞，平均），空間復(fù)雜度，穩(wěn)定性這些方面，只要理解其思路，弄明白其適用場(chǎng)景，不需要死記。優(yōu)化思路可以通過(guò)觀察分析得出，還有一點(diǎn)，冒泡排序雖然使用了數(shù)組存儲(chǔ)數(shù)據(jù)但是并沒(méi)有使用數(shù)組隨機(jī)訪問(wèn)的特性，因此改用鏈表這種存儲(chǔ)結(jié)構(gòu)，使用冒泡排序仍然是可以實(shí)現(xiàn)的，你可以嘗試下。

關(guān)注個(gè)人微信公眾號(hào) somenzz 與你一起學(xué)習(xí)。