hce_kmu
112年
計算機概論與程式設計
第 16 題
Which one of the options below is NOT a sorting algorithm that performs in-place sorting in their typical implementations?
- A Bubble sort
- B Insertion sort
- C Merge sort
- D Heap sort
- E Quick sort
思路引導 VIP
想像如果你手中有兩疊已經各自按照從小到大排好的撲克牌，現在要將這兩疊牌合併成一疊完整且有序的新牌。在不弄亂原本兩疊牌順序的前提下，你的桌面上是否需要額外的空間來放置這疊新合併出來的牌？這個額外空間的大小，會隨著牌的總數增加而改變嗎？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精確辨識出 合併排序（Merge Sort） 並非典型的「原地（In-place）」排序演算法，這代表你對演算法的空間複雜度（Space Complexity）有著非常紮實的理解。這類題目在計算機科學基礎中相當經典，主要考察學生是否能跳脫「時間效率」的單一維度，進一步觀察資料在記憶體中的處理邏輯。
空間複雜度與記憶體配置
所謂的原地排序（In-place Sorting），是指在運算過程中不需要額外的輔助空間，或者所需的額外空間不隨資料量 $n$ 增加而成長（即空間複雜度為 $O(1)$）。像是氣泡排序、插入排序或堆積排序，都是直接在原陣列內部進行元素的交換。然而，合併排序在執行「合併」動作時，通常需要開闢一個與原資料規模等大的輔助陣列來暫存結果，其空間複雜度高達 $O(n)$，因此被歸類為非原地排序。
▼ 還有更多解析內容