算法js实现

JavaScript 算法实现基础

JavaScript 作为一门灵活且强大的编程语言，能够实现各种常见算法。以下是一些基础算法的 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++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else 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;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

数据结构实现

链表

链表是一种线性数据结构，每个元素包含数据和指向下一个元素的指针。

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }
  append(val) {
    const newNode = new ListNode(val);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }
}

栈

栈是一种后进先出（LIFO）的数据结构。

class Stack {
  constructor() {
    this.items = [];
  }
  push(item) {
    this.items.push(item);
  }
  pop() {
    return this.items.pop();
  }
  peek() {
    return this.items[this.items.length - 1];
  }
  isEmpty() {
    return this.items.length === 0;
  }
}

动态规划

动态规划常用于解决优化问题，如斐波那契数列。

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];
}

图算法

广度优先搜索（BFS）用于遍历或搜索图数据结构。

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

实用算法技巧

递归与迭代

递归阶乘实现：

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

迭代阶乘实现：

function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

这些示例展示了 JavaScript 实现常见算法和数据结构的基本方法。根据具体需求，可以进一步优化或扩展这些实现。