插入排序是所有排序演算法裡最適合當作入門的一個,因為它的運作方式就是人類整理撲克牌的方式。
插入排序的平均時間複雜度是平方級的,效率不高,但非常容易實作。它借助的是「逐步擴大成果」的思想,讓有序列表的長度慢慢增加,最後等於原列表的長度。
<script type="text/javascript">
var org = [5, 4, 3, 2, 1, 6, 7, 9, 8, 10];
var tempArr = new Array();
for (var i = 0; i < org.length; i++) {
if (i == 0) {
tempArr[0] = org[0]; // 第一個元素直接放進新序列
} else {
for (var j = 0; j < tempArr.length; j++) {
if (org[i] > tempArr[j]) {
// 如果是新序列的最後一個元素,直接附加
if (j == tempArr.length - 1) {
tempArr[j + 1] = org[i];
break;
} else {
continue; // 否則繼續往後找插入點
}
} else {
// 找到插入點:把後面的元素全部往後移一格
for (var k = tempArr.length - 1; k >= j; k--) {
tempArr[k + 1] = tempArr[k];
}
tempArr[j] = org[i];
break;
}
}
}
}
alert(tempArr);
</script>
外層迴圈每次從 org 取一張牌,內層迴圈在 tempArr 裡從頭比較,找出「第一個比它大的位置」。找到之後,把該位置到尾端的所有元素往後挪一格(k 迴圈),空出來的洞就放進新元素。如果一直比較到最後都沒找到更大的(代表它是目前最大的),就直接附加在尾端。
實務上不開新陣列,而是在原陣列上「從右往左挪」:
function insertionSort(arr) {
for (var i = 1; i < arr.length; i++) {
var current = arr[i];
var j = i - 1;
// 把比 current 大的元素全部往後移
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
這個版本更短、不需要額外記憶體,而且內層迴圈同時完成「比較」與「搬移」兩件事,沒有原版那個 break / continue 的分支迷宮。
雖然是 O(n²),它在實務上仍有一席之地:
最後補充:真正要排序時請直接用 arr.sort(),但記得數字排序必須傳比較函式 arr.sort((a, b) => a - b),否則會以字串順序排序,[10, 9, 1] 會變成 [1, 10, 9]。