二分查詢和合併排序如何用於 GCSE?

如果你正在複習 GCSE 電腦科學的演算法,有四個名字會一次次出現:線性查詢、二分查詢、氣泡排序和合併排序。考試委員會喜歡要求你手動追蹤這些演算法、找出執行時間,或填入遺漏的虛擬碼行。這裡說明了考試中真正重要的內容,以及更深層的知識。

線性查詢:基礎方法

線性查詢逐一檢查列表中的每一項,直到找到目標或到達末尾為止。就這樣。

for i = 0 to length(list) - 1
    if list[i] == target then
        return i
return -1

最壞情況下,你要檢查每一個元素,所以是 O(n)。最好的情況下,目標在第一個,所以是 O(1)。考官喜歡要求你同時說出兩者。線性查詢適用於未排序的資料,這是它比起二分查詢唯一真正的優勢。

二分查詢:令人困惑的那個

二分查詢只適用於已排序的列表。你將目標與中間項比較。如果目標較小,捨棄上半部;如果較大,捨棄下半部。重複直到找到或用完項目為止。

low = 0
high = length(list) - 1
while low <= high
    mid = (low + high) / 2
    if list[mid] == target then
        return mid
    else if list[mid] < target then
        low = mid + 1
    else
        high = mid - 1
return -1

這是 O(log n),所以在大型資料集上快得多。在一百萬項的已排序列表中搜尋,線性查詢可能需要多達一百萬次比較;二分查詢只需約 20 次。考官通常會給你一個列表,例如 16 個數字,要求你追蹤檢查哪些索引──用紙筆親手練習這個,不要只在腦海裡進行。

氣泡排序:簡單但緩慢

氣泡排序反覆遍歷列表,如果相鄰項目順序錯誤則交換它們。每次完整遍歷都會將最大的未排序項推到末尾的正確位置。

for i = 0 to length(list) - 1
    for j = 0 to length(list) - 2 - i
        if list[j] > list[j+1] then
            swap(list[j], list[j+1])

最壞情況是 O(n²)──對於每個元素,你可能需要再次掃描幾乎整個列表。它在實際軟體中很少使用,因為在大型資料上很慢,但考官喜歡它,因為手動追蹤是可以管理的,清楚地展示了重複遍歷和交換的概念。知道如何在追蹤表中計算比較和交換的次數;這是常見的計分項目。

合併排序:分治法

合併排序反覆將列表分成兩半,直到每個子列表只有一項,然後將這些子列表以排序順序合併在一起。

function mergeSort(list)
    if length(list) <= 1 then
        return list
    mid = length(list) / 2
    left = mergeSort(list[0:mid])
    right = mergeSort(list[mid:])
    return merge(left, right)

合併步驟比較每一半的前項目並選擇較小的那個,重複直到兩個半邊用完為止。這給出 O(n log n),在除了微小列表外的任何情況下都遠優於氣泡排序。GCSE 題目有時會要求你畫出分割和合併圖表──一個樹狀圖形,顯示列表向下分割然後重新組合。用 8 個數字的列表練習畫這個,這樣你在考試時速度會快。

考官實際測試什麼

大多數計分方案要求你能夠:

• 逐步追蹤演算法並寫下每次遍歷或比較後列表的狀態。
• 用 Big O 術語說明時間複雜度,或至少用詞語描述它(