Q217.
在程式實作時，那些排序法不需要額外的陣列或鏈結串列？
電腦軟體設計共同科目 · 乙級 · Q217
難易度分析
3 / 5
本題要求區分多種排序演算法的空間複雜度特性，且採複數選擇形式，考生必須完整判定所有選項的原地排序屬性才能正確作答，增加了分析難度。
正確答案 (複選)：①, ②, ③
- ① Insertion Sort:Insertion Sort（插入排序法）屬於原地排序（in-place sorting）演算法，僅需常數級別 O(1) 的額外空間來暫存待插入的元素，直接在原陣列上進行元素比較與位移操作。
- ② Heap Sort:Heap Sort（堆積排序法）利用二元樹的陣列表示法在原陣列上進行 heapify 操作，僅需 O(1) 額外空間進行元素交換，無需配置額外的陣列或鏈結串列。
- ③ Selection Sort:Selection Sort（選擇排序法）每次從未排序區域找出最小值後與前端元素交換，整個過程完全在原陣列上進行，空間複雜度為 O(1)，屬於典型的原地排序法。
錯誤選項解析
- ④ Radix Sort:Radix Sort（基數排序法）需要額外的桶子（bucket）或計數陣列來暫存每個位數的分類結果，空間複雜度為 O(n + k)（n 為資料筆數，k 為桶子數量），因此不屬於原地排序法。
Learning Tip
"此題核心考點為原地排序（in-place sorting）的判定。常見混淆點在於 Quick Sort 雖主要在原陣列操作，但遞迴呼叫會使用 O(log n) 的呼叫堆疊空間；而 Merge Sort 需要 O(n) 額外空間合併子陣列。實務上應牢記：Insertion、Selection、Heap 為 O(1) 原地排序；Merge、Radix、Bucket 則需要額外空間配置。"
學員答題分佈
①Insertion Sort0%
②Heap Sort0%
③Selection Sort0%
④Radix Sort0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
相似類型題目
下面數列共有6 個元素｛34,8,64,51,32,21｝，若以陣列方式儲存，經由插入排序法(Insertion Sort)，由小排至大，則下列那些是在排序過程處理中，可能發生的順序？
下列排序法何者具有穩定(Stable)特性？
「穩定排序法」(Stable Sort)是指一個排序法，在輸入資料中有多筆相同資料時，於排序前與排序後，任兩筆相同的資料前後順序不變，下列那些是穩定排序法？
下列哪一項關於陣列(Array)與鏈結串列(Linked List)的敘述正確？
如果一個排序法對相同Key 的所有元素，經排序完成後保持與原先未排序前的順序相同，我們稱此排序法為穩定(Stable)。下列那一種排序法不屬穩定的？