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

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

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

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

  def bubble_sort(collection):
    """
    無任何優(yōu)化版
    """
    compare_count=0
    length = len(collection)
    for i in range(length-1):
        print(collection) #方便查看數(shù)組的排序過程
        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

下面來執(zhí)行一下,，看看執(zhí)行的過程，及總循環(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

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

優(yōu)化一

def bubble_sort2(collection):
    """
    如果沒有元素交換,，說明數(shù)據(jù)在排序過程中已經(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

下面來執(zhí)行一下,，看看執(zhí)行的過程,，及總循環(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

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

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

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

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

優(yōu)化二：

def bubble_sort3(collection):
    """
    bubble_sort2的基礎(chǔ)上再優(yōu)化,。
    優(yōu)化思路：在排序的過程中，數(shù)據(jù)可以從中間分為兩段,，一段是無序狀態(tài),，另一段是有序狀態(tài)。
    每一次循環(huán)的過程中,，記錄最后一個交換元素的公交車,，它便是有序和無序狀態(tài)的邊界
    下一次僅循環(huán)到邊界即可，從而減少循環(huán)次數(shù),，達到優(yōu)化,。
    """
    compare_count=0
    length = len(collection)
    last_change_index = 0 #最后一個交換的位置
    border = length-1 #有序和無序的分界線
    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 # 最后一個交換的位置就是邊界

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

下面來執(zhí)行一下，看看執(zhí)行的過程,，及總循環(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í)行效率

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

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

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

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

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

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

2、內(nèi)存消耗

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

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

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

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

小結(jié)

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

關(guān)注個人微信公眾號 somenzz 與你一起學習,。