原住民族考試四等考試-電子工程類科計算機概要106 年第 17 題單選題
關於實作快速排序法（quick sort），下列那種資料結構是有助益的？
A堆疊（stack）正確答案
B集合（set）
C串列（list）
D佇列（queue）
A正確答案
快速排序遞迴分割，用堆疊(stack)的LIFO特性可模擬遞迴呼叫，便於非遞迴實作。
為什麼答案是 A
快速排序本質是遞迴分割（divide and conquer），每次 partition 後需處理左右兩段。用 stack 保存子區間的起訖索引，後進先出正好模擬遞迴呼叫堆疊，可將遞迴版改寫為迭代版。
載入中…
完整詳解
Pro · 無限重點 快速排序遞迴分割，用堆疊(stack)的LIFO特性可模擬遞迴呼叫，便於非遞迴實作。
逐選項分析
A✓ 正確
快速排序本質是遞迴分割（divide and conquer），每次 partition 後需處理左右兩段。用 stack 保存子區間的起訖索引，後進先出正好模擬遞迴呼叫堆疊，可將遞迴版改寫為迭代版。
B✕
集合(set)不允許重複且無順序，無法保存排序過程中的索引順序，對快速排序的分割流程沒有幫助。
C✕ 陷阱
串列(list)是被排序的資料容器本身，不是「輔助」快速排序演算法的資料結構。題目問的是實作演算法流程需要的輔助結構。
D✕ 陷阱
佇列(queue)是 FIFO，適合廣度優先(BFS)。快速排序是深度優先分割，用 FIFO 會失去遞迴呼叫的語意，效果不如 stack 自然。
排序演算法 × 輔助資料結構
| 演算法 | 核心技巧 | 輔助結構 | 時間複雜度 |
|---|
| 快速排序 Quick Sort | 分割遞迴(DFS) | Stack | 平均 O(n log n) |
| 合併排序 Merge Sort | 分割合併 | 暫存陣列 | O(n log n) |
| 堆積排序 Heap Sort | 最大/最小堆 | Heap | O(n log n) |
| 基數排序 Radix Sort | 分桶 | Queue | O(nk) |
C 選項 list 是「被排序的對象」，考生容易誤以為選它；但題目問的是「有助於實作」的輔助結構。快速排序的精髓在遞迴分割，需要的是能保存呼叫狀態的 stack，而不是裝資料的 list。 
