視覺化展示
已排序區域
比較 / 交換中
300ms
演算法偽代碼
function bubbleSort(arr):
1 n = arr.length
2 for i = 0 to n-2: // 共 n-1 輪
3 swapped = false
4 for j = 0 to n-2-i: // 已就位的不再比較
5 if arr[j] > arr[j+1]:
6 swap(arr[j], arr[j+1])
7 swapped = true
8 if not swapped: break // 提前結束最佳化
操作原理
氣泡排序法是一種簡單直觀的排序演算法。它會重複地走訪過要排序的數列，一次比較兩個相鄰的元素，如果它們的順序錯誤就把它們交換過來。
走訪數列的工作會重複地進行，直到沒有再需要交換，這意味著該數列已經排序完成。這個演算法的名字由來是因為越大的元素會經由交換，慢慢「浮」到數列的尾端（或越小的元素浮到頂端）。
操作過程
- 比較相鄰元素： 比較陣列中第 1 個和第 2 個元素。如果第 1 個元素大於第 2 個元素，則交換它們。
- 向後移動： 接著比較第 2 個和第 3 個元素，依此類推，直到比較到最後一對相鄰元素。這一步完成後，最大的元素將會被移動到陣列的最後一個位置。
- 重複步驟： 忽略已經排好序的最後一個元素，對剩下的元素重複步驟 1 和 2。
- 完成排序： 每進行一輪，需要比較的元素就少一個，直到所有元素都排序完畢。
複雜度分析
- 時間複雜度 (最佳情況):
O(n)
當陣列已經是排序好的狀態時，氣泡排序只需進行一次走訪，發現沒有元素需要交換即可提早結束。 - 時間複雜度 (平均/最壞情況):
O(n2)
當陣列是反序時，需要進行完整的 n 輪比較，每輪進行 n-i 次交換，因此效率較低。 - 空間複雜度 (Space Complexity):
O(1)
氣泡排序是一種「原地排序 (In-place Sort)」，只需要一個額外的空間來暫存變數以進行交換，不需要額外的陣列配置。