了解一个知识,需要从它的含义开始。 什么是插入排序呢,用一个例子来说明:按照身高排队🌰 一群小朋友站在一起,老师让他们按照从低到高进行排队,小朋友们不知道怎么排队,于是老师让他们先站成一排,已知排队顺序为【A,B,C,D】,其中B>A>D>C。 老师从第B同学开始,把第B同学拎出来,先让他和第A同学进行比较,如果A同学身高低于B同学的。那么就把第B同学放回第二位的位置。同理,A同学比B同学高,那么交换位置。 到这并不能体现出插入排序的意义,由此,向下看 然后老师拎出C同学,和B同学进行比较,恰好C同学比B矮,那么,让第B同学到C同学的位置上,但是C同学暂时不排队,接着让C同学与A同学进行比较。发现C同学比A同学矮,所以让A同学到B同学原来的位置上,也就是说像右移动一位。此时在把C同学插入到A同学原来的位置上。此时的排队顺序是【C,A,B,D】。 接着将D同学拎出来,和B同学比较身高,B同学比D同学高,那么让B同学到D同学的位置上。继续拎着D同学和A同学比较,A>D,所以A同学到B同学上一次的位置上。接着拎着D同学和C同学比较,发现D>C,所以再将D同学插入到第二个位置上,此时排队顺序是【C,D,A,B】。 由此,排队完成。举这个例子的目的主要是了解插入排序是怎么插入到其中的。
首先,定义一个数组
var arr=[58,34,76,12,42,57,23,64]
排序代码
for(var i=1;i<arr.length;i++){
var key =arr[i];
var j=i-1;
while(j>=0 && arr[j]>key){
arr[j+1]=arr[j]
j=j-1;
}
arr[j+1]=key;
}
首先,外部for循环
for(var i=1;i<arr.length;i++){
//循环体
}
主要作用是遍历每一个元素,相当于排队的每一个同学。
key变量
var key =arr[i];
将第二个元素的值赋值给key,这里的key元素相当于作为标记元素,例如例子当中被拎出来的同学。
初始化j
var j=i-1;
遍历j的,相当于标记同学的前一位同学的下标号
while循环
while(j>=0 && arr[j]>key){
arr[j+1]=arr[j]
j=j-1;
}
判断条件是当j>=0时,也就是必须在数组下标范围内 arr[0]、arr[1]…第一位同学、第二位等等 条件二 前一位同学的身高大于标记同学的身高,则进入循环体进行换位
arr[j+1]=arr[j]
前一位同学大于标记同学,将前一位同学的位置更换到标记同学的位置上,但未将标记同学插入。
j=j-1;
此时j的位置为再次基础上的前一个同学。然后执行后再次进入while循环。
当循环未满足时,也就是前一位的同学小于后一位的同学时,那么执行插入计划
arr[j+1]=key;
为什么是j+1呢 当跳出循环的时候有两种情况,第一种,j<0,此时的j=-1,说明这个值是最小的值,那么+1的时候刚好在第一位arr[0],所以就此插入 第二种情况是当值不大于标记值时。
arr[j]>key j=j-1=3 假如arr[3]>key是false 即key>arr[3] key排在arr[3]的后面 那么则key的位置应该是j=4那么就命令arr[j+1]=arr[4]=key
这样结束后就进入第二轮循环。
插入排序相当于先比较后插入,合适位置后再插入排序。算法并不是看一眼就可以懂的了,写一个数组,写一遍插入排序,运行之后,跟随代码步骤进行走一遍数据,才能更加深刻的了解其中是如何比较的。