原住民族考試四等考試-電子工程類科計算機概要113 年第 20 題單選題
以快速排序法（Quick Sort）與堆積排序法（Heap Sort）來排序 n 筆資料，其最壞狀況（Worst case）的時間複雜度為：
A前者：O(n2)，後者：O(nlogn)正確答案
B前者：O(nlogn)，後者：O(n2)
C兩者均是 O(nlogn)
D兩者均是：O(n2)
A正確答案
Quick Sort 最壞 O(n²),Heap Sort 最壞 O(n log n),故選 (A)。
為什麼答案是 A
正確。Quick Sort 最壞 O(n²),Heap Sort 最壞 O(n log n)。
載入中…
完整詳解
Pro · 無限重點 Quick Sort 最壞 O(n²),Heap Sort 最壞 O(n log n),故選 (A)。
1. Quick Sort 最壞情況發生於每次選的 pivot 為最大或最小值(如已排序資料且取首尾為 pivot),分割極不平均,遞迴深度為 n,總比較次數為 n+(n-1)+...+1 = O(n²)。
2. Quick Sort 平均時間為 O(n log n),但最壞為 O(n²)。
3. Heap Sort 利用最大堆/最小堆,建堆 O(n),每次取出堆頂後重建堆需 O(log n),共 n 次,總時間恆為 O(n log n),最壞情況也是 O(n log n)。
4. 故前者 O(n²)、後者 O(n log n),答案為 (A)。
逐選項分析
A✓ 正確
正確。Quick Sort 最壞 O(n²),Heap Sort 最壞 O(n log n)。
B✕
錯誤。前後順序顛倒,Quick Sort 才會出現 O(n²) 的最壞情況。
C✕
錯誤。Quick Sort 平均才是 O(n log n),最壞為 O(n²)。
D✕
錯誤。Heap Sort 不論最壞、平均、最佳皆為 O(n log n)。
勿將 Quick Sort 平均複雜度 O(n log n) 誤當成最壞;Heap Sort 三種情況皆 O(n log n)。 
