請問下列的C 語言函式xxxSort()是在執行那種排序演算法？請說明 理由。（10 分） void xxxSort(int arr[], int n) { i…

題目

請問下列的C 語言函式xxxSort()是在執行那種排序演算法？請說明 理由。（10 分） void xxxSort(int arr[], int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } 費氏數列的定義為： F(0)=0, F(1)=1 F(n)=F(n−1)+F(n−2), n≥2 假設我們要寫一個程序來算出F(n)，可以用遞迴（recursive）方式，也 可用迭代（iterative）方式來寫程式。請問這兩種方式的優缺點為何？ （10 分）

參考解答（AI 生成，非官方）

• 一、演算法判定：此函式為插入排序（Insertion Sort）。外層迴圈 i 由 1 遞增至 n−1，每回合取出 key = arr[i]，內層 while 將所有大於 key 的元素逐一右移一格，最後把 key 放入 arr[j+1]，正是「前段已排序、逐筆插入」的典型結構。
• 二、判定理由與性質：程式中以 arr[j] > key 作為搬移條件，且只在嚴格大於時搬移，故相等元素不會互換，屬穩定排序（stable sort）；全程只使用常數個額外變數，屬原地排序（in-place）。最佳情況為輸入已排序時，內層不執行，時間複雜度 O(n)；最差與平均為 O(n^2)，適用於資料量小或近乎排序的資料。
• 三、與其他排序的區別：氣泡排序（Bubble Sort）是相鄰兩兩交換、每回合把最大值推到尾端；選擇排序（Selection Sort）是每回合在未排序區找最小值再與前端交換；合併排序（Merge Sort）需額外陣列與遞迴分割。本題沒有相鄰交換、沒有找最小值、也沒有遞迴，故可排除。
• 四、遞迴方式計算費氏數列：優點是程式碼直接對應 F(n)=F(n−1)+F(n−2) 的數學定義，簡潔易讀、易驗證正確性；缺點是未加記憶化（memoization）時，同一子問題被重複計算，時間複雜度達 O(2^n)，且遞迴深度為 n，n 較大時會造成堆疊溢位（stack overflow），每次函式呼叫亦有額外開銷。
• 五、迭代方式：以兩個變數滾動保存 F(n−2)、F(n−1)，時間複雜度 O(n)、空間 O(1)，無堆疊溢位風險、執行效率高；缺點是程式較不直觀，需自行處理 n=0、n=1 的邊界條件，且若日後要改求其他遞迴式，改寫成本較高。
• 六、建議：實務上可採迭代法，或採遞迴搭配記憶化（即動態規劃，Dynamic Programming），將時間降為 O(n)；若語言支援，也可使用尾遞迴（tail recursion）讓編譯器優化。考生作答時應明確寫出兩者的時間、空間複雜度對照，以顯示層次。

AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。

官方資料

• 官方試題 PDF