JavaScript 算法:排序、搜索和图遍历
JavaScript 是一种广泛用于 Web 开发的多功能编程语言。虽然它以增强网页交互性的能力而闻名，但 JavaScript 还提供了用于排序、搜索和图遍历的强大算法。这些算法对于有效解决复杂问题至关重要。在本文中，我们将探索高级 JavaScript 算法，包括快速排序和合并排序等排序算法、二分搜索等搜索算法以及广度优先搜索和深度优先搜索等图遍历算法。
排序算法
排序算法在按特定顺序组织数据方面起着至关重要的作用。JavaScript 提供了几种高效的排序算法，其中两种是快速排序和合并排序。
让我们来看看每种算法及其在 JavaScript 中的实现 -
快速排序
快速排序是一种流行的分而治之排序算法。它的工作原理是选择一个枢轴元素，并将数组划分为两个子数组，一个子数组的元素小于枢轴，另一个子数组的元素大于枢轴。然后，该算法以递归方式应用于子数组。
示例
考虑下面显示的代码。
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)];
}
const arr = [5, 2, 9, 1, 7];
console.log(quicksort(arr));
解释
在上面的代码片段中，快速排序函数将数组作为输入，并递归应用快速排序算法。它选择第一个元素作为基准，并创建两个子数组，左和右，分别用于保存小于和大于基准的元素。最后，它将排序后的左数组、基准和排序后的右数组连接起来，返回排序后的数组。
上述代码的输出将是 [1, 2, 5, 7, 9]，这是输入数组 [5, 2, 9, 1, 7] 的排序版本。
归并排序
归并排序是另一种遵循分治方法的高效排序算法。它的工作原理是将数组分成更小的子数组，对它们进行排序，然后将它们合并在一起。
示例
考虑下面显示的代码。
function mergesort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = mergesort(arr.slice(0, mid));
const right = mergesort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const merged = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
merged.push(left[leftIndex]);
leftIndex++;
} else {
merged.push(right[rightIndex]);
rightIndex++;
}
}
return merged.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
const arr = [5, 2, 9, 1, 7];
console.log(mergesort(arr));
解释
mergesort 函数以数组为输入，并递归应用合并排序算法。它将数组分成两半，并使用合并排序对它们进行递归排序。merge 函数用于通过比较两个数组中的元素并将它们按升序附加到合并后的数组来将排序后的子数组合并在一起。排序后的左数组和右数组与任一数组中的任何剩余元素连接在一起。
上述代码的输出也将是 [1, 2, 5, 7, 9]，表示合并排序算法已成功对输入数组进行排序。
搜索算法
搜索算法用于在给定数据集中查找特定元素或条件。二分搜索算法是最有效的搜索算法之一。让我们探索它在 JavaScript 中的实现 -
二分查找
二分查找是一种分而治之算法，用于在排序数组中搜索特定元素。它反复将数组分成两半，并将目标元素与中间元素进行比较，以确定应该搜索左半部分还是右半部分。
示例
考虑下面显示的代码。
function binarySearch(arr, target) {
let start = 0;
let end = arr.length - 1;
while (start <= end) {
const mid = Math.floor((start + end) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
const arr = [1, 2, 5, 7, 9];
console.log(binarySearch(arr, 7));
解释
binarySearch 函数以已排序的数组 arr 和目标元素 target 作为输入。它初始化两个指针 start 和 end，分别表示子数组的起始和结束索引。然后，它进入一个循环，一直持续到起始指针小于或等于结束指针。在每次迭代中，它计算中间索引 mid，并将目标元素与子数组的中间元素进行比较。如果找到目标，则返回索引。否则，它会根据目标是否大于或小于中间元素来调整起始和结束指针。
上述代码的输出将为 3，表示在数组 [1, 2, 5, 7, 9] 中的索引 3 处找到了目标元素 7。
图遍历算法
图遍历算法用于探索或遍历图数据结构。它们可用于解决各种问题，例如查找最短路径或检测循环。两种常用的图遍历算法是广度优先搜索 (BFS) 和深度优先搜索 (DFS)。让我们来看看它们在 JavaScript 中的实现:
广度优先搜索 (BFS)
广度优先搜索是一种在移动到下一级之前探索同一级图的所有顶点的算法。它使用队列来跟踪接下来要访问的顶点。
示例
考虑下面显示的代码。
function bfs(graph, start) {
const queue = [start];
const visited = new Set();
while (queue.length > 0) {
const vertex = queue.shift();
if (!visited.has(vertex)) {
console.log(vertex);
visited.add(vertex);
for (const neighbor of graph[vertex]) {
queue.push(neighbor);
}
}
}
}
const graph = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'E'],
D: ['B'],
E: ['C']
};
console.log('BFS traversal:');
bfs(graph, 'A');
解释
bfs 函数以表示为邻接表的图和起始顶点作为输入。它使用起始顶点和已访问集初始化队列，以跟踪已访问的顶点。然后它进入一个循环，一直持续到队列为空。在每次迭代中，它从队列中出队一个顶点，检查它是否已被访问，如果没有，则将其标记为已访问并打印。然后它将顶点的所有未访问邻居添加到队列中。
深度优先搜索 (DFS)
深度优先搜索是一种算法，它在回溯之前尽可能地遍历每个分支，探索图的所有顶点。它使用堆栈或递归来跟踪下一个要访问的顶点。
示例
function dfs(graph, start, visited = new Set()) {
console.log(start);
visited.add(start);
for (const neighbor of graph[start]) {
if (!visited.has(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}
const graph = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'E'],
D: ['B'],
E: ['C']
};
console.log('DFS traversal:');
dfs(graph, 'A');
解释
dfs 函数以表示为邻接表的图、起始顶点和访问集(可选)作为输入。它打印当前顶点，将其标记为已访问，并递归地将 dfs 函数应用于其未访问的邻居。此过程持续进行，直到所有顶点都已被访问。
