對於排序（Sorting）的敘述，下列何者正確？

題目

對於排序（Sorting）的敘述，下列何者正確？ A. 快速排序（Quick Sort）速度快，無論在何種資料情況下都能有O(n logn)的效能 B. 插入排序（Insertion Sort）最差的情況下，所花時間是O(n2)，但平均情況的效能會是O(n logn) C. 合併排序（Merge Sort）平均情況的效能是O(n logn)，且為穩定排序（Stable Sort） D. 堆積排序（Heap Sort）平均情況的效能是O(n logn)，且為穩定排序（Stable Sort）

官方答案

• 答案：C. 合併排序（Merge Sort）平均情況的效能是O(n logn)，且為穩定排序（Stable Sort）

解析

合併排序（Merge Sort）將序列不斷對半分割再逐層合併，每層合併成本為 O(n)，共約 O(log n) 層，因此平均與最差皆為 O(n log n)；合併時若遇相等元素，可優先取左半邊者，維持原相對次序，故為穩定排序，C 正確。快速排序最差情況（如已排序資料卻固定挑端點為基準）會退化為 O(n²)；插入排序平均仍為 O(n²)；堆積排序雖為 O(n log n)，但交換過程會破壞相等元素的相對次序，並不穩定。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。