前端常用算法解析：Bubble Sort，Quick Sort，Merge Sort，Binary Search，DFS，BFS，DP，Dijkstra，Union-Find
目录
一、算法在前端开发中的重要性
算法在前端开发中不仅仅用于面试，更重要的是解决实际问题：优化性能、处理复杂数据、提升用户体验等。
二、常用算法解析
2.1. 排序算法（Bubble Sort，Quick Sort，Merge Sort）
使用场景：
需要原地排序大量数据时，如表格排序、搜索结果排序
代码示例：
// ==================== 1. 冒泡排序 ====================constbubbleSort=(arr)=>{if(!Array.isArray(arr)|| arr.length <=1)return arr;const n = arr.length;let lastSwapIndex = n -1;for(let i =0; i < n -1; i++){let isSorted =true;let currentSwapIndex =0;// 只比较到上次最后交换的位置for(let j =0; j < lastSwapIndex; j++){if(arr[j]> arr[j +1]){// 使用ES6解构赋值交换[arr[j], arr[j +1]]=[arr[j +1], arr[j]]; isSorted =false; currentSwapIndex = j;}}// 更新最后交换位置 lastSwapIndex = currentSwapIndex;// 如果已经有序，提前结束if(isSorted)break;}return arr;};// ==================== 2. 快速排序 ====================functionquickSort(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++){if(arr[i]< pivot){ left.push(arr[i]);}else{ right.push(arr[i]);}}return[...quickSort(left), pivot,...quickSort(right)];}// 优化版（原地排序）functionquickSortInPlace(arr, left =0, right = arr.length -1){if(left >= right)return;const pivotIndex =partition(arr, left, right);quickSortInPlace(arr, left, pivotIndex -1);quickSortInPlace(arr, pivotIndex +1, right);return arr;}functionpartition(arr, left, right){const pivot = arr[right];let i = left;for(let j = left; j < right; j++){if(arr[j]< pivot){[arr[i], arr[j]]=[arr[j], arr[i]]; i++;}}[arr[i], arr[right]]=[arr[right], arr[i]];return i;}// 使用示例const data =[64,34,25,12,22,11,90]; console.log(quickSort(data));// [11, 12, 22, 25, 34, 64, 90]// ==================== 3. 归并排序 ====================constmergeSort=(arr)=>{if(!Array.isArray(arr)|| arr.length <=1)return arr;// 自底向上的归并排序，迭代版本const n = arr.length;const temp =newArray(n);// 外层循环控制子数组大小for(let size =1; size < n; size *=2){// 内层循环遍历所有子数组for(let left =0; left < n - size; left +=2* size){const mid = left + size -1;const right = Math.min(left +2* size -1, n -1);// 优化：如果已经有序，跳过合并if(arr[mid]<= arr[mid +1])continue;merge(arr, temp, left, mid, right);}}return arr;};// 归并排序辅助函数：合并两个有序数组constmerge=(arr, temp, left, mid, right)=>{let i = left;let j = mid +1;let k = left;// 复制到临时数组for(let m = left; m <= right; m++){ temp[m]= arr[m];}// 合并while(i <= mid && j <= right){ arr[k++]= temp[i]<= temp[j]? temp[i++]: temp[j++];}// 复制剩余元素while(i <= mid){ arr[k++]= temp[i++];}// 右侧剩余元素已经在正确位置，无需复制};2.2 二分查找（Binary Search）
使用场景：
有序数组查找、搜索建议、分页查询优化
代码示例：
functionbinarySearch(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;}elseif(arr[mid]< target){ left = mid +1;}else{ right = mid -1;}}return-1;}// 查找第一个大于等于目标值的位置functionbinarySearchLowerBound(arr, target){let left =0;let right = arr.length -1;let result =-1;while(left <= right){const mid = Math.floor((left + right)/2);if(arr[mid]>= target){ result = mid; right = mid -1;}else{ left = mid +1;}}return result;}// 使用示例const sortedArray =[1,3,5,7,9,11,13,15]; console.log(binarySearch(sortedArray,7));// 3 console.log(binarySearchLowerBound(sortedArray,8));// 4逻辑分析：
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
- 每次比较将搜索范围减半，适用于有序数据集
2.3 深度优先搜索（DFS）
使用场景：
DOM遍历、文件目录遍历、解决回溯问题
代码示例：
// 二叉树遍历classTreeNode{constructor(val){this.val = val;this.left =null;this.right =null;}}// 递归DFSfunctiondfsRecursive(root, result =[]){if(!root)return result;// 前序遍历 result.push(root.val);dfsRecursive(root.left, result);dfsRecursive(root.right, result);return result;}// 迭代DFS（使用栈）functiondfsIterative(root){if(!root)return[];const stack =[root];const result =[];while(stack.length >0){const node = stack.pop(); result.push(node.val);// 先右后左，保证左子树先被访问if(node.right) stack.push(node.right);if(node.left) stack.push(node.left);}return result;}// 文件夹结构遍历示例functiontraverseDirectory(dir, callback, depth =0){callback(dir, depth);if(dir.children){for(const child of dir.children){traverseDirectory(child, callback, depth +1);}}}// 使用示例const tree =newTreeNode(1); tree.left =newTreeNode(2); tree.right =newTreeNode(3); tree.left.left =newTreeNode(4); tree.left.right =newTreeNode(5); console.log(dfsRecursive(tree));// [1, 2, 4, 5, 3] console.log(dfsIterative(tree));// [1, 2, 4, 5, 3]2.4 广度优先搜索（BFS）
使用场景：
最短路径问题、层级遍历、社交网络关系
代码示例：
// 二叉树层级遍历functionlevelOrder(root){if(!root)return[];const queue =[root];const result =[];while(queue.length >0){const levelSize = queue.length;const currentLevel =[];for(let i =0; i < levelSize; i++){const node = queue.shift(); currentLevel.push(node.val);if(node.left) queue.push(node.left);if(node.right) queue.push(node.right);} result.push(currentLevel);}return result;}// 最短路径（无权图）functionshortestPath(graph, start, end){const queue =[[start]];const visited =newSet([start]);while(queue.length >0){const path = queue.shift();const node = path[path.length -1];if(node === end){return path;}for(const neighbor of graph[node]||[]){if(!visited.has(neighbor)){ visited.add(neighbor); queue.push([...path, neighbor]);}}}returnnull;// 没有路径}// 使用示例const graph ={A:['B','C'],B:['A','D','E'],C:['A','F'],D:['B'],E:['B','F'],F:['C','E']}; console.log(shortestPath(graph,'A','F'));// ['A', 'C', 'F']2.5 动态规划（DP）
使用场景：
优化问题、最长公共子序列、编辑距离、背包问题
代码示例：
// 斐波那契数列（记忆化）functionfibonacci(n, memo ={}){if(n <=1)return n;if(memo[n])return memo[n]; memo[n]=fibonacci(n -1, memo)+fibonacci(n -2, memo);return memo[n];}// 最长递增子序列functionlengthOfLIS(nums){if(nums.length ===0)return0;const dp =newArray(nums.length).fill(1);let maxLen =1;for(let i =1; i < nums.length; i++){for(let j =0; j < i; j++){if(nums[i]> nums[j]){ dp[i]= Math.max(dp[i], dp[j]+1);}} maxLen = Math.max(maxLen, dp[i]);}return maxLen;}// 背包问题（0/1背包）functionknapSack(weights, values, capacity){const n = weights.length;const dp =Array(n +1).fill().map(()=>Array(capacity +1).fill(0));for(let i =1; i <= n; i++){for(let w =1; w <= capacity; w++){if(weights[i -1]<= w){ dp[i][w]= Math.max( dp[i -1][w], dp[i -1][w - weights[i -1]]+ values[i -1]);}else{ dp[i][w]= dp[i -1][w];}}}return dp[n][capacity];}// 使用示例 console.log(fibonacci(10));// 55 console.log(lengthOfLIS([10,9,2,5,3,7,101,18]));// 4 console.log(knapSack([2,3,4,5],[3,4,5,6],8));// 102.6 Dijkstra算法
使用场景：
最短路径（带权重）、地图导航、网络路由
代码示例：
classPriorityQueue{constructor(comparator=(a, b)=> a < b){this.heap =[];this.comparator = comparator;}enqueue(item){this.heap.push(item);this.heapifyUp(this.heap.length -1);}dequeue(){if(this.size()===0)returnnull;if(this.size()===1)returnthis.heap.pop();const item =this.heap[0];this.heap[0]=this.heap.pop();this.heapifyDown(0);return item;}heapifyUp(index){while(index >0){const parent = Math.floor((index -1)/2);if(this.comparator(this.heap[index],this.heap[parent])){[this.heap[index],this.heap[parent]]=[this.heap[parent],this.heap[index]]; index = parent;}else{break;}}}heapifyDown(index){const left =2* index +1;const right =2* index +2;let smallest = index;if(left <this.heap.length &&this.comparator(this.heap[left],this.heap[smallest])){ smallest = left;}if(right <this.heap.length &&this.comparator(this.heap[right],this.heap[smallest])){ smallest = right;}if(smallest !== index){[this.heap[index],this.heap[smallest]]=[this.heap[smallest],this.heap[index]];this.heapifyDown(smallest);}}isEmpty(){returnthis.heap.length ===0;}size(){returnthis.heap.length;}}functiondijkstra(graph, start, end){// 初始化距离表const distances ={};const previous ={};const nodes =newPriorityQueue((a, b)=> a.distance < b.distance);// 设置初始距离for(const vertex in graph){if(vertex === start){ distances[vertex]=0; nodes.enqueue({vertex: start,distance:0});}else{ distances[vertex]=Infinity;} previous[vertex]=null;}// 主循环while(!nodes.isEmpty()){const{vertex: current }= nodes.dequeue();// 找到终点，提前结束if(current === end)break;// 遍历邻居for(const neighbor in graph[current]){const weight = graph[current][neighbor];const distance = distances[current]+ weight;if(distance < distances[neighbor]){ distances[neighbor]= distance; previous[neighbor]= current; nodes.enqueue({vertex: neighbor, distance });}}}// 重建路径const path =[];let current = end;while(current !==null){ path.unshift(current); current = previous[current];}return{distance: distances[end],path: path };}// 使用示例：地图导航const cityMap ={'A':{'B':4,'C':2},'B':{'A':4,'C':1,'D':5},'C':{'A':2,'B':1,'D':8,'E':10},'D':{'B':5,'C':8,'E':2,'F':6},'E':{'C':10,'D':2,'F':3},'F':{'D':6,'E':3}};const result =dijkstra(cityMap,'A','F'); console.log('最短距离:', result.distance);// 11 console.log('最短路径:', result.path);// ['A', 'C', 'B', 'D', 'E', 'F']逻辑分析：
- 时间复杂度：O((V+E) log V)，使用优先队列优化
- 空间复杂度：O(V)
- 贪心算法，每次选择当前距离最小的节点
2.7 并查集（Union-Find）
使用场景：
连通性问题、朋友圈、最小生成树（Kruskal算法）
代码示例：
classUnionFind{constructor(size){this.parent =newArray(size);this.rank =newArray(size);this.count = size;for(let i =0; i < size; i++){this.parent[i]= i;this.rank[i]=1;}}find(x){// 路径压缩if(this.parent[x]!== x){this.parent[x]=this.find(this.parent[x]);}returnthis.parent[x];}union(x, y){const rootX =this.find(x);const rootY =this.find(y);if(rootX === rootY)returnfalse;// 按秩合并if(this.rank[rootX]>this.rank[rootY]){this.parent[rootY]= rootX;}elseif(this.rank[rootX]<this.rank[rootY]){this.parent[rootX]= rootY;}else{this.parent[rootY]= rootX;this.rank[rootX]++;}this.count--;returntrue;}connected(x, y){returnthis.find(x)===this.find(y);}getCount(){returnthis.count;}}// Kruskal最小生成树算法functionkruskalMST(n, edges){// 按权重排序 edges.sort((a, b)=> a[2]- b[2]);const uf =newUnionFind(n);const mst =[];let totalWeight =0;for(const[u, v, weight]of edges){if(uf.union(u, v)){ mst.push([u, v, weight]); totalWeight += weight;if(mst.length === n -1)break;}}return{ mst, totalWeight };}// 使用示例：社交网络朋友圈classFriendCircle{constructor(size){this.uf =newUnionFind(size);this.friendCount =newArray(size).fill(1);}makeFriendship(a, b){const rootA =this.uf.find(a);const rootB =this.uf.find(b);if(rootA === rootB)returnthis.friendCount[rootA];// 合并朋友圈，更新人数this.uf.union(a, b);const newRoot =this.uf.find(a);this.friendCount[newRoot]=this.friendCount[rootA]+this.friendCount[rootB];returnthis.friendCount[newRoot];}areFriends(a, b){returnthis.uf.connected(a, b);}getCircleSize(person){const root =this.uf.find(person);returnthis.friendCount[root];}}// 使用示例const edges =[[0,1,4],[0,7,8],[1,2,8],[1,7,11],[2,3,7],[2,5,4],[2,8,2],[3,4,9],[3,5,14],[4,5,10],[5,6,2],[6,7,1],[6,8,6],[7,8,7]];const result =kruskalMST(9, edges); console.log('最小生成树:', result.mst); console.log('总权重:', result.totalWeight);const socialNetwork =newFriendCircle(5); socialNetwork.makeFriendship(0,1); socialNetwork.makeFriendship(2,3); socialNetwork.makeFriendship(0,3); console.log(socialNetwork.getCircleSize(0));// 4三、总结
- 掌握基础算法：排序、搜索、递归是基础
- 理解应用场景：算法是工具，解决问题是关键
- 关注实际性能：理论复杂度重要，但实际测试更重要
- 保持代码可读性：复杂的算法要添加注释
- 利用现代API：如Set、Map、Web Workers等
- 持续学习：算法在前端应用不断演进
前端工程师不需要成为算法专家，但掌握常用算法能显著提升解决问题的能力。将算法思维融入日常开发，写出更高效、健壮的代码。
