高考申論題
106年
[資訊處理] 資料結構
第 三 題
表二列出五種常見的排序演算法，請填滿該表以顯示各排序法在最佳情況、一般情況、最壞情況下的時間複雜度、所需額外記憶體空間及是否為穩定排序法。快速排序法的各項資料已事先填入作為範例。（(a),(b),(c),(d)各 5 分，共 20 分）
表二內容：
- 快速排序法 (quicksort): O(n log n), O(n log n), O(n^2), O(log n) [註: 題目寫 O(n)], 不是
- (a)泡沫排序法 (bubble sort)
- (b)插入排序法 (insertion sort)
- (c)合併排序法 (merge sort)
- (d)堆積排序法 (heap sort)
📝 此題為申論題
思路引導 VIP
看到排序演算法比較表，首先回憶各演算法的核心機制與交換方式。特別注意區分『最佳情況』是否有提早結束的優化（如泡沫、插入在已排序時為 O(n)），以及『穩定性』的判定原則（相鄰交換通常穩定，跳躍交換如 Heap Sort 則不穩定）。
🤖
AI 詳解
AI 專屬家教
【解答】 以下為各排序演算法的時間複雜度、額外空間與穩定性之完整表格內容填答： | 演算法 | 最佳情況<br>(best case) | 一般情況<br>(average case) | 最壞情況<br>(worst case) | 所需額外空間 | 是或不是穩定排序法<br>(stable sort) |
▼ 還有更多解析內容