算法的js实现
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++) {
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;
}斐波那契数列
递归与动态规划两种实现方式：
// 递归实现（时间复杂度 O(2^n)）
function fibRecursive(n) {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
// 动态规划实现（时间复杂度 O(n)）
function fibDP(n) {
let dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}深度优先搜索（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);
}
}
}链表反转
指针操作经典问题：
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}注意事项
- 递归算法需要注意调用栈溢出问题，可通过尾递归优化或改用迭代
- 排序算法在实际应用中建议使用内置的
Array.prototype.sort() - 算法复杂度分析应结合具体使用场景
- ES6+语法如展开运算符能简化部分算法实现
以上实现可作为学习参考，实际生产环境建议使用经过优化的算法库如 lodash 等。
