前言
上一节我们讨论了利用选择排序让班长帮着差生排队，这次我们使用另外一种办法排队-插入排序算法。另外：昨天的选择排序的动画图不动了，已经修正。
内容概要：
1、什么是插入排序算法。
2、插入排序算法的动画图。
3、插入算法的PHP代码实现。
一、什么是插入排序。
书接上回。老师又不满意（对不起老师，剧情需要，当然也有可能老师让差生出点洋相），问班上同学，你们谁有新的排序方法，体育委员自告奋勇。
差生的位置还是一样，ABCDE。
五个同学排队
体育委员的排序思路是这样的：
第一轮：假设第一个位置（A）的同学已经排好，让第二个位置（B）同学出列，和第一个位置（A）的同学比较分数，如果分数比第一位置(A)小的话，占据第一位置(A)，原来第一位置(A)的同学顺延往后排。这样，A位置和B位置按照分数多少已经升序排好。
第二轮：第三位置(C)的同学出列，分别和第二位置(B)先比较，如果比第二位置的同学分数大，则位置不动，直接进行下一轮。如果比第二个位置的同学分数少，则互换一下位置。然后第二个位置的同学（互换之后的同学）再和第一位置(A)的同学比较，如果比第一个同学分数大，则位置不动，直接进入下一轮。否则，与第一位置的同学互换位置。这样，ABC三个位置上的同学按照分数多少已经升序排好。
第三轮：第四位值（D）的同学出列，按照第二轮的思路依次比较，完成ABCD四个位置的同学按照分数多少升序排好。
第四轮：第五位值（E）的同学出列，同样道理，排好ABCDE位置同学，排序结束（体育委员还真行啊）。
总结一下：在要排序的一组数中，假设前面的数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。这种排序方法就是插入排序算法。
二、插入排序算法的动画图。
三、插入排序算法的PHP代码实现
还是以数组的形式，代码献丑如下：
<?php
/************************************************************
** @Description: PHP排序算法之插入排序
** @Author: haodaquan
** @Date: 2017-03-13 14:07:29
** @Last Modified by: haodaquan
** @Last Modified time: 2017-03-13 14:31:48
*************************************************************/
function insertSort($arr) {
$len = count($arr);
if ($len <= 1) return $arr;
for($i = 1; $i < $len; $i++) {
$tmp = $arr[$i];
#内层循环控制，比较并插入
for($j = $i-1;$j >= 0;$j--) {
#如果碰到不需要移动的元素，由于是已经排序好是数组，
#则前面的就不需要再次比较了。
if($tmp >= $arr[$j]) break;
#发现插入的元素要小，交换位置，将后边的元素与前面的元素互换
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
}
}
return $arr;
}
#应用
$arr = [30,49,15,21,19];
var_dump(insertSort($arr));
代码加入了注释，估计大家可以看懂。有问题评论区提出来吧。
