在JavaScript中实现插入排序算法

作者 : IT 大叔 本文共2108个字,预计阅读时间需要6分钟 发布时间: 2020-10-15

在计算机科学中,很少有工具像搜索算法那样经常使用。程序员和工程师每天都依靠它们筛选数据,并且几乎以一种或另一种方式将它们构建到几乎每种现代编程语言中。

尽管使用语言的内置搜索功能可以完成大多数日常工作,但重要的是要了解幕后工作情况,不同的搜索算法实际上在做什么以及为什么它们按照自己的方式工作。尽管它可能不会经常出现,但总是有机会要求您在技术面试环境中实施或解释搜索算法,这正是本文为您准备的内容!

今天,我们将研究计算机科学中基本的搜索算法之一“插入排序

什么是插入排序?

如该算法的Wikipedia页面所述:

插入排序是一种简单的排序算法,可以一次构建一个最终的排序数组(或列表)。...插入排序迭代,每次重复消耗一个输入元素,并增加一个排序的输出列表。在每次迭代时,插入排序都会从输入数据中删除一个元素,在排序列表中找到它所属的位置,然后将其插入那里。重复直到没有输入元素剩余为止。

通常通过迭代数组,增加数组后面的排序列表来就地进行排序。在每个数组位置,它会对照已排序列表中的最大值(在检查的前一个数组位置恰好在它旁边)检查那里的值。如果较大,它将元素留在原处并移至下一个。如果较小,它将在排序列表中找到正确的位置,将所有较大的值上移以形成一个空格,然后插入该正确的位置。

这听起来可能有点令人困惑,但是以下是该算法将如何处理数据的有用图表:

在JavaScript中实现插入排序算法插图

当我们遍历整数数组时,每个值将一次与之前的整数进行比较,并与每个交换位置,直到最终插入到正确的位置。

在处理数据时,我们将获得两个子数组,左侧是已排序的,右侧是未排序的。

有效率吗?

不幸的是,插入排序在大型数据集中的效率不如快速排序,堆排序或合并排序等效率更高的算法,尽管它确实具有某些优势。

  • 易于编程实现。
  • 对于小型数据集有效。
  • 对于已经大部分排序的数据集,自适应有效。
  • 就地运行,仅占用恒定的O(1)空间。

插入排序的最坏情况和平均情况下的时间复杂度均为O(n2)(二次)。

我们如何实施呢?

现在,我们进入了很好的阶段!

由于我们正在JavaScript中实现插入排序,因此我们将使用现代ES6 +语法来处理数组中的交换元素,这将有助于保持我们需要写下的代码行数。

最终的算法如下所示:

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i;
    while (j > 0 && array[j] < array[j - 1]) {
      [array[j - 1], array[j]] = [array[j], array[j - 1]];
      j--;
    }
  }
return array;
}

现在,让我们一步一步地分解它。


首先,让我们声明我们的函数,它的返回值(修改后的数组)以及将要执行所有逻辑的main for循环:

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {

  }
return array;
}

我们将其写为一个非常可预测的for循环,该循环仅遍历整个数组。区别在于我们将从索引1开始,而不是通常的0。这是因为我们总是将每个元素至少与它之前的元素进行比较,以查看是否需要进行交换。由于第0个元素没有前一个要比较的元素,因此我们跳过该元素并从1开始。

接下来,我们为遍历数组j建立第二个指针:

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i;
  }
return array;
}

指针j被设置为i的值,因为当我们穿越我们的for循环中,我们也将实现第二个通过阵列循环一会儿横穿落后于它的已排序子阵列中比较每个值。

该while循环以及我们算法的最后一步如下所示:

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i;
    while (j > 0 && array[j] < array[j - 1]) {
      [array[j - 1], array[j]] = [array[j], array[j - 1]];
      j--;
    }
  }
return array;
}

这是很多新代码,所以让我们研究一下它的所有三行代码。

  1. 我们实现了while循环,当j大于0(表示尚未到达数组的开头)并且array [j]的值小于array [j-1]时将触发。这两个条件将允许循环从数组一直向下遍历,交换值,直到将起始元素插入其适当位置(该元素之前的值较小)。
  2. 我们使用JavaScript ES6语法将每个元素与其之前的元素交换,将起始元素一次向下移动到数组中。
  3. 我们减小j的值,以便在下一个循环中,我们仍在交换与下一次开始时相同的元素。

就是这样!现在,我们已经成功地在JavaScript中实现了插入排序算法。万岁!

可视化和环绕头需要做很多事情,因此,我鼓励您考虑一下循环和指针,以真正了解正在发生的事情—单击它后,便将其永久锁定。我也将在此处重新粘贴此有用的动画,因为我认为它对可视化正在做的事情有很大帮助:

在JavaScript中实现插入排序算法插图(2)


如果您走了这么远,非常感谢您的阅读!我希望这对任何学习排序算法,JavaScript或一般编程基础的人来说都是有用的教程。

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 在JavaScript中实现插入排序算法

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论