DIV CSS 佈局教程網

JavaScript 基礎算法五例:查找、排序、階乘與奇偶輸出
編輯:關於JavaScript     

下面用五個小例子把最基礎的算法過一遍,每個都附完整可運行的 HTML 頁面,並在控制台打印循環次數,方便直觀對比不同算法的執行開銷。

一、線性查找

思路最樸素:從頭到尾逐個比較,命中即返回索引,循環結束仍未找到則返回提示。

<!doctype html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>線性查找</title>
</head>
<body>
<p>數組為:[2,4,6,23,53,545,65,3,24,5,3,6]</p>
<p>輸入要查的值:<input type="text" id="serch" onchange="search_index(this.value)"></p>
<p>這個值在數組的位置是:<span id="val"></span></p>
<script>
// Arr 為數組,x 為要搜索的值
function getX(Arr, x) {
    var count = 0;
    for (var i = 0; i < Arr.length; i++) {
        count++;
        console.log(count); // 輸出循環執行的次數
        if (Arr[i] == x) { return i; }
    }
    return "該值不存在";
}

function $$(id) { return document.getElementById(id); }
function search_index(value) {
    $$("val").innerHTML = getX(arr, value);
}

var arr = [2, 4, 6, 23, 53, 545, 65, 3, 24, 5, 3, 6];
</script>
</body>
</html>

線性查找的時間複雜度是 O(n),但它對數據沒有任何要求,這是唯一也是最重要的優勢。

二、二分查找

前提是數組已經有序。每次拿中間值比較,據結果把搜索範圍砍掉一半,因此效率是 O(log n)。

<!doctype html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>二分查找</title>
</head>
<body>
<script>
var arr = [-13, 2, 4, 6, 8, 12, 34, 35, 45, 56, 57, 88, 110, 234, 239, 342];

function binarySearch(arr, x) {
    var low = 0, high = arr.length - 1;
    var count = 0;
    while (low <= high) {
        count++;
        console.log("這是第 " + count + " 次循環");
        var mid = Math.floor((low + high) / 2);
        if (arr[mid] == x) {
            console.log("x 所在數組內的索引是: " + mid);
            return mid;
        }
        if (arr[mid] < x) {
            low = mid + 1;   // 目標在右半邊
            console.log("此時 low 的值是: " + low);
        } else {
            high = mid - 1;  // 目標在左半邊
            console.log("此時 high 的值是: " + high);
        }
    }
    return -1;
}

binarySearch(arr, 45);
</script>
</body>
</html>

16 個元素最多只需 4 次循環,把循環次數打印出來對比線性查找會非常直觀。

三、冒泡排序

相鄰兩兩比較,逆序就交換,每一輪結束後最大值會「浮」到末尾。

<!doctype html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>javascript 冒泡排序</title>
</head>
<body>
<script>
var arr = new Array(34, -3, 43, 67, 12, 44, 21, 34, 5, 645, 64, 3, 43, 23, 25);

function bubbleSort() {
    var temp;
    var count_outer = 0;
    var count_inner = 0;
    for (var i = 0; i < arr.length; i++) {
        count_outer++;
        console.log("這是外層循環的第 " + count_outer + " 次");
        for (var j = arr.length; j > 0; j--) {
            count_inner++;
            if (arr[j - 1] < arr[j - 2]) {
                temp = arr[j - 2];      // 暫存前一個值
                arr[j - 2] = arr[j - 1]; // 小的往前放
                arr[j - 1] = temp;      // 大的往後放
            }
            console.log("外層第 " + count_outer + " 次,內層第 " + count_inner + " 次後:" + arr);
        }
    }
    return "最終排序後的數組是: [" + arr + "],一共循環了 " + count_inner + " 次";
}

console.log(bubbleSort());
</script>
</body>
</html>

冒泡排序是 O(n²)。可以在外層加一個標志位,若某一輪沒有發生任何交換就提前退出——這是最容易想到、也最有效的一項優化,對接近有序的數據能顯著提速。

四、遞歸求階乘

<!doctype html>
<html>
<head>
<meta charset="UTF-8">
<title>階乘</title>
</head>
<body>
<script>
function factorial(num) {
    if (num <= 1) {
        return 1;
    } else {
        // arguments 是類數組對象,其 callee 指向所屬函數本身
        return num * arguments.callee(num - 1);
    }
}

var fac = factorial; // 不帶括號的函數名是指向該函數的指針
alert(fac(3));       // 6
</script>
</body>
</html>

這裡刻意用 arguments.callee 而不是直接寫函數名,好處是函數被賦值給其它變量後遞歸依然成立,降低了與名稱的耦合。代價是 arguments.callee 在嚴格模式下被禁用,現代寫法應改用具名函數表達式:

var factorial = function fact(num) {
    return num <= 1 ? 1 : num * fact(num - 1);
};

五、只輸出奇數或偶數

<html>
<head>
<title>只輸出奇數或者偶數項</title>
</head>
<body>
<script>
var ck = true; // 全局標志,用於交替跳過

function oddOreven(num) {
    // num 為 0 或 1,控制輸出偶數還是奇數
    for (var i = 0; i < 30; i++) {
        if (ck) {
            ck = false;
            alert(i + num);
        } else {
            ck = true;
        }
    }
}

oddOreven(0); // 偶數
// oddOreven(1); // 奇數
</script>
</body>
</html>

這個例子重點在於演示「用布爾標志控制隔次執行」。不過實戰中更直接的寫法是 if ((i + num) % 2 == 0) 或用 i += 2 跳步,語義更清楚,也不必依賴全局變量。

把這五個例子連起來看,其實覆蓋了算法學習最基礎的四塊:遍歷、雙指針收縮、雙層循環與交換、遞歸與狀態標志。理解每一塊的執行次數變化,比背下代碼更有價值。

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