JavaScript 算法实战全景

JavaScript 在算法实现上结合了高阶函数式编程与 V8 JIT 优化：

• 内置高效排序：Array.prototype.sort() 采用 TimSort 算法。
• 类型化数组与空间压缩：使用 Int32Array 实现动态规划状态转移的高性能内存加速。

---

📊 算法专题与复杂度

算法专题	典型问题 / 算法	核心思想	时间复杂度	空间复杂度
排序	Functional QuickSort / V8 TimSort	分治划分 / 自适应归并	$O(n \log n)$	$O(n)$
动态规划	0/1 背包问题	Int32Array 内存连续状态压缩转移	$O(N \cdot W)$	$O(W)$

---

1. 快速排序算法 (QuickSort)

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

console.log("=== JavaScript QuickSort & V8 TimSort ===");
const data = [64, 25, 12, 22, 11];
const sorted = quickSort(data);
console.assert(JSON.stringify(sorted) === JSON.stringify([11, 12, 22, 25, 64]), "Sort failed");
console.log("Sorted:", sorted);
console.log("JavaScript QuickSort tests passed successfully.");

🐳 Docker Verified📋node:22-alpine

Exit Code: 0

=== JavaScript QuickSort & V8 TimSort ===
Sorted: [ 11, 12, 22, 25, 64 ]
JavaScript QuickSort tests passed successfully.

---

2. 动态规划：0/1 背包问题

function knapsack01(W, weights, values) {
  const n = weights.length;
  const dp = new Int32Array(W + 1);

  for (let i = 0; i < n; i++) {
    for (let w = W; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[W];
}

console.log("=== JavaScript 0/1 Knapsack DP ===");
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const maxVal = knapsack01(5, weights, values);
console.assert(maxVal === 7, "Knapsack assertion failed");
console.log("Max Knapsack Value for W=5:", maxVal);
console.log("JavaScript Knapsack DP tests passed successfully.");

🐳 Docker Verified📋node:22-alpine

Exit Code: 0

=== JavaScript 0/1 Knapsack DP ===
Max Knapsack Value for W=5: 7
JavaScript Knapsack DP tests passed successfully.