民國100年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第41題
快速排序法( Q u i c k S o r t ) 可用下列何種策略來解題?
題目
快速排序法( Q u i c k S o r t ) 可用下列何種策略來解題?
- (1) 各個擊破法( D i v i d e a n d C o n q u e r )
- (2) 動態規劃( D y n a m i c P r o g r a m m i n g )
- (3) 貪婪法( G r e e d y )
- (4) 分支與限制法( B r a n c h a n d B o u n d )
官方答案
(1) 各個擊破法( D i v i d e a n d C o n q u e r )
解析
快速排序採用各個擊破法：先選一個基準值（pivot），經分割（partition）把比基準小的元素放左邊、大的放右邊，再對左右兩個子數列分別遞迴做同樣的事，最後即完成排序，平均時間複雜度 O(n log n)。動態規劃適用於具有重疊子問題的題目（如背包問題）；貪婪法每步取區域最佳解；分支與限制法則用於組合最佳化並以界限剪枝。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。