我正在参加「掘金·启航计划」
摘要
本文将介绍如何使用JavaScript实现常见的算法和数据结构，包括排序、查找、链表、栈、队列等内容，帮助读者提高编程能力。
算法
排序算法
冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法，它的基本思想是对待排序序列从后往前扫描，每次比较相邻的两个元素，如果前面的元素比后面的元素大，则交换这两个元素的位置，直到序列被完全排序。
以下是使用 JavaScript 实现冒泡排序的示例代码：
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j+1] 的位置
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
这段代码定义了一个名为 bubbleSort 的函数，它接受一个数组作为参数，并返回一个已排序的数组。在函数内部，我们使用两个嵌套的循环来实现冒泡排序。外层循环控制排序的轮数，内层循环控制每轮排序中相邻元素的比较和交换。
具体来说，外层循环从第一个元素开始，到倒数第二个元素结束，因为最后一个元素已经排好序了。内层循环从第一个元素开始，到倒数第二个待排序元素结束，因为最后一个元素已经排好序了，并且我们不需要比较它和它后面的元素。在每轮排序中，如果相邻元素的顺序不正确，就交换它们的位置。经过多轮排序后，整个序列就被完全排序了。
以下是一个使用示例：
var arr = [3, 9, 1, 4, 7];
console.log("Before sorting:", arr); // [3, 9, 1, 4, 7]
arr = bubbleSort(arr);
console.log("After sorting:", arr); // [1, 3, 4, 7, 9]
在这个示例中，我们定义了一个待排序的数组 arr，并调用 bubbleSort 函数对其进行排序。最后，我们输出排序前后的数组内容，可以看到数组已经被正确地排序了。
快速排序
快速排序（Quick Sort）是一种常用的排序算法，它的基本思想是通过分治法（Divide and Conquer）将待排序序列划分为两个子序列，其中一个子序列的所有元素都小于等于基准值（pivot），另一个子序列的所有元素都大于等于基准值。然后对这两个子序列分别递归地进行快速排序，最终将整个序列排序完成。
以下是使用 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).concat(pivot, quickSort(right));
}
这段代码定义了一个名为 quickSort 的函数，它接受一个数组作为参数，并返回一个已排序的数组。在函数内部，我们首先判断待排序序列的长度是否为 0 或 1，如果是，则直接返回该序列。否则，我们选择第一个元素作为基准值，并将其他元素分为两个子序列，分别存储在 left 和 right 数组中。然后，我们递归地对这两个子序列进行快速排序，并将结果合并起来，最后返回排序后的数组。
插入排序
插入排序（Insertion Sort）是一种简单的排序算法，它的基本思想是将待排序序列分为已排序和未排序两个部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置，直到所有元素都被插入到已排序部分为止。
以下是使用 JavaScript 实现插入排序的示例代码：
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const temp = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
return arr;
}
这段代码定义了一个名为 insertionSort 的函数，它接受一个数组作为参数，并返回一个已排序的数组。在函数内部，我们使用两个嵌套的循环来实现插入排序。外层循环从第二个元素开始，到最后一个元素结束，因为第一个元素已经被默认为已排序部分。内层循环从当前元素的前一个元素开始，到已排序部分的最后一个元素结束，因为该元素之后的元素已经被排好序了。在内层循环中，我们将当前元素存储在 temp 变量中，然后将它插入到已排序部分的合适位置。具体来说，我们将已排序部分中比 temp 大的元素向右移动一个位置，然后插入 temp。最后，我们返回已排序的数组。
以下是一个使用示例：
const arr = [3, 5, 2, 1, 4];
console.log("Before sorting:", arr); // [3, 5, 2, 1, 4]
arr = insertionSort(arr);
console.log("After sorting:", arr); // [1, 2, 3, 4, 5]
在这个示例中，我们定义了一个待排序的数组 arr，并调用 insertionSort 函数对其进行排序。最后，我们输出排序前后的数组内容，可以看到数组已经被正确地排序了。
选择排序
选择排序（Selection Sort）是一种简单的排序算法，它的基本思想是每次从未排序部分选取最小（或最大）的元素，将其放在已排序部分的末尾，直到所有元素都被排序完成。
以下是使用 JavaScript 实现选择排序的示例代码：
function selectionSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
这段代码定义了一个名为 selectionSort 的函数，它接受一个数组作为参数，并返回一个已排序的数组。在函数内部，我们使用两个嵌套的循环来实现选择排序。外层循环从第一个元素开始，到倒数第二个元素结束，因为最后一个元素已经被默认为已排序部分。内层循环从当前元素的后一个元素开始，到最后一个元素结束，因为该元素之前的元素已经被排好序了。在内层循环中，我们维护一个 minIndex 变量来记录未排序部分中最小元素的下标。如果当前元素比 minIndex 对应的元素小，则更新 minIndex。最后，我们将当前元素和 minIndex 对应的元素交换位置。重复执行这个过程直到所有元素都被排序完成。
以下是一个使用示例：
const arr = [3, 5, 2, 1, 4];
console.log("Before sorting:", arr); // [3, 5, 2, 1, 4]
arr = selectionSort(arr);
console.log("After sorting:", arr); // [1, 2, 3, 4, 5]
在这个示例中，我们定义了一个待排序的数组 arr，并调用 selectionSort 函数对其进行排序。最后，我们输出排序前后的数组内容，可以看到数组已经被正确地排序了。
查找算法
二分查找
二分查找（Binary Search）是一种高效的查找有序数组中某个特定元素的算法。它的基本思想是将数组分成两部分，判断目标元素在哪一部分，然后继续在该部分进行查找，直到找到目标元素或者确定目标元素不存在为止。
以下是使用 JavaScript 实现二分查找的示例代码：
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;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
这段代码定义了一个名为 binarySearch 的函数，它接受两个参数：一个有序数组 arr 和一个目标元素 target。在函数内部，我们维护两个指针 left 和 right，分别指向数组的左边界和右边界。然后，我们使用一个 while 循环来进行二分查找。在每次循环中，我们计算中间位置 mid，并根据目标元素与 arr[mid] 的大小关系来更新左右指针。如果 arr[mid] 等于目标元素，则直接返回 mid。如果查找失败，则返回 -1。
以下是一个使用示例：
const arr = [1, 3, 5, 7, 9];
const target = 7;
const index = binarySearch(arr, target);
console.log(index); // 3，因为目标元素在数组的第 3 个位置（从 0 开始计数）
在这个示例中，我们定义了一个有序数组 arr 和一个目标元素 target。然后，我们调用 binarySearch 函数来查找目标元素在数组中的位置，并将结果存储在 index 变量中。最后，我们输出 index 的值，可以看到目标元素在数组中的位置是 3（从 0 开始计数）。
深度优先查找
深度优先查找（Depth-First Search，DFS）是一种用于遍历或搜索图形或树的算法，它从图中的某个顶点开始，沿着一条路径一直走到不能再走为止，然后返回到前一个顶点，继续沿着另一条路径搜索，直到遍历整个图形或树。
以下是使用 JavaScript 实现深度优先查找的示例代码：
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);
}
}
}
这段代码定义了一个名为 dfs 的函数，它接受三个参数：一个表示图的邻接表（adjacency list），一个表示起始顶点，以及一个表示已访问顶点的集合。在函数内部，我们首先将当前顶点标记为已访问，并输出它的值。然后，我们遍历与当前顶点相邻的未访问顶点，并对每个未访问顶点递归调用 dfs 函数。
以下是一个使用示例：
const graph = {
A: ['B', 'C'],
B: ['D', 'E'],
C: ['F'],
D: [],
E: ['F'],
F: []
};
dfs(graph, 'A'); // A B D E F C
在这个示例中，我们定义了一个表示图的邻接表 graph，其中每个顶点都是一个字符串，每个顶点的相邻顶点是一个数组。我们调用 dfs 函数，从起始顶点 A 开始遍历整个图形。最终输出的结果是 A B D E F C，表示从起始顶点开始遍历整个图形的路径。
图算法
广度优先搜索
广度优先搜索（Breadth-First Search，BFS）是一种用于遍历或搜索图形或树的算法，它从图中的某个顶点开始，逐层地遍历所有与它相邻的顶点，直到遍历整个图形或树。
以下是使用 JavaScript 实现广度优先搜索的示例代码：
function bfs(graph, start) {
const queue = [start]; // 用一个队列来存储待访问的顶点
const visited = new Set(); // 用一个集合来存储已访问的顶点
while (queue.length > 0) {
const vertex = queue.shift(); // 取出队列中的第一个顶点
if (!visited.has(vertex)) {
visited.add(vertex); // 标记该顶点为已访问
console.log(vertex); // 输出该顶点的值
// 将该顶点的所有未访问相邻顶点加入队列
for (const neighbor of graph[vertex]) {
if (!visited.has(neighbor)) {
queue.push(neighbor);
}
}
}
}
}
这段代码定义了一个名为 bfs 的函数，它接受两个参数：一个表示图的邻接表（adjacency list），一个表示起始顶点。在函数内部，我们首先用一个队列 queue 来存储待访问的顶点，用一个集合 visited 来存储已访问的顶点。然后，我们开始循环遍历队列中的每个顶点，如果该顶点未被访问过，就将它标记为已访问，并输出它的值。接着，我们将该顶点的所有未访问相邻顶点加入队列中，以便后续遍历。最终，当队列为空时，我们就完成了整个广度优先搜索的过程。
以下是一个使用示例：
const graph = {
A: ['B', 'C'],
B: ['D', 'E'],
C: ['F'],
D: [],
E: ['F'],
F: []
};
bfs(graph, 'A'); // A B C E F D
在这个示例中，我们定义了一个表示图的邻接表 graph，其中每个顶点都是一个字符串，每个顶点的相邻顶点是一个数组。我们调用 bfs 函数，从起始顶点 A 开始遍历整个图形。最终输出的结果是 A B C E F D，表示从起始顶点开始遍历整个图形的路径。
深度优先搜索
深度优先搜索（DFS，Depth-First Search），是一种搜索算法，用于遍历或搜索树或图的数据结构，其基本思路是从起点开始沿着一条路径一直走到底，若不可到达目标节点，则返回上一个节点，选择另一条路径进行搜索，直到找到目标节点或者搜索完整棵树为止。
以下是使用 JavaScript 实现深度优先搜索的示例代码：
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);
}
}
}
这段代码定义了一个名为 dfs 的函数，它接受三个参数：一个表示图的邻接表（adjacency list），一个表示起始顶点，以及一个表示已访问顶点的集合。在函数内部，我们首先将当前顶点标记为已访问，并输出它的值。然后，我们遍历与当前顶点相邻的未访问顶点，并对每个未访问顶点递归调用 dfs 函数。
深度优先搜索的基本思想是从图中的某个顶点开始，尽可能深地遍历图形，直到到达一个无法继续访问的顶点，然后返回到前一个顶点，继续遍历与该顶点相邻的未访问顶点。这个过程会一直持续到遍历整个图形或树。深度优先搜索使用递归的方式实现，可以避免使用队列等数据结构，代码更加简洁易懂。
以下是一个使用示例：
const graph = {
A: ['B', 'C'],
B: ['D', 'E'],
C: ['F'],
D: [],
E: ['F'],
F: []
};
dfs(graph, 'A'); // A B C E F D
在这个示例中，我们定义了一个表示图的邻接表 graph，其中每个顶点都是一个字符串，每个顶点的相邻顶点是一个数组。我们调用 dfs 函数，从起始顶点 A 开始遍历整个图形。最终输出的结果是 A B C E F D，表示从起始顶点开始遍历整个图形的路径。
