建立 2026-11-12 更新 2026-11-12 SL HL

B2.4 程式演算法

程式演算法（Programming algorithms）介紹最常用的搜尋與排序演算法，以及如何用大 O 表示法（Big O notation）比較演算法效率。本頁涵蓋線性搜尋、二元搜尋、氣泡排序、選擇排序，HL 再加上遞迴、合併排序與快速排序。

如何比較演算法效率？

大 O 表示法 描述資料量 n 變大時，演算法執行步驟數的成長趨勢（通常指最差情況）：

除了時間複雜度，也要考慮 空間複雜度：演算法需要多少額外記憶體。

線性搜尋和二元搜尋怎麼選？

線性搜尋（linear search）：從頭到尾逐一比對。資料不必排序，時間 O(n)。

二元搜尋（binary search）：資料 必須已排序。每次比對中間元素，排除一半資料，時間 O(log n)。

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

public static int binarySearch(int[] items, int target) {
    int low = 0, high = items.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (items[mid] == target) {
            return mid;
        } else if (items[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

氣泡排序與選擇排序

氣泡排序（bubble sort）：重複比較相鄰兩個元素，順序錯就交換。每一輪會把目前最大值「浮」到尾端。若某一輪完全沒有交換，代表已排好，可提早結束。

選擇排序（selection sort）：每一輪找出未排序部分的最小值，和未排序部分的第一個元素交換。

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if a[j] < a[min_index]:
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]
    return a

遞迴

遞迴（recursion） 是函式呼叫自己來解決較小的同類問題。每個遞迴函式必須有：

1. 基本情況（base case）：不再遞迴、直接回傳的條件，否則會無限遞迴導致 堆疊溢位（stack overflow）。
2. 遞迴情況（recursive case）：把問題縮小後呼叫自己。

def factorial(n):
    if n <= 1:              # 基本情況
        return 1
    return n * factorial(n - 1)   # 遞迴情況

# factorial(4) = 4 * factorial(3)
#              = 4 * 3 * factorial(2)
#              = 4 * 3 * 2 * factorial(1)
#              = 24

每次呼叫都會在 呼叫堆疊（call stack） 上新增一層，因此遞迴比迴圈耗記憶體；但對樹狀結構、分治法等問題，遞迴的程式碼更簡潔。

合併排序與快速排序

兩者都是 分治法（divide and conquer）：

• 合併排序（merge sort）：把陣列不斷對半切到只剩 1 個元素，再兩兩合併成已排序的陣列。時間永遠 O(n log n)，但需要額外 O(n) 記憶體。
• 快速排序（quicksort）：選一個基準值（pivot），把小於它的放左邊、大於它的放右邊，再分別遞迴排序兩邊。平均 O(n log n)，最差（pivot 每次都選到最大或最小）O(n²)，通常不需要額外陣列。

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    result, i, j = [], 0, 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
    return result + left[i:] + right[j:]

推薦影音

大 O 表示法

簡述：HackerRank 用實例說明如何從程式碼推算時間複雜度，以及為什麼可以省略常數與低次項，對應本頁效率比較一節。

二元搜尋

簡述：說明二元搜尋的運作方式，並示範迴圈與遞迴兩種寫法，特別提醒邊界條件的處理。

氣泡排序

簡述：用圖解與程式碼說明氣泡排序，並介紹「沒有交換就提早結束」的最佳化。

遞迴

簡述：HackerRank 說明遞迴的基本情況與遞迴情況，以及如何避免重複計算，適合 HL 學生入門遞迴。

合併排序

簡述：逐步示範合併排序的切分與合併過程，並分析為什麼是 O(n log n)。

快速排序

簡述：說明 pivot 的選擇與分割（partition）過程，並比較快速排序與合併排序的優缺點。

練習題

def second_largest(nums):
    first = second = float("-inf")
    for n in nums:
        if n > first:
            second = first
            first = n
        elif first > n > second:
            second = n
    return second

def power(base, exp):
    if exp == 0:          # 基本情況
        return 1
    return base * power(base, exp - 1)