請問下列的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 起，把 arr[i] 存成 key，內層以 j=i-1 向左掃描，凡 arr[j] 大於 key 就右移一格，最後將 key 放入空出的位置。這正是把新元素插入已排序前綴的動作，維持迴圈不變式「arr[0..i-1] 已排序」，與選擇排序的元素交換、氣泡排序的相鄰交換明顯不同。
• 二、特性與複雜度：原地（in-place）排序，額外空間 O(1)；穩定（stable），相等元素的相對次序不變；具適應性（adaptive），資料接近排序時內層幾乎不移動，最佳情況 O(n)，最差與平均為 O(n^2)。適合小筆數或串流式、逐步到來的資料，也是許多函式庫處理小陣列時採用的混合排序（如 Timsort）之基礎。
• 三、遞迴（recursive）版的優點是程式碼直接對應數學定義 F(n)=F(n-1)+F(n-2)，可讀性高、易於驗證正確性；缺點是會重複計算大量重疊子問題（overlapping subproblems），時間複雜度達 O(2^n)，且遞迴深度 O(n) 佔用堆疊，n 大時有堆疊溢位（stack overflow）風險，函式呼叫亦有額外開銷。
• 四、迭代（iterative）版以兩個變數保存 F(n-1)、F(n-2)，迴圈由 2 到 n 逐項累加，時間 O(n)、空間 O(1)，無堆疊溢位與呼叫開銷，執行效率明顯較佳；缺點是程式較不直觀，需自行維護變數更新順序（須先暫存舊值再更新），邊界條件 n=0、n=1 要特別處理，除錯也較不口語化。
• 五、改進建議：遞迴版可加入記憶化（memoization）或動態規劃（dynamic programming），把時間降為 O(n)；講求效能時可用矩陣快速冪（matrix exponentiation）達 O(log n)，或以 Binet 公式配合浮點運算。兩種寫法在大 n 時都會面臨整數溢位，須改用大數（big integer）或取模運算。

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

官方資料

• 官方試題 PDF