前言
在前端开发中，算法虽然不像后端那样频繁使用，，但在处理数据、优化性能等方面帮助我们解决很多问题，比如排序、查找、计算等等。算法的学习可以帮助我们提高自己的思维能力，也可以帮助我们更好地理解计算机的工作原理。
以下是一些常见的前端算法方法及其使用例子
排序算法
排序算法在前端中常用于对数据进行排序，如表格排序、搜索结果排序等。
冒泡排序
冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素，如果它们的顺序错误就交换它们，直到没有任何一对数字需要交换。
1
2
3
4
5
6
7
8
9
10
11
| function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
|
快速排序
快速排序是一种分治算法，它将一个数组分成两个子数组，然后递归地对子数组进行排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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)];
}
|
搜索算法
搜索算法在前端中常用于查找数据，如搜索框、下拉框等。
线性搜索
线性搜索是一种简单的搜索算法，它遍历数组，查找与目标值相等的元素。
1
2
3
4
5
6
| function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
|
二分搜索（要求数组已排序）
二分搜索是一种高效的搜索算法，它将数组分成两半，查找与目标值相等的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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;
}
|
递归算法
递归算法在前端中常用于处理树形结构、递归调用等。
阶乘计算
1
2
3
4
| function factorial(n) {
if (n === 0 || n === 1) return 1;
return n * factorial(n - 1);
}
|
遍历树形结构
遍历树形结构是一种常见的递归算法，它可以遍历一个树形结构，对每个节点进行处理。
1
2
3
4
5
6
| function traverseTree(node) {
if (node === null) return;
console.log(node.value);
traverseTree(node.left);
traverseTree(node.right);
}
|
动态规划
动态规划是一种将复杂问题分解成简单子问题的算法，它可以将一个问题分解成多个子问题，然后将子问题的解组合起来得到原问题的解。
斐波那契数列
斐波那契数列是一个经典的动态规划问题，它的定义是：第n个数等于前两个数之和。
1
2
3
4
5
6
| 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];
}
|
最大子序列和
最大子序列和是一个经典的动态规划问题，它的定义是：找到一个数组中连续子序列的最大和。
1
2
3
4
5
6
7
8
9
| function maxSubArray(arr) {
let maxSum = arr[0];
let currentSum = arr[0];
for (let i = 1; i < arr.length; i++) {
currentSum = Math.max(arr[i], currentSum + arr[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
|
贪心算法
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。
背包问题
背包问题是一个经典的贪心算法问题，它的定义是：给定一个容量为W的背包和n个物品，每个物品有一个重量和一个价值，如何选择物品放入背包，使得背包中的物品总价值最大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function knapsack(items, capacity) {
items.sort((a, b) => b.value / b.weight - a.value / a.weight);
let totalValue = 0;
let totalWeight = 0;
for (let i = 0; i < items.length; i++) {
if (totalWeight + items[i].weight <= capacity) {
totalValue += items[i].value;
totalWeight += items[i].weight;
} else {
const remainingWeight = capacity - totalWeight;
totalValue += items[i].value * remainingWeight / items[i].weight;
break;
}
}
return totalValue;
}
|
分治算法
分治算法是一种将一个问题分解成多个子问题，然后将子问题的解组合起来得到原问题的解的算法。
归并排序
归并排序是一种分治算法，它将一个数组分成两个子数组，然后递归地对子数组进行排序，最后将两个有序的子数组合并成一个有序的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
const result = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return [...result, ...left, ...right];
}
|
回溯算法
回溯算法常用于解决组合、排列、子集等问题。
全排列
全排列是一种回溯算法，它将一个数组中的所有元素进行全排列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| function permute(arr) {
const result = [];
const backtrack = (path) => {
if (path.length === arr.length) {
result.push(path.slice());
return;
}
for (let i = 0; i < arr.length; i++) {
if (path.includes(arr[i])) continue;
path.push(arr[i]);
backtrack(path);
path.pop();
}
};
backtrack([]);
return result;
}
|
双指针算法
双指针算法是一种在数组中使用两个指针来解决问题的算法。
两数之和 （有序数组）
两数之和是一个经典的双指针算法问题，它的定义是：给定一个有序数组和一个目标值，找到数组中两个数的和等于目标值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function twoSum(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) return [left, right];
if (sum < target) {
left++;
} else {
right--;
}
}
return [];
}
|
哈希表与映射
哈希表和映射是两种常用的数据结构，它们可以用来存储键值对，并且可以快速地查找、插入、删除键值对。
两数之和（无序数组）
两数之和是一个经典的哈希表问题，它的定义是：给定一个数组和一个目标值，找到数组中两个数的和等于目标值。
1
2
3
4
5
6
7
8
9
10
11
| function twoSum(arr, target) {
const map = new Map();
for (let i = 0; i < arr.length; i++) {
const complement = target - arr[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(arr[i], i);
}
return [];
}
|
