演算法入門：排序與搜尋
演算法是解決問題的步驟與方法。排序與搜尋是最基礎也最實用的演算法類別。
🔥 Vibe Prompt
「用 Python 實作並比較 5 種排序演算法（Bubble、Selection、Insertion、Merge、Quick）與 2 種搜尋演算法（Linear、Binary）。每種演算法附註解說明時間複雜度，並用隨機產生的 10000 筆資料測試實際執行時間。」
排序演算法
1. 氣泡排序 (Bubble Sort)
相鄰元素兩兩比較，大的往右交換。就像氣泡一樣，較大的元素慢慢「浮」到陣列末端。
| 指標 | 值 | |------|-----| | 時間複雜度 | O(n²) — 最差/平均；O(n) — 最好（已排序） | | 空間複雜度 | O(1) — 原地排序 | | 穩定性 | ✅ 穩定 |
def bubble_sort(arr):
"""氣泡排序：O(n²)"""
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 = True
if not swapped: # 已排序，提前結束
break
return arr
# 測試
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
2. 選擇排序 (Selection Sort)
每次從未排序部分選出最小值，放到已排序部分的末尾。
| 指標 | 值 | |------|-----| | 時間複雜度 | O(n²) — 全部情況 | | 空間複雜度 | O(1) | | 穩定性 | ❌ 不穩定 |
def selection_sort(arr):
"""選擇排序：O(n²)"""
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_sort([64, 34, 25, 12, 22, 11, 90]))
3. 插入排序 (Insertion Sort)
將每個元素插入到已排序部分的適當位置——就像你整理手上的撲克牌。
| 指標 | 值 | |------|-----| | 時間複雜度 | O(n²) — 最差/平均；O(n) — 最好 | | 空間複雜度 | O(1) | | 穩定性 | ✅ 穩定 |
def insertion_sort(arr):
"""插入排序：O(n²)"""
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
print(insertion_sort([64, 34, 25, 12, 22, 11, 90]))
4. 合併排序 (Merge Sort)
分治法經典範例。將陣列切成兩半，分別排序，再合併。
| 指標 | 值 | |------|-----| | 時間複雜度 | O(n log n) — 全部情況 | | 空間複雜度 | O(n) — 需要額外空間 | | 穩定性 | ✅ 穩定 |
def merge_sort(arr):
"""合併排序：O(n log n)"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([64, 34, 25, 12, 22, 11, 90]))
5. 快速排序 (Quick Sort)
選一個 pivot（基準值），將小於 pivot 的放左邊，大於的放右邊，再遞迴排序。
| 指標 | 值 | |------|-----| | 時間複雜度 | O(n log n) — 平均；O(n²) — 最差（已排序且 pivot 選得不好） | | 空間複雜度 | O(log n) — 遞迴堆疊 | | 穩定性 | ❌ 不穩定 |
def quick_sort(arr):
"""快速排序：O(n log n) 平均"""
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([64, 34, 25, 12, 22, 11, 90]))
排序演算法比較
import time
import random
# 產生測試資料
data = [random.randint(1, 10000) for _ in range(5000)]
algorithms = [
("Bubble Sort", bubble_sort),
("Selection Sort", selection_sort),
("Insertion Sort", insertion_sort),
("Merge Sort", merge_sort),
("Quick Sort", quick_sort),
]
for name, algo in algorithms:
test_data = data.copy()
start = time.time()
algo(test_data)
elapsed = time.time() - start
print(f"{name}: {elapsed:.4f} 秒")
| 演算法 | 5000 筆（約） | 10000 筆（約） | 50000 筆（約） | |--------|-------------|--------------|--------------| | 氣泡排序 | 0.25 秒 | 1.0 秒 | 25 秒 | | 選擇排序 | 0.12 秒 | 0.5 秒 | 12 秒 | | 插入排序 | 0.10 秒 | 0.4 秒 | 10 秒 | | 合併排序 | 0.008 秒 | 0.02 秒 | 0.1 秒 | | 快速排序 | 0.004 秒 | 0.01 秒 | 0.05 秒 |
搜尋演算法
1. 線性搜尋 (Linear Search)
從頭到尾逐一比對。
| 指標 | 值 | |------|-----| | 時間複雜度 | O(n) | | 空間複雜度 | O(1) | | 資料要求 | 無需排序 |
def linear_search(arr, target):
"""線性搜尋：O(n)"""
for i, val in enumerate(arr):
if val == target:
return i
return -1
2. 二元搜尋 (Binary Search)
每次將搜尋範圍縮小一半。
| 指標 | 值 | |------|-----| | 時間複雜度 | O(log n) | | 空間複雜度 | O(1) — 迭代版 | | 資料要求 | 必須已排序 |
def binary_search(arr, target):
"""二元搜尋：O(log n)，arr 必須已排序"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 測試
sorted_arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(f"搜尋 7: index {binary_search(sorted_arr, 7)}")
print(f"搜尋 6: {binary_search(sorted_arr, 6)} (找不到)")
總結
| 演算法 | 時間複雜度 | 空間 | 穩定 | 適合場景 | |--------|-----------|------|------|---------| | 氣泡排序 | O(n²) | O(1) | ✅ | 教學用途，小資料 | | 選擇排序 | O(n²) | O(1) | ❌ | 小資料 | | 插入排序 | O(n²) | O(1) | ✅ | 幾乎已排序的資料 | | 合併排序 | O(n log n) | O(n) | ✅ | 大型資料，需要穩定 | | 快速排序 | O(n log n) | O(log n) | ❌ | 大型資料，最快平均 | | 線性搜尋 | O(n) | O(1) | — | 無需排序的小資料 | | 二元搜尋 | O(log n) | O(1) | — | 已排序的大型資料 |
實戰練習
💡 Vibe Coding 練習：請 AI 建立一個「排序演算法視覺化工具」：
- 用 HTML Canvas 或 SVG 顯示條狀圖
- 即時展示每種排序的執行過程（條狀圖的交換與移動）
- 可選擇不同排序演算法
- 顯示比較次數與交換次數
- 支援自訂資料或隨機產生