冒泡排序是是一種比較基礎(chǔ)簡單的算法。

它的原理是通過對比前后的元素大小，將較大的數(shù)換到后面的方式來實現(xiàn)排序 。

排序過程

舉個例子：

假如現(xiàn)在有一個無序數(shù)組disorder_arr = [4,2,19,10,-1]。

第一步：

取第0個元素4，和第1個元素2

對比，發(fā)現(xiàn)4比2大。

第二步：

交換4與2的索引。

即第0個元素為2,第1個元素為4，disorder_arr =[2,4,19,10,-1]

第三步：

取第1個元素4，和第2個元素19

對比，發(fā)現(xiàn)4小于19。

第四步：

保持索引不變。

重復(fù)上面步驟

遍歷n-1次數(shù)組，會將數(shù)組中最大的數(shù)換到數(shù)組最后面的位置。

然后重頭開始遍歷，遍歷n-2次數(shù)組。

為什么是n-2次呢？

因為最大的數(shù)已經(jīng)在最后了，不需要再判斷多一次了，

所以是n-2次。

這次會將第二大的數(shù)放置在倒數(shù)第二個索引上。

寫一段代碼

代碼依然是使用Python3實現(xiàn)的

普通實現(xiàn)

通常所見到的冒泡排序都是這種實現(xiàn)，用了兩層循環(huán)。

時間復(fù)雜度為O(n^2)

def bubble(self, disorder_arr: list):
    for i in range(len(disorder_arr)): # 遍歷n次數(shù)組
        for j in range(len(disorder_arr) - i - 1): # 遍歷n-i-1個數(shù)組的元素

            if disorder_arr[j] > disorder_arr[j + 1]: # 對比當(dāng)前數(shù)與下一個數(shù)
                temp = disorder_arr[j]
                disorder_arr[j] = disorder_arr[j + 1]
                disorder_arr[j + 1] = temp
                
    return disorder_arr

一個for的實現(xiàn)

還有一個比較特別的實現(xiàn)，只用了一層循環(huán)

def bubble2(self, disorder_arr: list):
    team = len(disorder_arr) - 1 

    i = 0
    while i < team: #  遍歷n-1個元素，直到team等于i，即team=0
        if disorder_arr[i] > disorder_arr[i + 1]: # 對比當(dāng)前數(shù)與下一個數(shù)
            temp = disorder_arr[i]
            disorder_arr[i] = disorder_arr[i + 1]
            disorder_arr[i + 1] = temp

        if i == team - 1: # 如果遍歷到了最后一個元素，則重置i的值，并給team減1
            i = -1
            team -= 1

        i += 1
    return disorder_arr
  

乍一看，感覺時間復(fù)雜度是O(n)

但玄機(jī)在于循環(huán)下面的if i == team - 1:這個判斷，

當(dāng)遍歷到數(shù)組末尾的時候，會將i的值重置，

因此這個實現(xiàn)的時間復(fù)雜度依然是O(n^2)

分析

在冒泡排序中，首先需要遍歷n-1次數(shù)組，然后要執(zhí)行n次這種操作。

因此它的時間復(fù)雜度為O(n^2)

那么它是一個穩(wěn)定的算法嗎？

如果進(jìn)行比較的時候，兩個數(shù)相等，那么算法將不會對他們進(jìn)行交換索引，

因此它是穩(wěn)定的。

以上代碼已上傳至[github][https://github.com/alisen39/algorithm/blob/master/algorithms/sorting/bubbleSort.py]

歡迎大家友好交流[握手]