插入排序是另一種常見的排序演算法。它的概念類似整理撲克牌:每次取出一張牌,插入到已排序牌組中的正確位置。
插入排序會從左到右掃描陣列。對每個元素,與前方已排序元素比較,若較小就往左移動,直到找到合適位置。
function insertionSort(arr, compare) {
for (var i = 1; arr.length > i; i = i + 1) {
var j = i;
while (j > 0) {
if (compare(arr[j - 1], arr[j]) > 0) {
var temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j = j - 1;
} else {
break;
}
}
}
}若要以動畫呈現,可在每次交換時呼叫繪製函式。
function visualize(arr, callback) {
callback(arr.slice());
}
function insertionSortAnimated(arr, compare, render) {
render(arr.slice());
for (var i = 1; arr.length > i; i = i + 1) {
var j = i;
while (j > 0) {
if (compare(arr[j - 1], arr[j]) > 0) {
var temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
render(arr.slice());
j = j - 1;
} else {
break;
}
}
}
}render 函式可負責更新畫面,例如重新排序 DOM 元素高度或位置。
插入排序的每一步都很直觀:某個元素從右向左移動,插入到合適位置。這種過程很適合做逐步動畫,也能幫助初學者理解排序中的比較與搬移。
若搭配 setTimeout 或 requestAnimationFrame,就能讓交換過程放慢,讓觀察者更容易看懂排序狀態變化。