插入算法的示意图解以及每次循环数字的比对
首先,先看插入算法的示意图吧
先从图片开始,可以看到先从第二个开始往前面比,然后再从第三个。。。第四个。。。第五个。一直往前面比,如果比前面的小就更换一下顺序。。。
但上面的图片的示意并不能不是插入排序最好使用的场景是配合希尔排序是比较好的。。。下面开始搞算法
这里吐糟一下,本人全栈,php,go,js都会,但是写算法还是比较喜欢用js写。。。写的时候还喜欢用在线工具直接看结果
----------------------------------
时间复杂度:最坏情况下为O(N*N),此时待排序列为逆序,或者说接近逆序
最好情况下为O(N),此时待排序列为升序,或者说接近升序。
空间复杂度:O(1)
----------------------------------
----写完才发现结尾go写的更好一些,就先酱啦
var a = [9,8,5,2,10,66,33,4,982,56,99,552,44,5,3]; var b=0 var n=0 for (i=1;i<a.length;i++){ console.log("正在进行第"+i,"次排序") for(o=i-1;o>=0;o--){ n++ if(a[o]>a[o+1]){ b=a[o+1] a[o+1]=a[o] a[o]=b }else{ break } console.log(a) } } console.log("总共运行了",n,"次完成") -------------使用js运行出来的结果是:------------------ > "正在进行第" 1 "次排序" > Array [8, 9, 5, 2, 10, 66, 33, 4, 982, 56, 99, 552, 44, 5, 3] > "正在进行第" 2 "次排序" > Array [8, 5, 9, 2, 10, 66, 33, 4, 982, 56, 99, 552, 44, 5, 3] > Array [5, 8, 9, 2, 10, 66, 33, 4, 982, 56, 99, 552, 44, 5, 3] > "正在进行第" 3 "次排序" > Array [5, 8, 2, 9, 10, 66, 33, 4, 982, 56, 99, 552, 44, 5, 3] > Array [5, 2, 8, 9, 10, 66, 33, 4, 982, 56, 99, 552, 44, 5, 3] > Array [2, 5, 8, 9, 10, 66, 33, 4, 982, 56, 99, 552, 44, 5, 3] > "正在进行第" 4 "次排序" > "正在进行第" 5 "次排序" > "正在进行第" 6 "次排序" > Array [2, 5, 8, 9, 10, 33, 66, 4, 982, 56, 99, 552, 44, 5, 3] > "正在进行第" 7 "次排序" > Array [2, 5, 8, 9, 10, 33, 4, 66, 982, 56, 99, 552, 44, 5, 3] > Array [2, 5, 8, 9, 10, 4, 33, 66, 982, 56, 99, 552, 44, 5, 3] > Array [2, 5, 8, 9, 4, 10, 33, 66, 982, 56, 99, 552, 44, 5, 3] > Array [2, 5, 8, 4, 9, 10, 33, 66, 982, 56, 99, 552, 44, 5, 3] > Array [2, 5, 4, 8, 9, 10, 33, 66, 982, 56, 99, 552, 44, 5, 3] > Array [2, 4, 5, 8, 9, 10, 33, 66, 982, 56, 99, 552, 44, 5, 3] > "正在进行第" 8 "次排序" > "正在进行第" 9 "次排序" > Array [2, 4, 5, 8, 9, 10, 33, 66, 56, 982, 99, 552, 44, 5, 3] > Array [2, 4, 5, 8, 9, 10, 33, 56, 66, 982, 99, 552, 44, 5, 3] > "正在进行第" 10 "次排序" > Array [2, 4, 5, 8, 9, 10, 33, 56, 66, 99, 982, 552, 44, 5, 3] > "正在进行第" 11 "次排序" > Array [2, 4, 5, 8, 9, 10, 33, 56, 66, 99, 552, 982, 44, 5, 3] >&nb本文来自投稿,不代表本人立场,如若转载,请注明出处;如有问题您可以发邮件到:itlun@qq.com