冒泡排序

今天我們來(lái)詳解冒泡排序算法，從原理到實(shí)現(xiàn)，然后再到算法分析三個(gè)部分完成對(duì)這個(gè)算法的剖析。

1. 冒泡排序算法原理

所有的算法介紹都始于排序算法，所有的排序算法都會(huì)始于冒泡排序。排序問(wèn)題是一個(gè)非常古老的問(wèn)題，從算法出生就被研究到現(xiàn)在。當(dāng)然主要是排序的規(guī)模再不斷擴(kuò)大，從一開(kāi)始的幾百到幾千個(gè)數(shù)排序，到現(xiàn)在對(duì)幾百億個(gè)數(shù)甚至幾千億數(shù)進(jìn)行排序，這里面用到的技術(shù)和算法遠(yuǎn)遠(yuǎn)超過(guò)我們的想象。當(dāng)然，千里之行，始于足下，今天我們以這個(gè)冒泡算法為例，正式進(jìn)入算法的世界。

排序問(wèn)題：給定一列數(shù)據(jù)， 對(duì)它們進(jìn)行排序，并按照從小到大 (或者從大到小) 的順序輸出；

輸入: [8, 7, 12, 3, 2, 11, 10, 6]
輸出: [2, 3, 6, 7, 8, 10, 11, 12]

我們來(lái)用冒泡排序算法來(lái)解決一下這個(gè)問(wèn)題，在開(kāi)始動(dòng)手寫(xiě)代碼之前先來(lái)看下冒泡排序的原理：

冒泡排序的思想比較簡(jiǎn)單，對(duì)于需要從小到大排列的數(shù)組，我們采用這樣的方式：從第一個(gè)位置開(kāi)始，兩兩比較相鄰元素的大小 （第一個(gè)位置和第二個(gè)位置），如果前者比后者大，那么交換兩者的位置；接下來(lái)比較下一個(gè)相鄰位置（第二個(gè)位置和第三個(gè)位置）元素的大小，然后將大的值放到后面，這樣一直比較到最后一個(gè)位置，此時(shí)數(shù)組中的最大值就會(huì)落到最后一個(gè)位置上，這時(shí)第一輪比較就結(jié)束了。

接著開(kāi)始第二輪比較，同樣是從第一個(gè)位置開(kāi)始，兩兩相鄰比較，將較大者交換到后面位置，但這次我們比較到倒數(shù)第二個(gè)位置即停止。此時(shí)倒數(shù)第二個(gè)位置的元素就是除最后一個(gè)元素外的最大值。

1. 冒泡排序算法分析

以此類(lèi)推，對(duì)于 n 個(gè)元素的排序，在第 n-1 輪迭代后，我們的排序工作就結(jié)束了，此時(shí)的數(shù)組正是從小到大依次排列好。下面我們用一幅圖對(duì)冒泡排序算法進(jìn)行說(shuō)明，如下：

在第一輪迭代完成后，全局的最大值便落到了最后位置。接下來(lái)的第二輪迭代中，我們就不會(huì)再比較這個(gè)位置，而是相鄰比較到倒數(shù)第二個(gè)位置結(jié)束；接下來(lái)第三輪迭代是比較到倒數(shù)第三個(gè)位置結(jié)束；以此類(lèi)推，直到最后一輪迭代只剩下一個(gè)元素即可，此時(shí)得到的排列順序正是從小到大的有序排序。下面給出第二輪迭代示意圖，其余迭代過(guò)程依次類(lèi)推：

在經(jīng)過(guò) n-1 輪迭代后，最后得到的結(jié)果就是我們想要的從小到大的排序順序：

2，3，6，7，8，10，11，12

如果你還是不明白冒泡排序的原理的話，可以看下面的動(dòng)態(tài)圖：

冒泡排序的思想就是這樣：通過(guò)一輪相鄰元素的比較，將最大值找到并交換到最后的位置，第二輪找到第二大的值，放到倒數(shù)第二個(gè)位置，直到最后一輪迭代，找到第二小的值，放到第二個(gè)位置上，最小值此時(shí)就在第一個(gè)位置上。接下來(lái)我們就開(kāi)始完成該算法的 Python 編程。

