Python冒泡排序代碼通俗理解

冒泡排序是一種簡單的算法，它的原理是從數據的序列中一對一對比較相鄰的元素，將較大的數往後移動，較小的數往前移動，一次比較完成後，最大的數就被移動到了序列的尾部。接着，對剩下的數重複這樣的操作，直到整個序列排序完成。

一、算法原理

冒泡排序中，通過兩兩比較相鄰元素的大小，將較大的數往後移動，較小的數往前移動，這個過程就像氣泡冒上水面一樣，因此得名為「冒泡排序」。

冒泡排序的具體實現過程如下：

def bubble_sort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, 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]
    return arr

首先，定義了一個名為bubble_sort的函數，它的參數是一個數組。函數內部首先通過len()函數獲取數組的長度並將其賦值給n。然後利用兩個for循環來執行排序操作。

外部的循環將i從0到n-1遍曆數組，而內部的循環則將j從0到n-i-1來遍曆數組，因為在每趟排序後，序列的最後i項已經有序，不需要再進行比較。在內部循環中，通過比較數組中相鄰的元素，如果當前元素大於它的下一個元素，就交換它們的位置，從而將較大的數往後移動，較小的數往前移動。

二、算法分析

冒泡排序算法的時間複雜度為O(n²)，比較次數為n(n-1)/2，交換次數也達到n(n-1)/2，因此它不適合處理大規模的數據。

在最壞的情況下，即待排序的序列是一個逆序序列時，冒泡排序的時間複雜度為O(n²)。

冒泡排序算法是一種穩定排序算法，它不會改變相同元素之間的順序，即如果兩個元素的大小相同，它們在排序後仍保持原來的位置不變。

三、算法優化

冒泡排序是一種簡單但效率不高的算法，可以通過一些優化方法來提高它的性能。

1、如果在某一趟排序中沒有發生任何數據交換，那麼說明序列已經有序，因此可以跳出循環。這樣可以減少比較和交換次數，提高算法的效率。

def bubble_sort_v2(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n):
        flag = False
        # Last i elements are already in place
        for j in range(0, 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 = True
        if flag == False:
            break
    return arr

2、在內部循環中，可以將最大值和最小值分別往前和往後移動，從而進行雙向排序。這樣可以減少比較和交換次數，提高算法的效率。

def bubble_sort_v3(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n):
        flag = False
        # Sort from both ends
        low, high = i, n-i-1
        for j in range(low, high):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = True
        if not flag:
            break
        for j in range(high, low, -1):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
                flag = True
        if not flag:
            break
    return arr

四、總結

冒泡排序是一種非常簡單但效率不高的算法，它通過比較相鄰的元素來將序列中的較大值往後移動，較小值往前移動，最終實現排序。該算法的時間複雜度為O(n²)，適用於小規模的數據排序。通過優化算法可以提高它的性能，但在面對大規模的數據時，更加高效的排序算法如快速排序、堆排序等更為適合。