算法入門精講（一）：JavaScript 實現線性/二分查找、冒泡/選擇/插入排序、字符串反轉、單鏈表

算法入門精講（一）：JavaScript 實現經典查找、排序與鏈表操作

本文用 JavaScript 實現六大基礎算法與單鏈表數據結構，代碼簡潔、註釋詳細，適合前端工程師快速建立算法直覺。

一、線性查找 — O(n)

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

適用於無序、小規模數組；算法界的 Hello World。

二、二分查找 — O(log n)

function binarySearch(arr, target) {
    let low = 0, high = arr.length - 1;
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (arr[mid] === target) return mid;
        if (target < arr[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

前提：數組已按升序排列。每輪排除一半，極快。

三、冒泡排序 — O(n²)

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let sorted = true;
        for (let j = arr.length - 1; j > i; j--) { // 內層倒序，大元素「冒泡」到右側
            if (arr[j] < arr[j - 1]) {
                [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]; // ES6 解構交換
                sorted = false;
            }
        }
        if (sorted) break; // 本輪無交換，提前結束
    }
}

四、選擇排序 — O(n²)

function selectionSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let minIdx = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        if (minIdx !== i) [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
    return arr;
}

每輪選最小，交換次數最少（O(n)），但比較次數仍 O(n²)。

五、插入排序 — O(n²)

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        const x = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > x) {
            arr[j + 1] = arr[j]; // 向右移動
            j--;
        }
        if (j + 1 !== i) arr[j + 1] = x; // 插入空位
    }
    return arr;
}

類似整理撲克牌：假設左側有序，將當前牌插入合適位置。近似有序數組極快（O(n)）。

六、字符串反轉 — O(n)

function reverseString(str) {
    const arr = str.split('');
    let i = 0, j = arr.length - 1;
    while (i < j) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++; j--;
    }
    return arr.join('');
}

雙指針原地交換，空間 O(1)（不計輸出）。

七、排序穩定性結論

穩定**：相等元素相對順序不變。對多關鍵字排序至關重要。

八、單鏈表完整實現

// 節點類
class Node {
    constructor(val) {
        this.data = val;
        this.next = null;
    }
}

// 單鏈表類
class SinglyLinkedList {
    constructor() {
        this.head = new Node(null); // 哑節點，僅佔位
    }

    // 尾插
    insert(val) {
        let p = this.head;
        while (p.next) p = p.next;
        p.next = new Node(val);
    }

    // 刪除第 n 個節點（頭節點為第 0 位）
    removeAt(n) {
        if (n <= 0) return;
        const pre = this.getNodeByIndex(n - 1);
        if (pre.next) pre.next = pre.next.next;
    }

    // 獲取第 n 個節點
    getNodeByIndex(n) {
        let p = this.head, i = 0;
        while (p.next && i < n) { p = p.next; i++; }
        return p;
    }

    // 按值查找（返回首個匹配節點）
    getNodeByValue(val) {
        let p = this.head;
        while (p.next) {
            p = p.next;
            if (p.data === val) return p;
        }
        return null;
    }

    // 打印所有節點
    print() {
        let p = this.head, out = '';
        while (p.next) { p = p.next; out += p.data + ' '; }
        console.log(out.trim());
    }
}

// 測試
const list = new SinglyLinkedList();
['A','B','C','D'].forEach(v => list.insert(v));
list.print(); // A B C D

// 檢測重複元素
function hasDuplicate(list) {
    let i = list.head;
    while (i.next) {
        i = i.next;
        let j = i;
        while (j.next) {
            j = j.next;
            if (i.data === j.data) return true;
        }
    }
    return false;
}

// 鏈表反轉（借助數組）
function reverseList(list) {
    const arr = [];
    let p = list.head;
    while (p.next) { p = p.next; arr.push(p.data); }
    const newList = new SinglyLinkedList();
    for (let i = arr.length - 1; i >= 0; i--) newList.insert(arr[i]);
    return newList;
}

const reversed = reverseList(list);
reversed.print(); // D C B A

九、總結

• 查找：無序用線性，有序用二分。
• 排序：小數據/教學用 O(n²) 三兄弟；生產環境用內置 Array.sort()（V8 採用 Timsort，O(n log n) 穩定）。
• 鏈表：哑節點簡化邊界條件，雙指針/數組輔助實現反轉。