冒泡排序

今天我們來詳解冒泡排序算法，從原理到實現，然后再到算法分析三個部分完成對這個算法的剖析。

1. 冒泡排序算法原理

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

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

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

我們來用冒泡排序算法來解決一下這個問題，在開始動手寫代碼之前先來看下冒泡排序的原理：

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

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

1. 冒泡排序算法分析

以此類推，對于 n 個元素的排序，在第 n-1 輪迭代后，我們的排序工作就結束了，此時的數組正是從小到大依次排列好。下面我們用一幅圖對冒泡排序算法進行說明，如下：

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

在經過 n-1 輪迭代后，最后得到的結果就是我們想要的從小到大的排序順序：

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

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

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

3. 冒泡排序算法 Python 實現

基礎的冒泡排序實現代碼如下：

# 代碼位置：sort_algorithms.py
def bubble_sort(nums):
    """
    冒泡排序算法
    輸入：nums，無序列表
    執(zhí)行完后該nums值會變成有序列表
    """
    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]

我們簡單寫個代碼測試下這個函數：

# 冒泡排序算法
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í)行后結果如下：

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

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

4. 冒泡排序算法復雜度分析

對于算法的復雜度分析，會考慮以下幾種情況：

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

def bubble_sort(nums):
    # 在這里添加一個交換的標記
    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]
                # 出現了元素交換則標記
                swapped = True
        # 如果一次循環(huán)都沒有交換過數據，說明數據本身是有序的，則直接返回不用繼續(xù)冒泡
        if not swapped:
            break

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

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

5. 小結

本小節(jié)種我們詳細介紹了排序算法種的最基本的算法：冒泡排序算法。接下來，我們給出了 Python 實現，并簡單對代碼進行了說明。最后分析了冒泡排序算法的時間和空間復雜度以及簡單的優(yōu)化點。

Tips：文中動圖制作參考：https://visualgo.net/zh/sorting。