插入排序，一篇文章搞定

插入排序

插入排序含义

了解一个知识，需要从它的含义开始。 什么是插入排序呢，用一个例子来说明：按照身高排队🌰 一群小朋友站在一起，老师让他们按照从低到高进行排队，小朋友们不知道怎么排队，于是老师让他们先站成一排，已知排队顺序为【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

这样结束后就进入第二轮循环。

总结

插入排序相当于先比较后插入，合适位置后再插入排序。算法并不是看一眼就可以懂的了，写一个数组，写一遍插入排序，运行之后，跟随代码步骤进行走一遍数据，才能更加深刻的了解其中是如何比较的。