JavaScript 中一些常见算法的实现及详细解析

文章目录

• • @[TOC]
  • • 1. 排序算法
    • • (1) 冒泡排序（Bubble Sort）
      • (2) 快速排序（Quick Sort）
      • (3) 归并排序（Merge Sort）
    • 2. 查找算法
    • • (1) 线性查找（Linear Search）
      • (2) 二分查找（Binary Search）
    • 3. 图算法
    • • (1) 深度优先搜索（DFS）
      • (2) 广度优先搜索（BFS）
    • 4. 动态规划算法
    • • 背包问题（Knapsack Problem）

1. 排序算法

(1) 冒泡排序（Bubble Sort）

原理：
通过重复遍历数组，比较相邻元素并交换位置，使较大的元素逐渐“浮”到数组末尾。

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

---

(2) 快速排序（Quick Sort）

原理：
采用分治法。选择一个基准值，将数组分为小于、等于、大于基准的三部分，递归处理左右两部分。

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

---

(3) 归并排序（Merge Sort）

原理：
将数组一分为二，分别排序后合并两个有序数组。

function mergeSort(arr) {if (arr.length <= 1) return arr;function merge(left, right) {const result = [];let i = 0, j = 0;while (i < left.length && j < right.length) {result.push(left[i] < right[j] ? left[i++] : right[j++]);}return [...result, ...left.slice(i), ...right.slice(j)];}const mid = Math.floor(arr.length / 2);const left = mergeSort(arr.slice(0, mid));const right = mergeSort(arr.slice(mid));return merge(left, right);
}

---

2. 查找算法

(1) 线性查找（Linear Search）

原理：
逐个遍历数组元素，直到找到目标值或遍历结束。

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

---

(2) 二分查找（Binary Search）

原理：
适用于已排序数组。每次将搜索范围缩小一半，直到找到目标值或范围为空。

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;else if (arr[mid] < target) low = mid + 1;else high = mid - 1;}return -1;
}

---

3. 图算法

(1) 深度优先搜索（DFS）

原理：
从起点开始，沿着一条路径尽可能深入地探索图中的节点。

function dfs(graph, start, visited = new Set()) {visited.add(start);console.log(start);for (const neighbor of graph[start]) {if (!visited.has(neighbor)) {dfs(graph, neighbor, visited);}}
}

---

(2) 广度优先搜索（BFS）

原理：
按层遍历图，使用队列实现先进先出的访问顺序。

function bfs(graph, start) {const visited = new Set();const queue = [start];visited.add(start);while (queue.length > 0) {const node = queue.shift();console.log(node);for (const neighbor of graph[node]) {if (!visited.has(neighbor)) {visited.add(neighbor);queue.push(neighbor);}}}
}

---

4. 动态规划算法

背包问题（Knapsack Problem）

原理：
在容量限制下最大化物品总价值。使用二维 DP 数组 dp[i][w] 表示前 i 个物品、容量为 w 的最大价值。

function knapsack(weights, values, capacity) {const n = values.length;const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));for (let i = 1; i <= n; i++) {for (let w = 0; w <= capacity; w++) {if (weights[i - 1] <= w) {dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]],dp[i - 1][w]);} else {dp[i][w] = dp[i - 1][w];}}}return dp[n][capacity];
}