地特四等
114年
[電子工程] 計算機概要
第 20 題
對於排序（Sorting）的敘述，下列何者正確？
- A 快速排序（Quick Sort）速度快，無論在何種資料情況下都能有 O(n logn)的效能
- B 插入排序（Insertion Sort）最差的情況下，所花時間是 O(n^2)，但平均情況的效能會是 O(n logn)
- C 合併排序（Merge Sort）平均情況的效能是 O(n logn)，且為穩定排序（Stable Sort）
- D 堆積排序（Heap Sort）平均情況的效能是 O(n logn)，且為穩定排序（Stable Sort）
思路引導 VIP
想像你手中有兩張數值相同但顏色不同的標籤，如果你希望排序後這兩張標籤的相對前後順序保持不變，這種「保序」的特性在計算機科學中稱為什麼？再者，如果一個演算法每次都能將問題均勻地一分為二處理，且不需要依賴運氣來避開最差狀況，它的時間成本通常會趨近於哪種數學函數？
🤖
AI 詳解
AI 專屬家教
同學，很高興看到你精確地選出了正確答案。這反映出你對演算法的核心特性——**時間複雜度（Time Complexity）與穩定性（Stability）**有著非常清晰的邏輯判斷。在工程實務中，我們追求的往往不只是「快」，更重要的是「預期中的穩定」。
演算法的穩定性與效能分析
**合併排序（Merge Sort）之所以備受青睞，主因在於它採用「分而治之（Divide and Conquer）」的策略，無論初始資料的排列順序如何，其執行時間均穩定維持在 $O(n \log n)$。更關鍵的是，它具備穩定排序（Stable Sort）**的特質，這代表數值相等的元素在排序後的相對位置不會變動。相較之下，**快速排序（Quick Sort）在最差情況下會退化至 $O(n^2)$，而堆積排序（Heap Sort）**雖然平均效能同樣優秀，卻是非穩定排序，這在處理具有多重鍵值的資料結構時會是一大限制。
▼ 還有更多解析內容