DSA 氣泡排序

氣泡排序

氣泡排序是一種將陣列從最小值排序到最大值的演算法。

執行模擬以檢視氣泡排序演算法如何對一組值進行排序。陣列中的每個值都由一個列表示。

“冒泡”這個詞來源於這種演算法的工作方式，它使最高值“冒”到頂部。

繼續閱讀以完全理解氣泡排序演算法以及如何自行實現它。

手動演練

在我們用程式語言實現氣泡排序演算法之前，讓我們先手動遍歷一個短陣列一次，只是為了瞭解其思想。

步驟 1：我們從一個未排序的陣列開始。

步驟 2： 我們看前兩個值。最小值在前嗎？是的，所以我們不需要交換它們。

步驟 3： 向前一步，看看值 12 和 9。最小值在前嗎？不是。

步驟 4： 所以我們需要交換它們，使 9 排在前面。

步驟 5： 向前一步，看看 12 和 11。

步驟 6： 我們必須交換，使 11 在 12 之前。

步驟 7： 看看 12 和 3，我們需要交換它們嗎？是的。

步驟 8： 交換 12 和 3，使 3 排在前面。

執行下面的模擬以檢視上述 8 個步驟的動畫

手動執行：發生了什麼？

我們必須理解第一次遍歷中發生的事情，才能完全理解該演算法，從而可以用程式語言實現它。

您能看出最高值 12 發生了什麼嗎？它已經冒到陣列的末尾，也就是它所屬的位置。但陣列的其餘部分仍未排序。

因此，氣泡排序演算法必須一次又一次地遍歷陣列，每次下一個最高值都會冒到其正確位置。排序一直持續到最小值 3 留在陣列的開頭。這意味著我們需要遍歷陣列 4 次，才能對 5 個值的陣列進行排序。

每次演算法遍歷陣列時，陣列中剩餘的未排序部分都會變短。

這就是一次完整的手動遍歷的樣子

我們現在將利用所學知識，用程式語言實現氣泡排序演算法。

氣泡排序實現

要在程式語言中實現氣泡排序演算法，我們需要

1. 一個包含待排序值的陣列。
2. 一個內部迴圈，它遍歷陣列並在第一個值高於下一個值時交換值。此迴圈每次執行時必須少遍歷一個值。
3. 一個外部迴圈，它控制內部迴圈必須執行的次數。對於一個包含 n 個值的陣列，此外部迴圈必須執行 n-1 次。

生成的程式碼如下：

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(n-1):
    for j in range(n-i-1):
        if my_array[j] > my_array[j+1]:
            my_array[j], my_array[j+1] = my_array[j+1], my_array[j]

print("Sorted array:", my_array)

氣泡排序改進

氣泡排序演算法可以再改進一點。

想象一下陣列幾乎已經排序，最低的數字在開頭，例如這樣：

my_array = [7, 3, 9, 12, 11]

在這種情況下，陣列在第一次執行後就會被排序，但氣泡排序演算法會繼續執行，而不會交換元素，這是不必要的。

如果演算法一次遍歷陣列而沒有交換任何值，那麼陣列必須已完成排序，我們可以停止演算法，像這樣：

my_array = [7, 3, 9, 12, 11]

n = len(my_array)
for i in range(n-1):
    swapped = False
    for j in range(n-i-1):
        if my_array[j] > my_array[j+1]:
            my_array[j], my_array[j+1] = my_array[j+1], my_array[j]
            swapped = True
    if not swapped:
        break

print("Sorted array:", my_array)

氣泡排序時間複雜度

有關時間複雜度的一般性解釋，請訪問此頁面。

有關氣泡排序時間複雜度的更深入和詳細解釋，請訪問 此頁面。

氣泡排序演算法遍歷陣列中的每個值，將其與相鄰值進行比較。因此，對於一個包含 \(n\) 個值的陣列，在一個迴圈中必須有 \(n\) 次這樣的比較。

在一個迴圈之後，陣列會再次迴圈遍歷 \(n\) 次。

這意味著總共進行了 \(n \cdot n\) 次比較，因此氣泡排序的時間複雜度為

\[ \underline{\underline{O(n^2)}} \]

描述氣泡排序時間複雜度的圖表如下所示

如您所見，當陣列大小增加時，執行時間會非常快地增加。

幸運的是，還有比這更快的排序演算法，例如我們稍後會看到的快速排序。

您可以在下方模擬氣泡排序，其中紅色虛線是理論時間複雜度 \(O(n^2)\)。您可以選擇值的數量 \(n\)，並執行實際的氣泡排序實現，其中操作被計數，並且計數在下面的圖中標記為藍色十字。理論與實踐相比如何？

[,,,,]