直接插入排序是最直觀的排序演算法之一,非常適合作為演算法入門。以下先講清楚它的基本思想,再附上完整的 JavaScript 實作。
假設待排序的記錄存放在陣列 R[1..n] 中。初始時,R[1] 自成一個有序區,無序區則為 R[2..n]。從 i=2 起直到 i=n,依序把 R[i] 插入到當前有序區 R[1..i-1] 的正確位置,逐步擴大有序區,最終生成含 n 個記錄的有序區。
打個比方,這就像我們整理撲克牌:手牌始終保持有序,每摸到一張新牌,就從右往左比對,找到合適的位置插入。
<!doctype html>
<html>
<head><title>javascript直接插入排序</title>
<meta charset = "utf-8" />
</head>
<body>
<script>
var arr = [];
for(var i = 0; i < 20; ++i)
{
arr.push(~~(Math.random() * 20));
}
document.write(arr + "<br/>");
Array.prototype.insertionSort = function()
{
var j;
var value;
for(var i = 1; i < this.length; i++)
{
j = i;
value = this[j];
while(j > 0 && this[j - 1] > value)
{
this[j] = this[j - 1];
j--;
}
this[j] = value;
}
}
arr.insertionSort();
document.write(arr + "<br/>");
</script>
</body>
</html>
外層迴圈從第二個元素開始,把當前元素暫存到 value;內層 while 迴圈則不斷把前面比它大的元素往後挪,直到找到合適的位置,再把 value 放進去。整個過程中,j > 0 && this[j-1] > value 這個條件扮演關鍵角色,確保插入位置的正確性。程式會先印出亂數陣列,排序後再印一次,方便對照結果。