申論題

試卷：108年 - 108 中華郵政股份有限公司_職階人員甄試_專業職(一)/系統操作_專業科目(1)：資訊科學概論(含電腦基礎知識、資料結構、網路基本知識、資訊安全)#75271
科目：計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)
年份：108年
排序：0

申論題資訊

試卷：108年 - 108 中華郵政股份有限公司_職階人員甄試_專業職(一)/系統操作_專業科目(1)：資訊科學概論(含電腦基礎知識、資料結構、網路基本知識、資訊安全)#75271
科目：計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)
年份：108年
排序：0

題組內容

第二題：請就插入排序法(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)A(1) 已排序。
- 從第二個元素開始遍歷陣列，即 i 從 2 開始到 N（陣列的總長度）。
內部循環和元素插入：
- 將當前元素 A(i) 存儲在一個變量 key 中。
- 將前一個索引存儲在變量 j，用於比較和尋找 key 的正確位置。
- 進行內部循環：只要 j 沒有減到 0（超出陣列起始邊界）且A(j) 大於 key，就將A(j) 向右移動一個位置，以便為 key 騰出空間。
- 當找到 key 的正確位置或 j 減至 0 時，將 key 插入到 A(j+1)。
重複直到所有元素被檢查：
- 繼續對每個元素重複以上步驟，直到所有元素都被檢查過並放在適當位置。

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