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));

说明

在上面的代码片段中，quicksort函数接受一个数组作为输入，并递归地应用quicksort算法。它选择第一个元素作为枢轴，并创建两个子数组left和right，分别用于保存比枢轴小和大的元素。最后，它连接排序后的左数组、枢轴和排序后的右数组，以返回排序后的数组。

上述代码的输出将是[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函数接受一个数组作为输入，并递归地应用mergesort算法。它将数组分成两半，并使用mergesort递归地对它们进行排序。merge函数用于通过比较两个数组的元素并按升序将它们附加到合并后的数组中，将排序后的子数组合并在一起。排序好的左半部分和右半部分数组与任何剩余的元素连接起来。

上述代码的输出也将是[1, 2, 5, 7, 9]，表示mergesort算法成功地对输入数组进行了排序。

搜索算法

搜索算法用于在给定数据集中查找特定元素或条件。最有效的搜索算法之一是二分查找算法。让我们来探索它在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，分别表示子数组的起始和结束索引。然后进入一个循环，循环条件是start指针小于等于end指针。在每次迭代中，它计算中间索引mid，并将目标元素与子数组的中间元素进行比较。如果找到目标元素，则返回其索引。否则，根据目标元素与中间元素的大小调整start和end指针。

上述代码的输出将为3，表示目标元素7在数组[1, 2, 5, 7, 9]的索引为3处找到。

图遍历算法

图遍历算法用于探索或遍历图数据结构。它们可以用于解决各种问题，例如寻找最短路径或检测循环。其中两种常用的图遍历算法是广度优先搜索（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函数接受表示邻接表的图和一个起始顶点作为输入。它将起始顶点初始化为队列，将访问过的顶点存储在visited集合中。然后，它进入一个循环，直到队列为空。在每一次迭代中，它从队列中出列一个顶点，检查它是否已经访问过，如果没有，则将其标记为已访问并打印。然后，它将顶点的所有未访问邻居添加到队列中。

深度优先搜索（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');