用JavaScript实现插入排序

LittleLiByte 发布于2019-08-26 13:44 / 1927人阅读

摘要：实现插入排序插入排序是一种非常简单的算法，最适合大部分已经被排好序的数据。由此才有了这个名字插入排序。插入排序的最坏情况是输入的数组是按逆序排序的。总结当输入的数组已经大部分被排好序时，插入排序的效果最佳。

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

本文首发微信公众号：前端先锋
欢迎关注，每天都给你推送新鲜的前端技术文章

插入排序的工作原理是选择当前索引 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]”中找到的元素的排列顺序。

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

新排序的数组

原始输入

当前的索引。

一旦有了这些，就能将数组从 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²)。

总结

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

本文首发微信公众号：前端先锋 欢迎扫描二维码关注公众号，每天都给你推送新鲜的前端技术文章

欢迎继续阅读本专栏其它高赞文章：

12个令人惊叹的CSS实验项目

必须要会的 50 个React 面试题

世界顶级公司的前端面试都问些什么

11 个最好的 JavaScript 动态效果库

CSS Flexbox 可视化手册

从设计者的角度看 React

过节很无聊？还是用 JavaScript 写一个脑力小游戏吧！

CSS粘性定位是怎样工作的

一步步教你用HTML5 SVG实现动画效果

程序员30岁前月薪达不到30K，该何去何从

14个最好的 JavaScript 数据可视化库

8 个给前端的顶级 VS Code 扩展插件

Node.js 多线程完全指南

把HTML转成PDF的4个方案及实现

GPU云服务器云服务器用php实现插入排序实现插入排序插入排序直接插入排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/109417.html

用 JavaScript 实现链表操作 - 06 Insert Sort

摘要：需求实现一个函数对链表进行升序排列插入排序。关于插入排序插入排序的介绍可以看，大体逻辑为建立一个新的空链表。遍历完成，返回新链表。代码如下总结因为有上个的函数的帮助，这个插入排序实现起来非常简单。 TL;DR 2016 年末最后一篇，对链表进行插入排序。系列目录见前言和目录。需求实现一个 insertSort() 函数对链表进行升序排列（插入排序）。实现过程中可以使用上一个 ...

doodlewind 2019-08-21 11:28 评论0 收藏0
JavaScript 数据结构与算法之美 - 冒泡排序、插入排序、选择排序

摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，...

canger 2019-08-26 10:15 评论0 收藏0
深入浅出 JavaScript 的 Array.prototype.sort 排序算法

摘要：快速排序是不稳定的排序算法。浏览器的实现不同有什么影响排序算法不稳定有什么影响举个例子某市的机动车牌照拍卖系统，最终中标的规则为按价格进行倒排序相同价格则按照竞标顺位即价格提交时间进行正排序。本文要解决的问题 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一种直观的方式展示 Array.prototype.sort 的时间复杂度，看看它有多快？ 3、...

itvincent 2019-08-21 11:55 评论0 收藏0
JavaScript各种排序算法的实现及其速度性能分析

摘要：今天我们来讨论的问题有两个如何用实现选择排序冒泡排序插入排序快速排序归并排序堆排序对生成的万个随机数进行排序，各个排序算法的性能分析。快速排序快速排序算法基本上是面试必考排序算法，也是传闻最好用的算法。今天我们来讨论的问题有两个：如何用JavaScript实现选择排序、冒泡排序、插入排序、快速排序、归并排序、堆排序；对生成的10万个随机数进行排序，各个排序算法的性能分析。创...

yuanxin 2019-08-20 19:03 评论0 收藏0
JavaScript 数据结构与算法之美 - 十大经典排序算法汇总

摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面，而，排序之后，在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法为王。想学好前端，先练好内功，内功不行，就...

zsy888 2019-08-26 10:27 评论0 收藏0