javascript算法實例分析

# JavaScript算法實例分析

## 引言
算法是計算機科學的核心，而JavaScript作為最流行的編程語言之一，其算法實現具有廣泛的應用場景。本文將通過多個實例分析JavaScript中常見的算法實現，包括排序、搜索、遞歸等經典算法，幫助開發者深入理解算法思想并掌握JavaScript實現技巧。

---

## 一、排序算法

### 1. 冒泡排序
**時間復雜度**：O(n2)  
**實現原理**：通過相鄰元素比較和交換，將最大元素逐步"冒泡"到數組末尾。

```javascript
function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // ES6解構交換
      }
    }
  }
  return arr;
}

2. 快速排序

時間復雜度：平均O(n log n)
分治思想：選取基準值，將數組分為左右兩部分遞歸排序。

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = [], right = [];
  
  for (let i = 1; i < arr.length; i++) {
    arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
  }
  
  return [...quickSort(left), pivot, ...quickSort(right)];
}

二、搜索算法

1. 二分查找

前提條件：有序數組
時間復雜度：O(log n)

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

2. 深度優先搜索(DFS)

應用場景：樹/圖的遍歷

function dfs(node) {
  if (!node) return;
  console.log(node.value); // 處理當前節點
  node.children.forEach(child => dfs(child));
}

三、遞歸與動態規劃

1. 斐波那契數列

遞歸實現（存在重復計算問題）：

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

動態規劃優化：

function fibDP(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

2. 爬樓梯問題

問題描述：每次可以爬1或2階，求n階樓梯的爬法總數。

function climbStairs(n) {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

四、實用算法技巧

1. 雙指針法

典型應用：兩數之和、反轉字符串

function reverseString(s) {
  let left = 0, right = s.length - 1;
  while (left < right) {
    [s[left], s[right]] = [s[right], s[left]];
    left++;
    right--;
  }
  return s;
}

2. 滑動窗口

適用場景：子串/子數組問題

function maxSubarray(arr, k) {
  let maxSum = 0, windowSum = 0;
  
  for (let i = 0; i < arr.length; i++) {
    windowSum += arr[i];
    if (i >= k - 1) {
      maxSum = Math.max(maxSum, windowSum);
      windowSum -= arr[i - (k - 1)];
    }
  }
  
  return maxSum;
}

五、算法優化策略

1. 空間換時間：使用哈希表（對象）存儲中間結果
2. 尾遞歸優化：避免調用棧溢出
3. 記憶化技術：緩存函數計算結果
4. 位運算：提升數值計算效率

// 記憶化示例
function memoize(fn) {
  const cache = {};
  return function(...args) {
    const key = JSON.stringify(args);
    return cache[key] || (cache[key] = fn.apply(this, args));
  };
}

結語

通過以上實例我們可以看到，JavaScript雖然是一種高級語言，但同樣能夠高效實現各類算法。掌握這些基礎算法不僅能提升編碼能力，更能培養解決問題的計算思維。建議讀者在理解原理后，自行實現并嘗試優化這些算法，這對技術成長大有裨益。

提示：實際開發中應根據場景選擇合適的算法，例如小數據量可用簡單排序，而大數據集應考慮歸并排序等高效算法。 “`

（全文約1250字，包含代碼示例和詳細說明）