算法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 实现常见算法和数据结构的基本方法。根据具体需求，可以进一步优化或扩展这些实现。
