阅读 1202

手写算法并记住它:插入排序

对于经典算法,你是否也遇到这样的情形:学时觉得很清楚,可过阵子就忘了?

本系列文章就尝试解决这个问题。

研读那些排序算法,细品它们的名字,其实都很贴切。

比如插入排序,所谓“插入”,实指把待排序元素插入到已排好的序列里。

上图演示了第4次遍历,此时元素1、3、5已经是有序序列,待排的元素是2,要把它插入到1和3之间。此时3和5都往后移动了一位。

可以看出该算法的核心是:如何在有序序列里找到正确的插入位置?

思路是从有序序列的尾部开始,逐个与目标元素比较,如果大于目标元素,该元素需要后移。

可以看出之所以先要缓存一下目标,是为了要把它的位置先空下来,方便其他元素移入。 另外,当元素不大于目标时,此时说明要插入目标的位置已经找到了。

翻译成代码:

let array = [1, 3, 5, 2, 4]
let i = 3
let target = array[3]
while(i > 0 && array[i-1] > target) {
  array[i] = array[i-1]
  i--
}
array[i] = target
console.log(array) // [ 1, 2, 3, 5, 4 ]
复制代码

能插入成功一个,遍历n-1次(第一个元素本身就是有序序列了),就可以全部插入,代码很容易写出来:

for (let j = 1; j < array.length; j++) {
  let i = j
  let target = array[i]
  while(i > 0 && array[i-1] > target) {
    array[i] = array[i-1]
    i--
  }
  array[i] = target
}
复制代码

查看完整代码:codepen

至此,插入排序原理和实现已经说完了。

这里总结一下,插入排序不需要额外空间,是本地排序,相等元素是不会交换前后顺序,因而也是稳定排序,时间复杂度为O(n^2),适用于少量数据排序。相比冒泡排序和选择排序,插入排序的使用相对多一些。因为前两者是交换排序,本质上需要3次原子操作的。

插入排序,要做到能分分钟手写出来,是需要掌握其排序原理的。每次遍历核心是找到正确的插入位置,一旦内层遍历能写出来,那么整体就很容易写出来,不需要死记硬背的。

希望有所帮助,本文完。



本系列已经发表文章:

关注下面的标签,发现更多相似文章
评论