9.下列哪一個排序演算法在平均情況下的時間複雜度為 O(n log n)？
(A) Bubble Sort
(B) Selection Sort
(C)Merge Sort
(D) Insertion Sort

答案：登入後查看
統計： A(4), B(5), C(9), D(0), E(0) #3678240

詳解 (共 1 筆)

#7222419

【解題思路】

題目關鍵字：

  • 排序演算法（Sorting Algorithm）

  • 平均時間複雜度（Average Case）

  • O(n log n)

先記住：
在常見的排序法裡，只有進階排序法（如 Merge Sort／Quick Sort／Heap Sort）才會達到 O(n log n)。

而四個選項裡：

  • Bubble Sort（泡沫排序）：O(n²)

  • Selection Sort（選擇排序）：O(n²)

  • Merge Sort（合併排序）：O(n log n) ← 本題答案

  • Insertion Sort（插入排序）：平均 O(n²)

只有 Merge Sort（合併排序） 属於「平均 O(n log n)」。

【為什麼其他選項不正確（逐一破題）】

(A) Bubble Sort 泡沫排序

比較與交換次數大，平均 O(n²)，速度很慢。
不是 O(n log n)。

(B) Selection Sort 選擇排序

每次都找剩餘最小值，平均／最差都是 O(n²)。
不是 O(n log n)。

(C) Merge Sort 合併排序 ← 正確

分治法（Divide & Conquer）將資料切半後合併，
每一層成本 O(n)，深度 log n，
→ 總成本 O(n log n)。

(D) Insertion Sort 插入排序

資料接近排序時有效，但平均仍是 O(n²)。
不是 O(n log n)。

【延伸知識（短期衝刺必記表）】

演算法 中文 平均複雜度 排序方式
Bubble Sort 泡沫排序 O(n²) 比較交換
Selection Sort 選擇排序 O(n²) 找最小值
Insertion Sort 插入排序 O(n²) 插入適當位置
Merge Sort 合併排序 O(n log n) 分治法（穩定）
Quick Sort 快速排序 O(n log n) 分治法（不穩定）
Heap Sort 堆積排序 O(n log n) 利用 Heap

特別注意：
Merge Sort 是穩定排序、保證 O(n log n)，考試很愛考。

【記憶技巧】

口訣：

「三笨一聰明」
前面三個（泡、選、插）全部 O(n²)，
只有合併（Merge）是 O(n log n)。

另記：
「分治法（Divide & Conquer）＝ O(n log n) 的常見來源」

【常見錯誤】

  1. 看到 Quick Sort 就選 → 錯，本題沒有 Quick Sort。

  2. 誤以為 Insertion Sort 因為資料快排序好就很快 → 但平均仍是 O(n²)。

  3. 忘記 Merge Sort 是最穩、最保證 O(n log n) 的排序。

0
0