最新文章:

您的位置: 富录-前端开发|web技术博客 > JavaScript > 介绍8个入门级别的基础算法

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

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

    45c26b3ea68b13f3dccebd289ec42862.jpg

    线性搜索

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

    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 函数对其进行排序。排序后,将打印出排序后

二维码加载中...
本文作者:DGF      文章标题: 介绍8个入门级别的基础算法
本文地址: https://arbays.com/post-203.html     本文已被百度收录!
版权声明:若无注明,本文皆为“富录-前端开发|web技术博客”原创,转载请保留文章出处。
挤眼 亲亲 咆哮 开心 想想 可怜 糗大了 委屈 哈哈 小声点 右哼哼 左哼哼 疑问 坏笑 赚钱啦 悲伤 耍酷 勾引 厉害 握手 耶 嘻嘻 害羞 鼓掌 馋嘴 抓狂 抱抱 围观 威武 给力
提交评论

清空信息
关闭评论