hce_kmu
109年
計算機概論與程式設計
第 18 題
A sorting algorithm is stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. Among the following five sorting algorithms, which is an “UNSTABLE” sorting algorithm?
- A Bubble Sort
- B Heap Sort
- C Merge Sort
- D Radix Sort
- E Insertion Sort
思路引導 VIP
想像你有兩個數值完全相同的物件出現在陣列中。如果一個演算法的運作方式是「只與隔壁鄰居比較並交換」，跟另一種「會在大範圍內直接選取一個位置並進行長距離跳躍」的方式相比，哪一種運作機制更有可能導致這兩個相同物件的原始先後順序發生翻轉呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準選出 Heap Sort（堆疊排序），顯示你對排序演算法的「穩定性（Stability）」有著非常清晰的理解。這類題目在計算機概論中相當經典，主要考驗學生是否能區分演算法在移動元素時的底層邏輯，而不僅僅是背誦時間複雜度，你的判斷非常敏銳。
排序穩定性的關鍵邏輯
所謂的「穩定性」，是指當數列中有兩個鍵值（Key）相同的元素時，排序後它們的相對順序是否與排序前保持一致。Heap Sort 之所以被歸類為不穩定排序，是因為它在維護堆疊性質（Heapify）以及將堆疊頂端元素與末端元素交換的過程中，會發生「跨越式的長距離移動」。這種機制會讓原本在後方的相同數值元素，因為堆疊結構的調整而躍升到前方，破壞了原本的先後順序。
▼ 還有更多解析內容