引言

大家好！歡迎來到我的排序算法系列第二篇。今天，我們將學習另一種非常基礎且廣為人知的排序算法——冒泡排序 (Bubble Sort)。

冒泡排序的名字非常形象，它模擬了水中氣泡上升的過程：較小（或較大）的元素會像氣泡一樣，通過不斷交換，逐漸“浮”到數組的一端。

---

什么是冒泡排序？

冒泡排序的核心思想是：重復地遍歷待排序的序列，每次遍歷比較相鄰的兩個元素，如果它們的順序錯誤（例如，在升序排序中，前面的元素大于后面的元素），就交換它們的位置。

這個過程會一直重復，直到在某一次遍歷中沒有發生任何元素交換，這意味著整個序列已經排序完成。

想象一下：

1. 第一輪： 從第一個元素開始，依次比較相鄰的兩個元素。如果順序不對就交換。這一輪結束后，最大的元素會被移動到數組的末尾。
2. 第二輪： 再次從第一個元素開始，比較相鄰元素并交換（如果需要），但這次只需要比較到倒數第二個元素，因為最后一個元素已經是最大的了。這一輪結束后，第二大的元素會被移動到倒數第二的位置。
3. 重復這個過程： 每一輪都將當前未排序部分的最大元素“冒泡”到其最終位置。比較的范圍也逐漸縮小。

---

算法步驟詳解 (以升序為例)

假設我們有數組 [5, 1, 4, 2, 8]

1. 第 1 輪 (比較 n-1 次 = 4次):

   • 比較 5 和 1 -> 1 > 5? 否 -> 5 > 1? 是 -> 交換 -> [1, 5, 4, 2, 8]
   • 比較 5 和 4 -> 5 > 4? 是 -> 交換 -> [1, 4, 5, 2, 8]
   • 比較 5 和 2 -> 5 > 2? 是 -> 交換 -> [1, 4, 2, 5, 8]
   • 比較 5 和 8 -> 5 > 8? 否 -> 不交換 -> [1, 4, 2, 5, 8]
   • 結果： 最大元素 8 已就位。下次只需比較前 4 個。

2. 第 2 輪 (比較 n-2 次 = 3次):

   • 比較 1 和 4 -> 1 > 4? 否 -> 不交換 -> [1, 4, 2, 5, 8]
   • 比較 4 和 2 -> 4 > 2? 是 -> 交換 -> [1, 2, 4, 5, 8]
   • 比較 4 和 5 -> 4 > 5? 否 -> 不交換 -> [1, 2, 4, 5, 8]
   • 結果： 第二大元素 5 已就位。下次只需比較前 3 個。

3. 第 3 輪 (比較 n-3 次 = 2次):

   • 比較 1 和 2 -> 1 > 2? 否 -> 不交換 -> [1, 2, 4, 5, 8]
   • 比較 2 和 4 -> 2 > 4? 否 -> 不交換 -> [1, 2, 4, 5, 8]
   • 結果： 第三大元素 4 已就位。下次只需比較前 2 個。

4. 第 4 輪 (比較 n-4 次 = 1次):

   • 比較 1 和 2 -> 1 > 2? 否 -> 不交換 -> [1, 2, 4, 5, 8]
   • 結果： 第四（小）大元素 2 已就位。數組排序完成。

---

Java 代碼實現

下面提供了兩種冒泡排序的 Java 實現：基礎版和優化版。

1. 基礎冒泡排序 (bubbleSort1)

這是最經典的冒泡排序實現。

import java.util.Arrays;public class BubbleSort { // 類名建議大寫開頭public static void main(String[] args) {int[] arr = {31, 25, 18, 16, 19, 82, 71