Procedure BubbleSort(A: array of n elements)
for i = 1 to n-1 do:
for j = 0 to n-i-1 do:
if A[j] > A[j+1] then
swap(A[j], A[j+1])
end if
end for
end for
End Procedure
虛擬碼說明：
- 外層迴圈 (i)：從第 1 個元素到第 n-1 個元素。這個迴圈用來確保每次通過列表時，將最大的未排序元素推到列表的末尾。
- 內層迴圈 (j)：從第 0 個元素到第 n-i-1 個元素。每一輪中，該迴圈會逐個比較相鄰的元素，如果前面的元素大於後面的元素，則交換它們的位置。
- 交換 (swap)：當 A[j] > A[j+1] 時，交換它們的位置，這樣較大的元素會逐步向列表末端移動。
計算複雜度分析：
-
時間複雜度：
- 在最壞情況（例如，反序列表）下，每次內層迴圈都需要執行 n-i 次比較和最多一次交換。由於需要進行 (n-1) 次外層迴圈，因此總的時間複雜度為O(n^2)。
- 在最佳情況下（例如，已排序列表），雖然每次比較都不需要進行交換，但仍然必須進行 n-1 次內層迴圈，因此時間複雜度仍為 O(n^2)。
-
空間複雜度：
- 泡沫排序法是一種原地排序演算法，它不需要額外的儲存空間，因此空間複雜度為 O(1)。
泡沫排序法的計算複雜度為 O(n^2)，這使得它在處理大型數據集時效能不佳。然而，由於其實現簡單且直觀，仍然在某些情況下被使用，例如學習排序概念或處理小型數據集。
阿摩線上測驗
登入