DIV CSS 佈局教程網

JavaScript 演算法學習:直接插入排序實作
編輯:關於JavaScript     

直接插入排序是最直觀的排序演算法之一,非常適合作為演算法入門。以下先講清楚它的基本思想,再附上完整的 JavaScript 實作。

基本思想

假設待排序的記錄存放在陣列 R[1..n] 中。初始時,R[1] 自成一個有序區,無序區則為 R[2..n]。從 i=2 起直到 i=n,依序把 R[i] 插入到當前有序區 R[1..i-1] 的正確位置,逐步擴大有序區,最終生成含 n 個記錄的有序區。

打個比方,這就像我們整理撲克牌:手牌始終保持有序,每摸到一張新牌,就從右往左比對,找到合適的位置插入。

JavaScript 實作

<!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 這個條件扮演關鍵角色,確保插入位置的正確性。程式會先印出亂數陣列,排序後再印一次,方便對照結果。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved