這是我通過極客專欄《數(shù)據(jù)結(jié)構(gòu)與算法之美》學(xué)習(xí)后的思考，分享一下，希望對(duì)你有所幫助。上一篇文章 工作后，為什么還要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法 的思維導(dǎo)圖展現(xiàn)了這個(gè)專欄的內(nèi)容。
說到算法中的排序，冒泡排序是最簡(jiǎn)單的一種排序算法了，甚至不學(xué)數(shù)據(jù)結(jié)構(gòu)與算法的同學(xué)都會(huì)使用它。但是你有沒有想過可以怎么優(yōu)化？
什么是冒泡排序：就像水慢慢燒開，氣泡從下往上越來越大那樣，第一次循環(huán)都把n個(gè)元素中最大的元素移動(dòng)至最后位置，第二次從前 n-1 個(gè)位置中找出最大元素放在最后，重復(fù)執(zhí)行，直到最后結(jié)果全部有序。
最基本的算法實(shí)現(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ù)28bubble_sort end: 1 2 3 4 5 6 7 8通過排序的過程可以發(fā)現(xiàn)，在第 4 次冒泡時(shí)，數(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ù)22bubble_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)無序和有序的邊界，然后下次冒泡僅對(duì)無序部分進(jìn)行比較和冒泡，可大大減少比較次數(shù)（循環(huán)次數(shù)），從而加快速度。
問題是，怎么發(fā)現(xiàn)這個(gè)邊界呢？
第一次冒泡的過程中，第一個(gè)元素 4 被移動(dòng)到下標(biāo)為【3】的位置（python 列表索引從 0 開始），位置 【3】就是有序部分的開始位置。
第二次冒泡的過程中，第一個(gè)元素 3 被移動(dòng)到下標(biāo)為【2】的位置（python 列表索引從 0 開始），位置 【2】就是有序部分的開始位置。
...
可以推斷出，一次冒泡的過程中，最后一個(gè)被交換的元素下標(biāo)即為無序和有序的邊界，因而下次冒泡，僅對(duì) 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)的過程中，記錄最后一個(gè)交換元素的公交車，它便是有序和無序狀態(tài)的邊界 下一次僅循環(huán)到邊界即可，從而減少循環(huán)次數(shù)，達(dá)到優(yōu)化。 """ compare_count=0 length = len(collection) last_change_index = 0 #最后一個(gè)交換的位置 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 # 最后一個(gè)交換的位置就是邊界 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ù)10bubble_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)格來說平均時(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ù)雜，這里有一種思路，通過有序度和逆序度這兩個(gè)概念來分析。有序度就是有順序的元素的個(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è)公式
逆序度 = 滿有序度 - 有序度排序的過程就是增加有序度，減少逆序度，最后達(dá)到滿有序度，說明排序完成。逆序度也主濁元素的交換次數(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ù)要多，因而平均情況下，無論算法怎么優(yōu)化，時(shí)間復(fù)雜度不會(huì)低于 n*(n-1)/4，也就是 O(n^2)。
2、內(nèi)存消耗
算法的內(nèi)存消耗可以通過空間復(fù)雜度來衡量，冒泡排序僅需要一個(gè)變量
tmp 來儲(chǔ)存交換的數(shù)據(jù)，因此空間復(fù)雜度為 O(1)，空間復(fù)雜度為 O(1) 的排序算法，也叫 原地排序算法
3、排序算法的穩(wěn)定性
針對(duì)排序算法，有一個(gè)重要的衡量指標(biāo)，就是穩(wěn)定性，這個(gè)概念是說，如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變。假如有序列 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í)間排序，理解起來不難，有沒有想過，實(shí)現(xiàn)起來很復(fù)雜。
但是借助穩(wěn)定的排序算法，就很簡(jiǎn)單了，先按訂單時(shí)間排一次序，再按金額排一次序就可以了。
小結(jié)
對(duì)排序算法的分析無外乎時(shí)間復(fù)雜度（最好，最壞，平均），空間復(fù)雜度，穩(wěn)定性這些方面，只要理解其思路，弄明白其適用場(chǎng)景，不需要死記。優(yōu)化思路可以通過觀察分析得出，還有一點(diǎn)，冒泡排序雖然使用了數(shù)組存儲(chǔ)數(shù)據(jù)但是并沒有使用數(shù)組隨機(jī)訪問的特性，因此改用鏈表這種存儲(chǔ)結(jié)構(gòu)，使用冒泡排序仍然是可以實(shí)現(xiàn)的，你可以嘗試下。
關(guān)注個(gè)人微信公眾號(hào) somenzz 與你一起學(xué)習(xí)。
