什麼是插入排序法？
插入排序法是一種簡單的排序演算法，透過將未排序的元素插入到已排序部分的正確位置來完成排序。
演算法特點
- 簡單直觀：類似整理撲克牌的過程
- 穩定排序：相等元素的相對位置不改變
- 原地排序：不需要額外的記憶體空間
- 適應性強：對於部分有序的陣列效率較高
排序原理
將陣列分為已排序和未排序兩部分，每次從未排序部分取出第一個元素，插入到已排序部分的正確位置。
互動演示
比較次數：0
交換次數：0
當前步驟：就緒
Insertion Sort - 可視化演示與詳細解釋
插入排序法是一種簡單的排序演算法，透過將未排序的元素插入到已排序部分的正確位置來完成排序。
將陣列分為已排序和未排序兩部分，每次從未排序部分取出第一個元素，插入到已排序部分的正確位置。
比較次數：0
交換次數：0
當前步驟：就緒
| 情景 | 時間複雜度 | 說明 |
|---|---|---|
| 最好情況 | O(n) | 陣列已排序，只需一次掃描 |
| 平均情況 | O(n²) | 隨機排列的陣列 |
| 最壞情況 | O(n²) | 陣列反向排序，需要最多比較 |
| 空間複雜度 | O(1) | 原地排序，僅需常數額外空間 |
這裡展示 Insertion Sort 的主要邏輯，讓虛擬碼與 JavaScript 程式碼一一對應。
function insertionSort(arr):
for i in 1..length(arr)-1:
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j = j - 1
arr[j+1] = keyasync function insertionSort() {
const n = array.length;
for (let i = 1; i < n; i++) {
if (!isSorting) return;
const key = array[i];
let j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
render([], [j + 1], Array.from({ length: i }, (_, idx) => idx));
await sleep(getDelay());
}
array[j + 1] = key;
}
}const n = array.length; -> 取得資料長度，設定動畫資料範圍
const key = array[i]; -> 選取目前待插入的長條，顯示高亮狀態
while (j >= 0 && array[j] > key) { -> 比較待插入元素與已排序區域的元素
array[j + 1] = array[j]; -> 向右移動已排序元素，動畫模擬元素後移
render(...); -> 更新畫面，顯示目前比較、移動與排序區域
array[j + 1] = key; -> 將待插入元素放回正確位置，顯示插入動畫