1. 下列四種排序法(1)Insertion Sort (2)Quick sort (3)Merge Sort (4)Bubble Sort，
哪些是遞迴式(Recursive)的演算法？
(A) 1、2
(B) 1、4
(C) 2、3
(D) 3、4

屬於遞迴式（Recursive）演算法的有：

• (2) Quick Sort (快速排序)

• (3) Merge Sort (合併排序)

詳細說明

1. Quick Sort (快速排序)

快速排序採用分治法 (Divide and Conquer)。它的遞迴邏輯如下：

• 從數列中挑選一個基準值 (Pivot)。

• 將數列分為兩部分：比基準值小的在左邊，比基準值大的在右邊。

• 遞迴地對左右兩個子數列進行同樣的操作，直到子數列的大小為 0 或 1。

2. Merge Sort (合併排序)

合併排序同樣是典型的分治法應用：

• 將目前的數列從中間切半，分成兩個子數列。

• 遞迴地對這兩個子數列進行切分，直到每個子數列只剩下一個元素。

• 最後將這些排序好的子數列兩兩合併 (Merge)，最終完成排序。

3. Insertion Sort (插入排序) 與 Bubble Sort (泡沫排序)

這兩種演算法通常使用疊代（Iterative，即迴圈）的方式實作：

• Insertion Sort：透過逐一將未排序的元素插入到已排序部分的正確位置。

• Bubble Sort：透過重複交換相鄰且順序錯誤的元素，讓最大值像氣泡一樣逐漸「浮」到末端。

• 註：雖然這兩者也可以改寫成遞迴版本，但在標準定義與教學實務中，它們被歸類為非遞迴的疊代演算法。

總結表