插入排序

一、原理解析

1. 从第一个元素开始，该元素可以认为已经被排序取出下一个元素，在已经排序的元素序列中从后向前扫描把取出的元素放到已排序的元素中间的合适位置重复步骤2~3

就像排队一样，依次每次挑一个同学，把该同学“插入”到已经排好的部分队伍里。

二、范例演示

以下表格里，红色表示选中的待排序的数字，蓝色表示最终排好的数字。

第一轮：对于第一个元素(红色)，变成已排序元素(蓝色)

第二轮：对于第二个元素，和已排序元素(蓝色数字)比较，插入到已排序元素中合适的位置（8放到10前面，之后都变成已排序元素）

第三轮：对于第三个元素，和已排序元素(蓝色数字)比较，插入到已排序元素中合适的位置（9放到8和10中间，之后变成已排序元素）

...

三、实现方式

插入法JS 版

插入法普通版

四、效率测试

下面我们测试排序性能

经浏览器测试，数组长度增加10倍，排序时间约增加100倍。

五、复杂度分析

时间复杂度为 O(n^2) ，和上面的测试基本一致。

本文作者：若愚

如果你觉得不错，或者发现文章中的错误，或者有更好的建议，欢迎加入算法交流群交流，添加微信:hungervalley 拉入群

往期文章

前端工程师算法系列(1)-冒泡排序

前端工程师算法系列(2)-选择排序