当前位置：首页 > JavaScript

算法js实现

2026-04-05 14:37:55JavaScript

在JavaScript中实现算法涉及多个方面，包括基础算法、数据结构操作、以及性能优化等。以下是一些常见算法的实现示例和关键点：

排序算法（快速排序）

快速排序通过分治策略实现高效排序，平均时间复杂度为O(n log n)。

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = [];
  const 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)];
}

搜索算法（二分查找）

二分查找要求数组已排序，时间复杂度为O(log n)。

function binarySearch(arr, target) {
  let left = 0;
  let 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;
}

动态规划（斐波那契数列）

使用备忘录优化递归实现的斐波那契数列，避免重复计算。

function fibonacci(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 2) return 1;
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

图算法（Dijkstra最短路径）

适用于加权图的单源最短路径算法，使用优先队列优化。

算法js实现

function dijkstra(graph, start) {
  const distances = {};
  const priorityQueue = new PriorityQueue();
  for (let vertex in graph) {
    distances[vertex] = vertex === start ? 0 : Infinity;
    priorityQueue.enqueue(vertex, distances[vertex]);
  }
  while (!priorityQueue.isEmpty()) {
    const current = priorityQueue.dequeue();
    for (let neighbor in graph[current]) {
      const distance = distances[current] + graph[current][neighbor];
      if (distance < distances[neighbor]) {
        distances[neighbor] = distance;
        priorityQueue.enqueue(neighbor, distance);
      }
    }
  }
  return distances;
}