題組內容

第二題： 請就插入排序法(Insertion sort)的觀念，回答下列問題：

（二）請依據下列規定，以虛擬碼（pseudo-code）寫出插入排序演算法：【20 分】
 (1) A 是擬排序的資料集合，是由 N 個鍵值組成的陣列(array)。
 (2) A 有 N 個元素，A = {A(1), A(2), ..., A(N)}。 
(3)在陣列 A 中進行插入排序法的遞增排序(ascending sort)。

詳解 (共 1 筆)

詳解 提供者：hchungw
Procedure InsertionSort(A) N = length(A) For i from 2 to N key = A(i) j = i - 1 // 將 A(i) 插入到已排序的序列 A(1) 到 A(i-1) While j > 0 and A(j) > key A(j + 1) = A(j) j = j - 1 End While A(j + 1) = key End For End Procedure

虛擬碼解釋：

  1. 初始化和條件設定：

    • 開始時假設陣列的第一個元素 (1)A(1) 已排序。
    • 從第二個元素開始遍歷陣列，即 i 從 2 開始到 N（陣列的總長度）。

  2. 內部循環和元素插入：

    • 將當前元素 A(i) 存儲在一個變量 key 中。
    • 將前一個索引存儲在變量 j，用於比較和尋找 key 的正確位置。
    • 進行內部循環：只要 j 沒有減到 0（超出陣列起始邊界）且A(j) 大於 key，就將A(j) 向右移動一個位置，以便為 key 騰出空間。
    • 當找到 key 的正確位置或 j 減至 0 時，將 key 插入到 A(j+1)。

  3. 重複直到所有元素被檢查：

    • 繼續對每個元素重複以上步驟，直到所有元素都被檢查過並放在適當位置。

這種排序方法在陣列部分已排序或完全排序時表現尤為高效，因為它減少了不必要的比較和移動。