阿摩線上測驗
題組內容
第二題：
請就插入排序法(Insertion sort)的觀念，回答下列問題：
（一）請簡述插入排序法。【10 分】
詳解 (共 5 筆)
詳解
插入排序法為每次只和自己前面已排序的值相比，值小往前放；且未排序的值之前的值必定已排序。
詳解
直接將未排序的數值與已排序的數列作比較，直接將數值插入正確位置。
例：9 5 8 4 6 3 7
已排序數列 未排序
9 5 8 4 6 3 7
59 8 4 6 3 7
589 4 6 3 7
4589 6 3 7
45689 3 7
345689 7
3456789
詳解
將資料分成已排序、未排序兩部份
依序由未排序中的第一筆(正處理的值)，插入到已排序中的適當位置
插入時由右而左比較，直到遇到第一個比正處理的值小的值，再插入
比較時，若遇到的值比正處理的值大或相等，則將值往右移
詳解
插入排序（英語：Insertion Sort）是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序資料，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用in-place排序（即只需用到 {\\displaystyle O(1)} {\\displaystyle O(1)}的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。
詳解
插入排序法（Insertion Sort）是一種簡單直觀的排序算法，它的工作原理類似於整理撲克牌。在插入排序中，元素被一個一個地取出並插入到已經排序的部分中的適當位置，從而達到整個數據序列的排序。這個算法適合於少量數據的排序，是一種穩定的排序方法。
算法步驟：
- 從第二個元素開始：將數列的第二個元素認為是未排序的第一個元素（第一個元素前面沒有其他元素，自然視為已排序）。
- 與已排序的元素比較：將這個元素和它前面的已排序部分的元素逐一比較，找到它適當的位置。
- 插入操作：在比較過程中，每當發現已排序元素比當前元素大，就將這個已排序元素向後移動一位，為當前元素騰出空間。
- 重複步驟：重複以上過程，直到整個數列都被視為已排序。
特點：
- 效率：對於較小的數據集，插入排序比其他複雜的排序算法（如快速排序和合併排序）表現更佳。
- 最佳情況：如果輸入數組已經是排序狀態，插入排序的時間複雜度是 O(n)。
- 最壞情況：如果輸入數組是反向排序的，時間複雜度將是 O(n2)。
- 穩定性：插入排序是穩定的排序方法，因為它不會改變相同元素的初始相對位置。
- 就地排序：插入排序是就地排序，不需要額外的儲存空間。
插入排序的直觀性和簡單性使它在處理小型數據集或幾乎已排序的數據時非常有效。