moea_joint_essay
113年
[資訊] 資訊管理、程式設計
第 五 題
五、請實作下列函式以完成設計 1 個插入排序法(Insertion Sort)，據以依參數值決定排序方式採遞增或遞減。（18 分）
bool isInverse(int x, int y, bool isAsc); //判斷傳入的 x、y 是否反序
void InsertionSort(int *arr, int len, bool isAsc); //插入排序
(註：參數 arr 為傳入的整數陣列；參數 len 為整數陣列的長度；參數 isAsc 為是否遞增，函式 InsertionSort 應呼叫函式 isInverse。)
bool isInverse(int x, int y, bool isAsc); //判斷傳入的 x、y 是否反序
void InsertionSort(int *arr, int len, bool isAsc); //插入排序
(註：參數 arr 為傳入的整數陣列；參數 len 為整數陣列的長度；參數 isAsc 為是否遞增，函式 InsertionSort 應呼叫函式 isInverse。)
📝 此題為申論題
思路引導 VIP
isInverse 用來判斷是否需要交換位置，若是遞增排序 (isAsc=true)，當前元素大於後面的元素 (x > y) 就是反序；遞減排序則相反。接著用標準的插入排序迴圈，使用 isInverse 來作為內層移動資料的判斷條件。
🤖
AI 詳解
AI 專屬家教
// 判斷傳入的 x、y 是否反序 (是否需要將元素往後挪動)
bool isInverse(int x, int y, bool isAsc) {
▼ 還有更多解析內容
插入排序法實作
💡 將資料逐一取出，在已排序序列中由後往前尋找適當位置插入。
🔗 插入排序法單輪運作邏輯
- 1 取出待排序值 — 暫存當前位置元素為 key，並記錄前一索引 j
- 2 判斷是否反序 — 呼叫 isInverse 判斷 arr[j] 與 key 是否需調換
- 3 元素向後挪動 — 若反序則 arr[j+1] = arr[j] 騰出前方空間
- 4 插入正確位置 — 當不滿足反序或到頭時，將 key 置入 arr[j+1]
↓
↓
↓
🔄 延伸學習：延伸學習：當資料量幾乎已排序時，插入排序的效率接近 O(n)。
