Python實現冒泡排序

一、冒泡排序簡介

冒泡排序（Bubble Sort）是一種簡單的排序演算法，它重複地遍歷要排序的列表，每次比較相鄰的兩項，如果它們的順序錯誤就交換它們，直到沒有要交換的項為止。冒泡排序演算法的時間複雜度為 O(n²)。

二、冒泡排序實現思路

冒泡排序演算法的實現思路可以用以下的步驟來描述：

1、比較相鄰的元素，如果第一個比第二個大，就交換它們的位置；

2、對每一對相鄰的元素都進行步驟1的工作，從開始第一對到結尾最後一對，這樣在最後的元素應該會是最大的數；

3、針對所有的元素重複以上的步驟，除了最後一個；

4、持續每次對越來越少的元素重複上述步驟，直到沒有任何一對數字需要比較為止。

三、Python實現代碼

def bubble_sort(arr):
    n = len(arr)
    # 遍歷所有數組元素
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n-i-1):
            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]

四、代碼解析

1、定義bubble_sort函數，傳入一個參數arr，表示待排序的數組；

2、定義變數n，表示數組的長度；

3、通過兩個for循環遍曆數組，外層循環遍曆數組的所有元素，內層循環則遍曆數組中前n-i-1個元素，因為最後的n-i-1個元素已經排好序了；

4、當發現arr[j]比arr[j+1]大時，交換這兩個元素的位置；

5、最終，得到一個有序的數組。

五、演算法優化

冒泡排序演算法雖然簡單，但是時間複雜度比較高，因此需要對演算法進行優化。

1、設置標誌位

如果在某次遍歷中，沒有任何元素被交換，說明數組已經有序，可以停止遍歷。

def bubble_sort(arr):
    n = len(arr)
    # 遍歷所有數組元素
    for i in range(n):
        # Last i elements are already in place
        flag = True
        for j in range(0, n-i-1):
            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = False
        # 如果遍歷中沒有任何元素被交換，說明數組已經有序，可以停止遍歷。
        if flag:
            break

2、優化搜索範圍

對於傳統的冒泡排序，在每一輪遍歷時都要比較整個數組，這樣即使數組已經有序，仍然要進行n次遍歷。而如果每次遍歷時記錄最後一次交換的位置，那麼後面的元素就已經有序了，可以減少比較次數。

def bubble_sort(arr):
    n = len(arr)
    # 遍歷所有數組元素
    for i in range(n):
        # Last i elements are already in place
        flag = True
        # 記錄最後一次元素交換的位置
        k = n - 1
        for j in range(0, k):
            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                # 更新最後一次元素交換的位置
                k = j
                flag = False
        # 如果遍歷中沒有任何元素被交換，說明數組已經有序，可以停止遍歷。
        if flag:
            break

六、總結

冒泡排序是一種簡單有效的排序演算法，但是時間複雜度比較高，需要使用優化手段來提高效率。Python實現冒泡排序的代碼也比較簡單，可以方便地進行調試和優化。