視覺化展示
已排序區域
當前插入元素 (Key)
比較 / 位移中
300ms
演算法偽代碼
function insertionSort(arr):
1 n = arr.length
2 for i = 1 to n-1:
3 key = arr[i] // 取出準備要插入的牌
4 j = i - 1
5 while j >= 0 and arr[j] > key: // 往前尋找比對
6 arr[j+1] = arr[j] // 將較大的元素往後移
7 j = j - 1
8 arr[j+1] = key // 找到位置，插入卡牌
操作原理
插入排序法的工作原理與我們「打撲克牌時整理手牌」的方式非常相似。它會將陣列分為「已排序」與「未排序」兩個部分。初始狀態下，第一個元素被視為已排序。
接著，演算法會逐一從未排序部分取出元素，將其與已排序部分的元素由後往前進行比較，找到合適的位置並插入，直到所有元素都排序完畢。
操作過程
- 初始狀態： 假設陣列的第一個元素已經排好序。
- 選取元素： 取出下一個未排序的元素（稱為
key）。 - 向前比較與位移： 在已經排序的元素序列中，從後向前掃描。如果掃描到的已排序元素大於
key，就將該元素往後移一個位置，騰出空間。 - 插入元素： 重複步驟 3，直到找到一個小於或等於
key的元素，並將key插入到該位置的後方。 - 重複： 重複步驟 2 到 4，直到整個陣列排序完成。
複雜度分析
- 時間複雜度 (最佳情況):
O(n)
當陣列已經是排序好的狀態時，每次比較只需進行一次，不需要移動元素，效率極高。 - 時間複雜度 (平均/最壞情況):
O(n2)
當陣列是反序時，每個新取出的元素都需要與前面所有已排序的元素進行比較並移動，耗費較多時間。 - 空間複雜度 (Space Complexity):
O(1)
插入排序也是一種「原地排序 (In-place Sort)」，只需要一個變數key來暫存當前元素，不需額外配置大記憶體空間。