Q138.
快速排序法(Quick Sort)可用下列何種策略來解題？
電腦軟體設計共同科目 · 乙級 · Q138
難易度分析
2 / 5
本題考查對演算法設計基本策略的定義與對應關係，屬於基礎概念的記憶型題目，只要掌握核心術語即可快速判定。
正確答案：①各個擊破法(Divide and Conquer)
① 各個擊破法(Divide and Conquer):快速排序法的核心機制正是各個擊破法(Divide and Conquer)：透過選取基準元素(Pivot)將陣列分割為兩個子陣列，再遞迴排序各子陣列，最後合併結果。
錯誤選項解析
- ② 動態規劃(Dynamic Programming):動態規劃適用於具有重疊子問題與最佳子結構特性的問題（如費氏數列、最短路徑），透過儲存子問題解避免重複計算；快速排序的子問題彼此獨立，無需記憶化。
- ③ 貪婪法(Greedy):貪婪法是在每一步驟中選取區域最佳解以期望達到全域最佳解（如 Kruskal 最小生成樹演算法）；快速排序並非基於貪婪策略，而是透過遞迴分割來完成排序。
- ④ 分支與限制法(Branch and Bound):分支與限制法主要用於組合最佳化問題（如旅行推銷員問題、0/1 背包問題），透過計算上下界來剪枝搜尋空間；快速排序是純粹的排序演算法，不涉及最佳化搜尋。
Learning Tip
"快速排序法與合併排序法(Merge Sort)皆採用各個擊破法，兩者的差異在於：快速排序的分割(Partition)動作在遞迴前完成，而合併排序的合併(Merge)動作在遞迴後執行。考試中常將四種演設計策略（各個擊破、動態規劃、貪婪法、分支與限制法）交叉混淆，需牢記各策略的適用情境與代表性演算法。"
學員答題分佈
①各個擊破法(Divide and Conquer)0%
②動態規劃(Dynamic Programming)0%
③貪婪法(Greedy)0%
④分支與限制法(Branch and Bound)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！