Js实现插入排序

更新日期: 2019-05-12阅读: 2.5k标签: 算法

插入排序的工作原理是选择当前索引 i 处的元素,并从右向左搜索放置项目的正确位置。


实现插入排序

插入排序是一种非常简单的算法,最适合大部分已经被排好序的数据。在开始之前,通过可视化演示算法如何运作一个好主意。你可以参考前面的动画来了解插入排序的工作原理。

算法的基本思想是一次选择一个元素,然后搜索并插入到正确的位置。由此才有了这个名字:插入排序。这种操作将会导致数组被分为两个部分 —— 已排序部分和未排序的元素。有些人喜欢把它描绘成两个不同的数组 —— 一个包含所有未排序的元素,而另一个的元素是完全排序的。但是将其描述为一个数组更符合代码的工作方式。

先来看看代码,然后再进行讨论。

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

在插入排序的代码中有两个索引:i 和 j。 i 用来跟踪外循环并表示正在排序的当前元素。它从 1 开始而不是0,因为当我们在新排序的数组中只有一个元素时,是没有什么可做的。所以要从第二个元素开始,并将它与第一个元素进行比较。第二个索引 j 从 i-1 开始,从右往左迭代,一直到找到放置元素的正确位置。在此过程中,我们将每个元素向后移动一个位置,以便为要排序的新元素腾出空间。

这就是它的全部过程!如果你只是对实现感兴趣,那你就不用再看后面的内容了。但如果你想知道怎样才能正确的实现这个算法,那么请继续往下看!


检查循环不量变条件

为了确定算法是否能够正常工作而不是恰好得出了给定输入的正确输出,我们可以建立一组在算法开始时必须为真的条件,在算法结束时,算法的每一步都处于条件之中。这组条件称为循环不变量,并且必须在每次循环迭代后保持为真。

循环不变量并不是总是相同的东西。它完全取决于算法的实现,是我们作为算法设计者必须确定的。在例子中,我们每次迭代数组中的一个元素,然后从右向左搜索正确的位置以插入它。这将会导致数组的左半部分(到当前索引为止)始终是最初在该数组切片中找到的元素的排序排列。换一种说法是

插入排序的循环不变量表示到当前索引的所有元素“A [0..index]”构成在我们开始排序前最初在“A [0..index]”中找到的元素的排列顺序。

要检查这些条件,我们需要一个可以在循环中调用的函数,该函数作为参数接收:

  1. 新排序的数组
  2. 原始输入
  3. 当前的索引。

一旦有了这些,就能将数组从 0 开始到当前索引进行切片,并运行我们的检查。第一个检查是新数组中的所有元素是否都包含在旧数组中,其次是它们都是有序的。

//用于检查插入排序循环不变的函数
const checkLoopInvariant = (newArr, originalArr, index) => {
  //need to slice at least 1 element out
  if (index < 1) index = 1

  newArr = newArr.slice(0,index)
  originalArr = originalArr.slice(0, index)

  for (let i=0; i < newArr.length; i++) {

    //check that the original array contains the value
    if (!originalArr.includes(newArr[i])) {
      console.error(`Failed! Original array does not include ${newArr[i]}`)
    }

    //check that the new array is in sorted order
    if (i < newArr.length - 1 && newArr[i] > newArr[i+1]) {
      console.error(`Failed! ${newArr[i]} is not less than ${newArr[i+1]}`)
    }
  }
}

如果在循环之前、期间和之后调用此函数,并且它没有任何错误地通过,就可以确认我们的算法是正常工作的。修改我们的代码以包含此项检查,如下所示:

const insertionSort = (nums) => {
  checkLoopInvariant(nums, input, 0)
  for (let i = 1; i < nums.length; i++) {
    ...
    checkLoopInvariant(nums, input, i)
    while (j >= 0 && nums[j] > tmp) {
      ...
    }
    nums[j+1] = tmp
  }
  checkLoopInvariant(nums, input, nums.length)
  return nums
}

注意下图中在索引为2之后的数组状态,它已对3个元素进行了排序。


如你所见,我们已经处理了3个元素,前3个元素按顺序排列。你还可以看到已排序数组的前3个数字与原始输入中的前3个数字相同,只是顺序不同。因此保持了循环不变量。


分析运行时间

我们将要使用插入排序查看的最后一件事是运行时。执行真正的运行时分析需要大量的数学运算,你可以很快找到自己的杂草。如果你对此类分析感兴趣,请参阅Cormen的算法导论,第3版。但是,就本文而言,我们只会进行最坏情况的分析。

插入排序的最坏情况是输入的数组是按逆序排序的。这意味着对于我们需要迭代每个元素,并在已经排序的元素中找到正确的插入点。外部循环表示从 2 到 n 的总次数(其中 n 是输入的大小),并且每次迭代必须执行i-1次操作,因为它从 i-1 迭代到零。


这个结论的证明超出了本文的范围。老实说,我只是将它与最佳情况进行比较,其中元素已经排序,因此每次迭代所需要的时间都是固定的......


就 big-O 表示法而言,最坏情况是 Ɵ(n²),最好的情况是Ɵ(n)。我们总是采用最坏情况的结果,因此整个算法的复杂度是Ɵ(n²)。


总结

当输入的数组已经大部分被排好序时,插入排序的效果最佳。一个好的程序应该是将一个新元素插入已经排好序的数据存储中。即便是你可能永远不必编写自己的排序算法,并且其他类型(例如归并排序和快速排序)更快,但是我认为用这种方式去分析算法的确很有趣。

本文首发微信公众号:前端先锋  

翻译:疯狂的技术
https://medium.com/@jimrottin...  


链接: https://www.fly63.com/article/detial/3290

js洗牌算法:javascript数组随机打乱顺序的实现方法

有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。

程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法

js从数组取出 连续的 数字_实现一维数组中连续数字分成几个连续的数字数组

使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

js之反转整数算法

将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!