演算法日記 - Bubble Sort
作者 WaitZ
Sorting AlgorithmsbeginnerBubble SortO(n^2)O(1)algorithmsbubble-sortbeginner
今日主題 (Today's Topic)
主題: Bubble Sort
難度: beginner
分類: Sorting Algorithms
時間複雜度: O(n^2)
空間複雜度: O(1)
概念學習 (Concept Learning)
核心概念
**泡沫排序（Bubble Sort）**是最簡單的排序演算法之一。它透過重複遍歷陣列，比較相鄰元素並在順序錯誤時交換它們。這個演算法的名稱來自於較小的元素會像「泡泡」一樣浮到陣列的頂端（開頭），而較大的元素則「沉降」到底部（末尾）。
演算法會持續遍歷陣列，直到不再需要交換為止，這表示陣列已經排序完成。每次完整遍歷都能保證最大的未排序元素移動到末尾的正確位置。
關鍵重點
- 基於比較: 泡沫排序比較相鄰的元素對
- 穩定性: 相等的元素在排序後仍保持其相對順序
- 原地排序: 僅需要 O(1) 的額外記憶體空間
- 簡單但效率低: 容易理解和實作，但在大型資料集上效能不佳
- 適應性: 可以優化以偵測陣列是否已經排序完成
演算法步驟
- 從開頭開始: 從陣列的第一個元素開始
- 比較相鄰對: 比較每對相鄰元素（arr[i] 和 arr[i+1]）
- 必要時交換: 如果元素順序錯誤（arr[i] > arr[i+1]），則交換它們
- 繼續到末尾: 移到下一對並重複，直到到達陣列末尾
- 重複遍歷: 每次完整遍歷後，最大的元素就在正確位置上
- 縮小範圍: 在後續的每次遍歷中，忽略最後已排序的元素
- 檢查完成: 如果某次遍歷中沒有發生交換，陣列已排序，可以停止
程式實作 (Implementation)
JavaScript 實作
function bubbleSort(arr) {
const n = arr.length;
// 外層迴圈：遍歷次數
for (let i = 0; i < n - 1; i++) {
// 內層迴圈：比較相鄰元素
for (let j = 0; j < n - i - 1; j++) {
// 如果元素順序錯誤則交換
if (arr[j] > arr[j + 1]) {
// 使用解構賦值交換
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
// 使用範例
const array = [64, 34, 25, 12, 22, 11, 90];
console.log("原始陣列:", array);
console.log("排序後:", bubbleSort([...array]));
// 輸出: 排序後: [11, 12, 22, 25, 34, 64, 90]
優化版本（提早結束）
function bubbleSortOptimized(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
// 如果沒有發生交換，陣列已經排序完成
if (!swapped) break;
}
return arr;
}
Kotlin 實作
fun bubbleSort(arr: IntArray): IntArray {
val n = arr.size
for (i in 0 until n - 1) {
var swapped = false
for (j in 0 until n - i - 1) {
if (arr[j] > arr[j + 1]) {
// 交換元素
val temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
swapped = true
}
}
// 如果已經排序完成則提早結束
if (!swapped) break
}
return arr
}
// 使用範例
fun main() {
val array = intArrayOf(64, 34, 25, 12, 22, 11, 90)
println("原始陣列: ${array.contentToString()}")
bubbleSort(array)
println("排序後: ${array.contentToString()}")
}
說明
- 解法核心概念: 重複比較和交換相鄰元素，直到整個陣列排序完成
- 時間複雜度:
- 最佳情況: O(n) - 當陣列已經排序完成時（有優化）
- 平均情況: O(n²) - 需要多次遍歷陣列
- 最壞情況: O(n²) - 當陣列是反向排序時
- 空間複雜度: O(1) - 只使用常數量的額外空間來存放臨時變數
- 邊界條件與常見錯誤:
- 空陣列或單一元素: 已經排序完成，直接返回
- 所有元素相同: 不需要交換，透過優化可提早結束
- 忘記縮小內層迴圈範圍（n - i - 1）會浪費對已排序元素的比較
- 未實作優化旗標可能導致不必要的迭代
練習題目 (Practice Problems)
題目清單
LeetCode 912 - Sort an Array
- 難度: Medium
- 使用泡沫排序來排序整數陣列
- 注意: 對這個問題不是最佳解，但適合練習
基本實作
- 排序陣列 [5, 2, 8, 1, 9] 使用泡沫排序
- 計算進行了多少次交換
自訂比較器排序
- 使用泡沫排序按長度排序字串陣列
- 範例: ["apple", "pie", "banana", "cat"] → ["pie", "cat", "apple", "banana"]
優化挑戰
- 實作並測試優化版本
- 比較在已排序陣列與反向排序陣列上的迭代次數
泡沫排序視覺化
- 在每次遍歷後印出陣列狀態
- 觀察元素如何「冒泡」到正確位置
解題筆記
重點:
- 始終檢查陣列邊界以避免索引超出範圍錯誤
- 使用
swapped旗標的優化可以顯著提升接近排序完成的陣列的效能 - 記住每次遍歷至少會將一個元素移動到最終位置
陷阱:
- 忘記縮小內層迴圈範圍（使用
n - i - 1） - 未處理空陣列或單一元素陣列等邊界情況
- 嘗試在大型資料集上使用泡沫排序（應改用快速排序或合併排序）
最佳做法:
- 總是實作帶有提早結束的優化版本
- 泡沫排序僅用於小型資料集（< 100 個元素）或教學目的
- 考慮穩定性需求：泡沫排序會保持相等元素的相對順序
重要細節 (Important Details)
需要注意的邊界條件
- 空陣列
[]: 直接返回 - 單一元素
[5]: 已經排序完成 - 已排序
[1, 2, 3, 4]: 優化版本在第一次遍歷後就結束 - 反向排序
[4, 3, 2, 1]: 最壞情況，需要最多次交換 - 全部重複
[5, 5, 5, 5]: 不需要交換，提早結束
適用場景與限制
適合使用的時機:
- 教學目的（學習排序演算法）
- 非常小的資料集（< 10-20 個元素）
- 接近排序完成的陣列（有優化時）
- 簡單性比效率更重要時
- 需要穩定排序且資料集很小時
限制:
- 效能不佳: O(n²) 時間複雜度對大型資料集太慢
- 不實用: 生產環境中有更好的演算法（合併排序、快速排序、堆積排序）
- 比較次數多: 即使是優化版本也需要許多比較
延伸應用或變形題
雙向泡沫排序（雞尾酒排序）
- 交替進行前向和後向遍歷
- 在某些情況下稍微更有效率
帶旗標的泡沫排序
- 追蹤是否發生交換以啟用提早結束
- 將最佳情況時間複雜度改善為 O(n)
計算交換次數
- 對於關於最小操作的面試問題很有用
- 可以幫助分析陣列的「已排序程度」
排序不同資料類型
- 為物件、字串、自訂類型調整比較器
- 練習使用比較函式
今日反思 (Daily Reflection)
重要收穫: 泡沫排序是一個基礎演算法，教導比較排序的基本概念。雖然對大型資料集效率不高，但它是演算法分析、迴圈不變式和優化技術的絕佳入門。理解泡沫排序有助於欣賞更複雜的排序演算法。
相關演算法:
- 選擇排序: 類似的 O(n²) 複雜度，但使用不同方法（每次遍歷找最小值）
- 插入排序: 同樣是 O(n²) 但對小型/接近排序的陣列在實務上更有效率
- 雞尾酒排序: 泡沫排序的雙向變體
- 合併排序: 高效的 O(n log n) 分治排序
- 快速排序: 流行的平均情況 O(n log n) 排序演算法
- 堆積排序: 使用堆積資料結構的 O(n log n) 排序