3. 冒泡排序算法 Python 實(shí)現(xiàn)

基礎(chǔ)的冒泡排序?qū)崿F(xiàn)代碼如下：

# 代碼位置：sort_algorithms.py
def bubble_sort(nums):
    """
    冒泡排序算法
    輸入：nums，無(wú)序列表
    執(zhí)行完后該nums值會(huì)變成有序列表
    """
    for i in range(len(nums) - 1):
        for j in range(0, len(nums) - i - 1):
            # 如果當(dāng)前元素比下一個(gè)元素大，則交換兩個(gè)元素，保證左邊的比右邊的元素要小
            if nums[j] > nums[j + 1]:
                # 交換相鄰元素
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

我們簡(jiǎn)單寫(xiě)個(gè)代碼測(cè)試下這個(gè)函數(shù)：

# 冒泡排序算法
from sort_algorithms import bubble_sort

if __name__ == '__main__':
    nums = [8, 7, 12, 3, 2, 11, 10, 6]
    bubble_sort(nums)
    print('排序后的nums:{}'.format(nums))

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

排序后的nums:[2, 3, 6, 7, 8, 10, 11, 12]

這里的實(shí)現(xiàn)非常簡(jiǎn)單，注意兩個(gè) for 循環(huán)的次數(shù)即可，然后便是相鄰數(shù)據(jù)比較，滿足條件即交換數(shù)據(jù)。接下來(lái)我們要分析這種算法的復(fù)雜度。

4. 冒泡排序算法復(fù)雜度分析

對(duì)于算法的復(fù)雜度分析，會(huì)考慮以下幾種情況：

時(shí)間復(fù)雜度：注意，這里的復(fù)雜度其實(shí)是包含 3 種情況，分別是最優(yōu)復(fù)雜度、最壞情況復(fù)雜度和平均復(fù)雜度。由于我們不管怎么樣，進(jìn)行的 for 循環(huán)次數(shù)為：
$(n-1) + (n-2) + ... + 1 = O(n^2)$
所以所有情況的復(fù)雜度都是$O(n^2)$。但是對(duì)于最優(yōu)的情況呢，有沒(méi)有優(yōu)化空間？要想在序列已有序的情況下使復(fù)雜度為 O (n)，其實(shí)只需要增加一個(gè)標(biāo)記量，如果內(nèi)部循環(huán)沒(méi)有發(fā)生任何的交換（swap），則表示序列已經(jīng)有序，此時(shí)可以跳出循環(huán)。這楊我們對(duì)前面的代碼進(jìn)行簡(jiǎn)單的優(yōu)化下：

def bubble_sort(nums):
    # 在這里添加一個(gè)交換的標(biāo)記
    swapped = False
    for i in range(len(nums) - 1):
        for j in range(0, len(nums) - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                # 出現(xiàn)了元素交換則標(biāo)記
                swapped = True
        # 如果一次循環(huán)都沒(méi)有交換過(guò)數(shù)據(jù)，說(shuō)明數(shù)據(jù)本身是有序的，則直接返回不用繼續(xù)冒泡
        if not swapped:
            break

上面簡(jiǎn)單添加了一個(gè)交換的標(biāo)記，如果一輪冒泡中不存在數(shù)據(jù)交換，說(shuō)明數(shù)據(jù)本身有序，那么可以直接退出循環(huán)，不用繼續(xù)冒泡排序。

空間復(fù)雜度：很明顯這里我們沒(méi)有用到額外的空間，冒泡排序的空間復(fù)雜度就是單純的問(wèn)題規(guī)模，也就是 $O(n)$。

5. 小結(jié)

本小節(jié)種我們?cè)敿?xì)介紹了排序算法種的最基本的算法：冒泡排序算法。接下來(lái)，我們給出了 Python 實(shí)現(xiàn)，并簡(jiǎn)單對(duì)代碼進(jìn)行了說(shuō)明。最后分析了冒泡排序算法的時(shí)間和空間復(fù)雜度以及簡(jiǎn)單的優(yōu)化點(diǎn)。

Tips：文中動(dòng)圖制作參考：https://visualgo.net/zh/sorting。