介绍8个入门级别的基础算法

发布时间:2023年05月13日评论数：抢沙发阅读数： 1193

线性搜索

顺序搜索或线性搜索是最简单的搜索算法，它从列表或数组的开头开始逐个比较元素，直到找到目标值或搜索完整个列表。

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i; // 返回目标值在数组中的索引
    }
  }
  return -1; // 目标值不存在于数组中
}

// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const target = 7;
const result = linearSearch(arr, target);
if (result !== -1) {
  console.log("目标值 " + target + " 的索引为 " + result);
} else {
  console.log("目标值 " + target + " 不存在于数组中");
}

在上述代码中，linearSearch 函数接受一个数组 array 和目标值 target 作为参数。它通过遍历数组，逐个比较元素与目标值是否相等，如果找到目标值则返回其索引，否则返回 -1 表示目标值不存在于数组中。

在示例中，我们定义了一个数组 arr，目标值 target 设置为 7，然后调用 linearSearch 函数进行线性搜索。如果目标值存在于数组中，则打印目标值的索引；否则打印目标值不存在于数组中的消息。

请注意，线性搜索算法的时间复杂度为 O(n)，其中 n 是数组的长度。在最坏的情况下，需要遍历整个数组才能找到目标值或确定目标值不存在。

二分搜索

二分搜索是一种高效的搜索算法，适用于已排序的数组。它通过将目标值与数组的中间元素进行比较，然后根据比较结果在数组的前半部分或后半部分继续搜索，直到找到目标值或搜索范围缩小为空。

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (array[mid] === target) {
      return mid; // 返回目标值在数组中的索引
    } else if (array[mid] < target) {
      left = mid + 1; // 目标值在右半部分
    } else {
      right = mid - 1; // 目标值在左半部分
    }
  }

  return -1; // 目标值不存在于数组中
}

// 示例用法
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const target = 6;
const result = binarySearch(arr, target);
if (result !== -1) {
  console.log("目标值 " + target + " 的索引为 " + result);
} else {
  console.log("目标值 " + target + " 不存在于数组中");
}

在上述代码中，binarySearch 函数接受一个已排序的数组 array 和目标值 target 作为参数。使用两个指针 left 和 right 来表示搜索范围的左右边界。在每次迭代中，计算中间索引 mid 并将其与目标值进行比较。如果目标值等于中间元素，则返回其索引。如果目标值小于中间元素，则将搜索范围缩小到左半部分；如果目标值大于中间元素，则将搜索范围缩小到右半部分。通过不断缩小搜索范围，直到找到目标值或确定其不存在。

在示例中，我们定义了一个已排序的数组 arr，目标值 target 设置为 6，然后调用 binarySearch 函数进行二分搜索。如果目标值存在于数组中，则打印目标值的索引；否则打印目标值不存在于数组中的消息。

请注意，二分搜索的前提是数组已排序。二分搜索的时间复杂度为 O(log n)，其中 n 是数组的长度。由于每次迭代都将搜索范围减半，因此相对于线性搜索，二分搜索具有更高的效率。

冒泡排序

冒泡排序是一种简单的排序算法，它通过重复地交换相邻的元素，将较大（或较小）的元素逐渐移动到数组的一端，直到整个数组排序完成。

function bubbleSort(array) {
  const length = array.length;

  for (let i = 0; i < length - 1; i++) {
    for (let j = 0; j < length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        // 交换相邻的两个元素
        const temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }

  return array;
}

// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const sortedArr = bubbleSort(arr);
console.log("排序后的数组：", sortedArr);

在上述代码中，bubbleSort 函数接受一个数组 array 作为参数，然后使用冒泡排序算法对数组进行排序。冒泡排序的基本思想是通过相邻元素之间的比较和交换，将较大的元素逐步“冒泡”到数组的末尾。

在外层循环中，我们逐渐减小未排序部分的大小。在内层循环中，比较相邻的两个元素，如果它们的顺序不正确（升序排序时，前一个元素大于后一个元素），则进行交换。通过不断遍历和交换，较大的元素会逐渐移动到数组的末尾。

在示例中，我们定义了一个数组 arr，然后调用 bubbleSort 函数对其进行排序。排序后，将打印出排序后的数组。

冒泡排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。它是一种简单但效率较低的排序算法，在处理小型数据集或用于教学目的时比较常见。对于大型数据集，更高效的排序算法（如快速排序或归并排序）通常更为合适。

选择排序

选择排序也是一种简单的排序算法，它通过每次从未排序的部分选择最小（或最大）的元素，并将其放置在已排序部分的末尾，逐渐完成整个数组的排序。

function selectionSort(array) {
  const length = array.length;

  for (let i = 0; i < length - 1; i++) {
    let minIndex = i;

    // 在未排序部分中找到最小的元素索引
    for (let j = i + 1; j < length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }
    }

    // 将最小的元素与当前位置交换
    if (minIndex !== i) {
      const temp = array[i];
      array[i] = array[minIndex];
      array[minIndex] = temp;
    }
  }

  return array;
}

// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const sortedArr = selectionSort(arr);
console.log("排序后的数组：", sortedArr);

在上述代码中，selectionSort 函数接受一个数组 array 作为参数，并使用选择排序算法对数组进行排序。选择排序的基本思想是，在每次迭代中，从未排序部分中找到最小（或最大）的元素，然后将其放置在当前位置。

在外层循环中，我们逐渐增加已排序部分的大小。在内层循环中，我们通过遍历未排序部分，找到最小元素的索引。一旦找到最小元素的索引，我们将其与当前位置进行交换。

在示例中，我们定义了一个数组 arr，然后调用 selectionSort 函数对其进行排序。排序后，将打印出排序后的数组。

选择排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。虽然选择排序的性能通常较低，但它在某些情况下可能比其他排序算法更适合，例如在内存受限的环境下，由于选择排序每次只进行一次交换，所需的内存开销较小。然而，对于大型数据集，更高效的排序算法（如快速排序或归并排序）通常更为合适。

插入排序

插入排序是一种简单且高效的排序算法，它通过构建有序序列，对未排序的元素逐个插入到有序序列的适当位置，从而完成整个数组的排序。

function insertionSort(array) {
  const length = array.length;

  for (let i = 1; i < length; i++) {
    const key = array[i];
    let j = i - 1;

    // 将大于 key 的元素向右移动
    while (j >= 0 && array[j] > key) {
      array[j + 1] = array[j];
      j--;
    }

    // 将 key 插入到正确位置
    array[j + 1] = key;
  }

  return array;
}

// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const sortedArr = insertionSort(arr);
console.log("排序后的数组：", sortedArr);

在上述代码中，insertionSort 函数接受一个数组 array 作为参数，并使用插入排序算法对数组进行排序。插入排序的基本思想是，将数组划分为已排序部分和未排序部分，然后将未排序部分的元素逐个插入到已排序部分的正确位置。

在外层循环中，我们逐渐将未排序部分的元素插入到已排序部分。内层循环用于找到正确的插入位置。我们将当前元素标记为 key，然后将其与已排序部分的元素进行比较。如果已排序部分的元素大于 key，我们将这些元素向右移动，为 key 腾出插入的位置。

最终，我们将 key 插入到正确的位置，然后继续迭代下一个未排序元素，直到所有元素都被插入到已排序部分。

在示例中，我们定义了一个数组 arr，然后调用 insertionSort 函数对其进行排序。排序后，将打印出排序后的数组。

插入排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。尽管插入排序的性能相对较低，但在某些情况下，它可能比其他排序算法更适合，特别是对于较小的数组或已接近排序的部分有序的数组。

快速排序

快速排序是一种常用且高效的排序算法，它基于分治的思想，通过选择一个基准元素将数组划分为较小和较大的两个子数组，然后对子数组进行递归排序，最终实现整个数组的排序。

function quickSort(array) {
  if (array.length <= 1) {
    return array;
  }

  const pivot = array[Math.floor(array.length / 2)];
  const less = [];
  const equal = [];
  const greater = [];

  for (let element of array) {
    if (element < pivot) {
      less.push(element);
    } else if (element > pivot) {
      greater.push(element);
    } else {
      equal.push(element);
    }
  }

  return [...quickSort(less), ...equal, ...quickSort(greater)];
}

// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const sortedArr = quickSort(arr);
console.log("排序后的数组：", sortedArr);

在上述代码中，quickSort 函数接受一个数组 array 作为参数，并使用快速排序算法对数组进行排序。快速排序的基本思想是选择一个基准元素（通常为数组的中间元素），然后将数组分割为小于、等于和大于基准元素的三个子数组，接着对子数组进行递归排序，最后将它们合并起来。

在 quickSort 函数中，首先检查数组的长度，如果长度小于等于 1，则返回数组本身。否则，选择一个基准元素 pivot，并创建三个空数组 less、equal 和 greater 用于存放小于、等于和大于基准元素的元素。

然后，通过遍历数组中的元素，将它们分别放入对应的数组中。小于基准元素的元素放入 less 数组，大于基准元素的元素放入 greater 数组，等于基准元素的元素放入 equal 数组。

最后，通过递归调用 quickSort 函数对 less 和 greater 数组进行排序，并使用展开运算符 ... 将排序后的 less、equal 和 greater 数组合并起来，得到最终的排序结果。

