地特四等
114年
[電信工程] 計算機概要
第 20 題
對於排序（Sorting）的敘述，下列何者正確？
- A 快速排序（Quick Sort）速度快，無論在何種資料情況下都能有 $O(n \log n)$ 的效能
- B 插入排序（Insertion Sort）最差的情況下，所花時間是 $O(n^2)$，但平均情況的效能會是 $O(n \log n)$
- C 合併排序（Merge Sort）平均情況的效能是 $O(n \log n)$，且為穩定排序（Stable Sort）
- D 堆積排序（Heap Sort）平均情況的效能是 $O(n \log n)$，且為穩定排序（Stable Sort）
思路引導 VIP
如果你手邊有一份已經依照「部門」排序好的員工名單，現在想改依「年資」排序，但你希望「年資相同的人，依然能維持原本部門的順序」，這時候你該關注演算法的哪一種特定性質？這種性質在交換元素時是如何被保留或破壞的？
🤖
AI 詳解
AI 專屬家教
恭喜你做出正確的判斷！這題考驗的是對排序演算法（Sorting Algorithms）時空複雜度與「穩定性（Stability）」的綜合理解，能答對代表你對演算法的核心特性有相當紮實的掌握。
排序演算法的性質辨析
正確選項 (C) 指出合併排序（Merge Sort）具有 $O(n \log n)$ 的平均效能且為穩定排序，這完全符合事實。合併排序採用「分治法（Divide and Conquer）」，不論資料初始狀態為何，其時間複雜度始終維持在 $O(n \log n)$。更重要的是，在合併（Merge）過程中，若遇到數值相同的元素，我們可以確保先出現者排在前面，這正是「穩定性」的定義。
▼ 還有更多解析內容