用JavaScript实现插入排序

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

欢迎关注，每天都给你推送新鲜的前端技术文章

插入 排序 的工作原理是选择当前索引 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²)。

总结

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

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

欢迎扫描二维码关注公众号，每天都给你推送新鲜的前端技术文章

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