1?? 冒泡排序（Bubble Sort）

基本思想

• 重復地比較相鄰的兩個元素，如果順序錯誤就交換它們。
• 一趟冒泡結束后，最大（或最小）的元素會“浮”到末尾。
• 下一趟時可以少比較一次，因為最后的元素已經排好。

過程示例（升序）

假設數組：[5, 3, 8, 4, 2]

第一趟比較：

• (5, 3) → 交換 → [3, 5, 8, 4, 2]
• (5, 8) → 不換 → [3, 5, 8, 4, 2]
• (8, 4) → 交換 → [3, 5, 4, 8, 2]
• (8, 2) → 交換 → [3, 5, 4, 2, 8] ? 最大的 8 已到末尾

第二趟比較（不用管最后的 8）：

• (3, 5) → 不換
• (5, 4) → 交換 → [3, 4, 5, 2, 8]
• (5, 2) → 交換 → [3, 4, 2, 5, 8] ? 次大值 5 已到倒數第二位

… 直到全部有序。

時間復雜度

• 最壞情況：O(n2)（逆序）
• 最好情況：O(n)（已排序，可加優化）
• 空間復雜度：O(1)

Python 代碼

def bubble_sort(arr):n = len(arr)for i in range(n):swapped = False  # 優化：如果一趟沒交換，說明已排序for j in range(0, n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]swapped = Trueif not swapped:breakreturn arr# 示例
data = [5, 3, 8, 4, 2]
print(bubble_sort(data))

---

2?? 選擇排序（Selection Sort）

基本思想

• 每一趟從未排序部分選擇最小（或最大）元素，放到已排序部分的末尾。
• 每趟交換次數固定為 1 次，但比較次數較多。

工作過程示例（升序）

初始數組：[5, 3, 8, 4, 2]

第一趟：

• 在 [5, 3, 8, 4, 2] 中找到最小值 2
• 交換 2 和第一個元素 → [2, 3, 8, 4, 5]

第二趟：

• 在 [3, 8, 4, 5] 中最小值 3（不動） → [2, 3, 8, 4, 5]

第三趟：

• 在 [8, 4, 5] 中最小值 4
• 交換 → [2, 3, 4, 8, 5]

第四趟：

• 在 [8, 5] 中最小值 5
• 交換 → [2, 3, 4, 5, 8]

時間復雜度

• 最壞情況：O(n2)
• 最好情況：O(n2)（比較次數固定）
• 空間復雜度：O(1)

Python 代碼

def selection_sort(arr):n = len(arr)for i in range(n):min_idx = ifor j in range(i + 1, n):if arr[j] < arr[min_idx]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i]return arr# 示例
data = [5, 3, 8, 4, 2]
print(selection_sort(data))

---

3?? 插入排序（Insertion Sort）

基本思想

• 將數組分為已排序區和未排序區。
• 每次從未排序區取出一個元素，插入到已排序區的合適位置。

工作過程示例（升序）

初始數組：[5, 3, 8, 4, 2]

第一步（i=1）：

• 已排序區 [5]
• 取 3，插入到 5 前面 → [3, 5, 8, 4, 2]

第二步（i=2）：

• 已排序區 [3, 5]
• 取 8，放到末尾 → [3, 5, 8, 4, 2]

第三步（i=3）：

• 已排序區 [3, 5, 8]
• 取 4，插到 5 前面 → [3, 4, 5, 8, 2]

第四步（i=4）：

• 已排序區 [3, 4, 5, 8]
• 取 2，插到最前面 → [2, 3, 4, 5, 8]

時間復雜度

• 最壞情況：O(n2)
• 最好情況：O(n)（已排序）
• 空間復雜度：O(1)
• 對小規模數據或基本有序數據非常快

Python 代碼

def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]  # 當前要插入的元素j = i - 1while j >= 0 and arr[j] > key:arr[j + 1] = arr[j]  # 后移j -= 1arr[j + 1] = keyreturn arr# 示例
data = [5, 3, 8, 4, 2]
print(insertion_sort(data))

---

🔍 對比總結

算法	最好時間	最壞時間	穩定性	空間復雜度	適用場景
冒泡排序	O(n)	O(n2)	穩定	O(1)	數據量小，且大致有序
選擇排序	O(n2)	O(n2)	不穩定	O(1)	數據量小，對交換次數敏感
插入排序	O(n)	O(n2)	穩定	O(1)	數據基本有序，小規模排序