插入排序时一种常见的排序算法 , 有点类似于我们打扑克摸牌的过程 , 每摸一张牌 , 我们便通过对比手上已有的牌 , 将刚拿到的牌放入合适的位置 。实现实现思路假设前j-1个元素已经排好序 , 将第j个元素分别于其前面元素[i]比较,
- 如i元素较大 , 则将i元素的值往前移动一位 , 即 a[i+1] = a[i]
- 若i元素较小 , 则直接将j位置的值放到 i+1元素的位置 。
从j等于1开始(这里假设初始位置为0) , 如下图所示
文章插图
此时拿着5和前面的每个数对比 , 此处是1 , 发现 5 > 1,故将五放在 i+1的位置 , 即5的位置保持不变 , 此时i = 0, 即前面已经没有其他数了了 , 所以前两个数已经排好序 。
接着 j = j+ 1,如下图所示 。i = j-1
文章插图
为了能将3排好序 , 必须将其与其前面(位置0,1)的数逐个对比 , 这里先对比 3和5 , 发现 3< 5,此时 将5放到3的位置 ,
文章插图
此时i =0, 对比i位置的值和key的大小 , 发现 1 < 3,此时找到key应该放置的位置 , 即 i + 1 =3;
文章插图
此时前三个数已经排好序 , j 继续加1
文章插图
此时 , 要将 key =4 插入到前面( 0 -3)的合适位置中去 , 同样对比 key和 i位置的值 , 发现 5 > 4,大的应该往后推 , 所以 5应该在4的后面 。
文章插图
这里将5往前移动一位 , i –,在比较 i位置的值和 key的大小关系
发现 3 < key , 0 -i都已排好序 , 所以找到了key的合适位置 , 即是 i+ 1;
文章插图
j继续加1 , 重复上述过程 , 直至 j = 6,最后便可以排成
1 , 3, 4 , 5, 5 , 6 , 8
简而言之 , 每次排序一个数key , 都要对比前面的对比该位置的值与该位置前面的值的大小 , 若key较小 , 则将与key对比的数往后( i+1)移动一位 。直到找到一个小于或等于key的值 , 则将key放在该数的后一个位置处 。
根据上面的过程 , 我们可以很容易的得到该排序过程的时间复杂度 , 因为要排序每一个数(n),排序该数的时候 , 还得将这个数与前面最多(n-1)个数对比 , 才能找到合适的位置 。所以其时间复杂度约为0(n2) 。
js代码实现
文章插图
总结1)从第二位开始,与前面的所有数值比较,将大的数据向下移动
2)时间复杂度是O(n2)
【图解插入排序算法】
推荐阅读
- 滇红茶泡法图解
- 图解硬盘的物理结构 硬盘的结构
- 单工、半双工、全双工通信的基础知识,图解分析,看完就理解了
- 图解泡普洱茶方法,图解泡普洱茶的方法
- 5分钟图解SSH
- 淘宝按销量排序是什么销量 为什么淘宝按销量排序是不对的
- 小清新树叶书签折纸图解 树叶书签制作方法
- 凉席折叠步骤图解 凉席折叠的印怎么弄平
- 马桶应该坐哪一层图解 马桶应该坐哪一层
- 杀蟑饵剂使用方法图解 杀蟑胶饵使用方法图解