Javascript常见算法详解

在JavaScript（JS）中，常见的算法涵盖了多个领域，从基础的数组操作到更复杂的排序、搜索和数据结构算法。下面是一些在JS中常见的算法示例：

1. 排序算法

Java排序算法-CSDN博客

• 冒泡排序（Bubble Sort）：通过重复遍历要排序的数列，比较每对相邻元素的值，若发现顺序错误则交换之。应用场景：冒泡排序由于其实现简单，适合小规模数据或基本有序的数据排序。

function bubbleSort(arr) {  const len = arr.length;  for (let i = 0; i < len - 1; 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;  
}  
const nums = [4, 5, 2, 7, 8];  
console.log(bubbleSort(nums)); // [2, 4, 5, 7, 8]

• 选择排序（Selection Sort）：在要排序的一组数中，选出最小（或最大）的一个数与第一个位置的数交换；然后在剩下的数当中再找最小（或最大）的与第二个位置的数交换，依此类推。应用场景：选择排序同样适合小规模数据的排序。

function selectionSort(arr) {  const len = arr.length;  for (let i = 0; i < len - 1; i++) {  let minIndex = i;  for (let j = i + 1; j < len; j++) {  if (arr[j] < arr[minIndex]) {  minIndex = j;  }  }  [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];  }  return arr;  
}  
const nums = [4, 5, 2, 7, 8];  
console.log(selectionSort(nums)); // [2, 4, 5, 7, 8]

• 插入排序（Insertion Sort）：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。小规模数据或基本有序的数据。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，找到排序位置后，需要将已排序元素逐步向后挪位，为新元素提供插入空间。

function insertionSort(arr) {  for (let i = 1; i < arr.length; i++) {  let key = arr[i]; // 当前需要插入的元素  let j = i - 1;  // 将大于key的元素向后移动一位  while (j >= 0 && arr[j] > key) {  arr[j + 1] = arr[j];  j = j - 1;  }  arr[j + 1] = key; // 插入key到正确的位置  }  return arr;  
}  // 示例  
const nums = [12, 11, 13, 5, 6];  
console.log(insertionSort(nums)); // 输出: [5, 6, 11, 12, 13]

• 归并排序（Merge Sort）：分治法的一个典型应用，将已有序的子序列合并，得到完全有序的序列。它将一个数组分成两半，对每半部分递归地应用归并排序，然后将排序好的两半合并成一个有序数组。归并排序的主要优点是稳定、效率高（平均和最坏时间复杂度均为O(n log n)），并且易于实现并行化。

function mergeSort(arr) {  if (arr.length < 2) {  // 基本情况：如果数组只有一个元素或为空，则直接返回该数组  return arr;  }  // 找到中间位置，将数组分成两部分  const middle = Math.floor(arr.length / 2);  const left = arr.slice(0, middle);  const right = arr.slice(middle);  // 递归地对左右两部分进行归并排序  return merge(mergeSort(left), mergeSort(right));  
}  function merge(left, right) {  let result = [], leftIndex = 0, rightIndex = 0;  // 当左右两部分都还有元素时，比较并合并  while (leftIndex < left.length && rightIndex < right.length) {  if (left[leftIndex] < right[rightIndex]) {  result.push(left[leftIndex]);  leftIndex++;  } else {  result.push(right[rightIndex]);  rightIndex++;  }  }  // 如果左部分还有剩余元素，则将它们添加到结果数组中  while (leftIndex < left.length) {  result.push(left[leftIndex]);  leftIndex++;  }  // 如果右部分还有剩余元素，则将它们添加到结果数组中  while (rightIndex < right.length) {  result.push(right[rightIndex]);  rightIndex++;  }  return result;  
}  // 示例  
const nums = [38, 27, 43, 3, 9, 82, 10];  
console.log(mergeSort(nums)); // 输出: [3, 9, 10, 27, 38, 43, 82]

• 快速排序（Quick Sort）：是一种高效的排序算法，采用分而治之的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。在JavaScript中，快速排序的实现通常涉及选择一个“基准”元素（pivot），然后将数组分成两个子数组：一个包含所有小于基准值的元素，另一个包含所有大于基准值的元素。最后，递归地对这两个子数组进行快速排序。
  。应用场景：快速排序适用于大规模数据的排序，平均时间复杂度为O(n log n)。

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 nums = [4, 5, 2, 7, 8];  
console.log(quickSort(nums)); // [2, 4, 5, 7, 8]

2. 搜索算法

• 线性搜索（Linear Search）：逐个检查每个元素，直到找到所需的特定元素为止。

function linearSearch(arr, target) {  for (let i = 0; i < arr.length; i++) {  if (arr[i] === target) {  // 找到目标值，返回其索引  return i;  }  }  // 未找到目标值，返回-1  return -1;  
}  // 示例  
const arr = [3, 5, 7, 9, 11, 13, 15];  
const target = 9;  
console.log(linearSearch(arr, target)); // 输出: 3  const missingTarget = 10;  
console.log(linearSearch(arr, missingTarget)); // 输出: -1

• 二分搜索（Binary Search）：在有序数组中查找某一特定元素的搜索算法，搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

function binarySearch(arr, target) {  let left = 0;  let right = arr.length - 1;  while (left <= right) {  let mid = Math.floor((left + right) / 2);  if (arr[mid] === target) {  // 找到目标值，返回其索引  return mid;  } else if (arr[mid] < target) {  // 目标值在中间值的右侧，调整左边界  left = mid + 1;  } else {  // 目标值在中间值的左侧，调整右边界  right = mid - 1;  }  }  // 未找到目标值，返回-1  return -1;  
}  // 示例  
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];  
const target = 7;  
console.log(binarySearch(arr, target)); // 输出: 3  const missingTarget = 10;  
console.log(binarySearch(arr, missingTarget)); // 输出: -1

3. 数组和字符串操作

• 反转数组：通过交换首尾元素的方式实现。

反转数组是一个基础且常见的算法问题，可以通过多种编程语言实现。在JavaScript中，我们已经知道有一个内置的reverse()方法可以直接用来反转数组，但如果你想要自己实现一个反转数组的算法，你可以通过交换数组的首尾元素，然后向中心移动，直到到达数组的中间位置。

下面是一个使用JavaScript实现的反转数组算法的例子：

function reverseArray(arr) {  let left = 0; // 左指针  let right = arr.length - 1; // 右指针  while (left < right) {  // 交换左右指针所指的元素  let temp = arr[left];  arr[left] = arr[right];  arr[right] = temp;  // 移动指针  left++;  right--;  }  // 由于是在原数组上进行操作，所以不需要返回新的数组  // 但为了演示，我们可以返回原数组或者null，表示操作已完成  return arr;  
}  // 示例  
let arr = [1, 2, 3, 4, 5];  
reverseArray(arr);  
console.log(arr); // 输出: [5, 4, 3, 2, 1]

这个算法的时间复杂度是O(n/2)，但通常我们将其简化为O(n)，因为n/2和n在算法分析中属于同一数量级。空间复杂度是O(1)，因为我们只是使用了常量级别的额外空间（几个变量）来执行操作，而没有使用与输入规模成比例的额外空间。

需要注意的是，这个算法直接修改了原数组。如果你不想修改原数组，你可以先复制一份数组，然后在复制的数组上进行反转操作。例如：

function reverseArrayWithoutMutating(arr) {  let copy = [...arr]; // 使用扩展运算符创建数组的一份浅拷贝  let left = 0;  let right = copy.length - 1;  while (left < right) {  let temp = copy[left];  copy[left] = copy[right];  copy[right] = temp;  left++;  right--;  }  return copy; // 返回反转后的新数组  
}  // 示例  
let arr = [1, 2, 3, 4, 5];  
let reversedArr = reverseArrayWithoutMutating(arr);  
console.log(reversedArr); // 输出: [5, 4, 3, 2, 1]  
console.log(arr); // 输出: [1, 2, 3, 4, 5]（原数组未改变）

• 字符串去重：使用Set或遍历字符串，利用对象记录字符出现情况，实现去重。

function uniqueCharsInOrder(str) {  // 创建一个 Set 对象，用于存储已经遇到的字符  let seen = new Set();  // 初始化一个空字符串，用于存放去重后的结果  let result = '';  // 遍历原字符串中的每个字符  for (let char of str) {  // 检查当前字符是否已经在 Set 中  if (!seen.has(char)) {  // 如果没有，则将其添加到 Set 中，并追加到结果字符串的末尾  seen.add(char);  result += char;  }  // 如果字符已经在 Set 中，则跳过它，不添加到结果字符串中  }  // 返回去重后且保持原始顺序的字符串  return result;  
}  // 示例  
console.log(uniqueCharsInOrder('hello world!')); // 输出: "helo wrd!"

• 子字符串搜索：使用indexOf或includes等方法。

indexOf() 方法

indexOf() 方法用于返回在父字符串中首次出现的子字符串的索引，如果没有找到则返回 -1。这个方法对于需要知道子字符串具体位置的场景非常有用。

let str = "Hello, world!";  
let index = str.indexOf("world");  
console.log(index); // 输出: 7  let fromIndex = 8;  
let notFoundIndex = str.indexOf("world", fromIndex);  
console.log(notFoundIndex); // 输出: -1，因为从索引8开始找不到"world"

includes() 方法

includes() 方法用于判断一个字符串是否包含在另一个字符串中，根据情况返回 true 或 false。这个方法对于只需要知道子字符串是否存在，而不需要知道其位置的场景很有用。

let str = "Hello, world!";  
let found = str.includes("world");  
console.log(found); // 输出: true  let notFound = str.includes("universe");  
console.log(notFound); // 输出: false  let fromPosition = 7;  
let foundAtPosition = str.includes("world", fromPosition);  
console.log(foundAtPosition); // 输出: true，即使起始位置是7，"world"依然从该位置开始  // 注意：如果fromIndex大于字符串长度，则includes方法返回false  
let fromIndexTooHigh = str.includes("world", 20);  
console.log(fromIndexTooHigh); // 输出: false

4. 动态规划

• 斐波那契数列：经典的动态规划问题，每个数是前两个数的和。

• 最长公共子序列（LCS）：寻找两个序列共有的最长子序列的问题。

5. 图论算法

• 深度优先搜索（DFS）：沿着树的深度遍历树的节点，尽可能深地搜索树的分支。

• 广度优先搜索（BFS）：从根节点开始，沿着树的宽度遍历树的节点。

6. 递归算法

递归算法在JS中非常常见，如计算阶乘、遍历文件目录等。

7. 数据结构相关算法

• 栈和队列的基本操作：如入栈（入队）、出栈（出队）、查看栈顶（队首）等。

• 链表操作：包括创建链表、添加节点、删除节点、反转链。表等