在示例中，我们定义了一个数组 arr，然后调用 quickSort 函数对其进行排序。排序后，将打印出排序后的数组。

快速排序的平均时间复杂度为 O(n log n)，其中 n 是数组的长度。它是一种高效的排序算法，在大多数情况下具有较好的性能。

归并排序

归并排序是一种高效的排序算法，它采用分治策略，将数组递归地划分为较小的子数组，然后将子数组合并为一个有序的数组，从而完成整个数组的排序。

function mergeSort(array) {
  if (array.length <= 1) {
    return array;
  }

  const middle = Math.floor(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);

  return merge(mergeSort(left), mergeSort(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++;
    }
  }

  // 将剩余的元素添加到 merged 数组中
  while (leftIndex < left.length) {
    merged.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    merged.push(right[rightIndex]);
    rightIndex++;
  }

  return merged;
}

// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const sortedArr = mergeSort(arr);
console.log("排序后的数组：", sortedArr);

在上述代码中，mergeSort 函数接受一个数组 array 作为参数，并使用归并排序算法对数组进行排序。归并排序的基本思想是将数组分成较小的子数组，然后递归地将子数组排序，并将已排序的子数组合并以产生最终排序的结果。

在 mergeSort 函数中，首先检查数组的长度，如果长度小于等于 1，则返回数组本身。否则，找到数组的中间位置，并将数组分割为两个子数组 left 和 right。

然后，通过递归调用 mergeSort 函数对 left 和 right 子数组进行排序。递归调用会将子数组进一步细分，直到长度为 1，然后开始合并子数组。

merge 函数用于合并两个已排序的子数组。在 merge 函数中，我们使用两个指针 leftIndex 和 rightIndex 分别指向 left 和 right 子数组的起始位置。

通过比较指针所指位置的元素，我们将较小的元素添加到 merged 数组中，并将对应子数组的指针向后移动。当其中一个子数组的指针到达末尾时，我们将另一个子数组剩余的元素依次添加到 merged 数组中。

最后，我们返回合并后的 merged 数组作为结果。

在示例中，我们定义了一个数组 arr，然后调用 mergeSort 函数对其进行排序。排序后，将打印出排序后的数组。

归并排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。它是一种稳定的排序算法，在各种情况下都具有良好的性能。

堆排序

堆排序是一种基于二叉堆的排序算法，它利用堆的性质来实现排序。首先将待排序的元素构建成一个最大堆（或最小堆），然后反复从堆中取出最大（或最小）元素，将其放置在已排序部分的末尾，最终完成排序。

function heapSort(array) {
  buildMaxHeap(array);

  for (let i = array.length - 1; i > 0; i--) {
    swap(array, 0, i);
    heapify(array, 0, i);
  }

  return array;
}

function buildMaxHeap(array) {
  const length = array.length;
  const startIndex = Math.floor(length / 2) - 1;

  for (let i = startIndex; i >= 0; i--) {
    heapify(array, i, length);
  }
}

function heapify(array, index, heapSize) {
  const left = 2 * index + 1;
  const right = 2 * index + 2;
  let largest = index;

  if (left < heapSize && array[left] > array[largest]) {
    largest = left;
  }

  if (right < heapSize && array[right] > array[largest]) {
    largest = right;
  }

  if (largest !== index) {
    swap(array, index, largest);
    heapify(array, largest, heapSize);
  }
}

function swap(array, i, j) {
  const temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const sortedArr = heapSort(arr);
console.log("排序后的数组：", sortedArr);

在上述代码中，heapSort 函数接受一个数组 array 作为参数，并使用堆排序算法对数组进行排序。堆排序的基本思想是通过构建最大堆，将最大元素放置在堆顶，然后逐步减小堆的大小，重复此过程，直到所有元素都被排序。

在 heapSort 函数中，首先调用 buildMaxHeap 函数构建初始的最大堆。然后，从数组末尾开始，逐步将堆顶元素（最大值）与当前位置进行交换，然后通过调用 heapify 函数恢复堆的性质。

buildMaxHeap 函数用于构建最大堆。它从最后一个非叶子节点开始，依次调用 heapify 函数，使每个子树满足最大堆的性质。

heapify 函数用于调整堆的性质。给定一个节点索引 index 和堆的大小 heapSize，函数首先计算左子节点和右子节点的索引，然后找到最大的节点作为 largest。

如果 largest 不等于当前节点索引 index，则交换当前节点和 largest 节点的值，并递归调用 heapify 函数，继续向下调整以确保子树满足最大堆的性质。

最后，我们返回排序后的数组作为结果。

在示例中，我们定义了一个数组 arr，然后调用 heapSort 函数对其进行排序。排序后，将打印出排序后