算法引入：
在这里我们依然使用《大话数据结构》里面的一个例子：
扑克牌是我们几乎每个人都玩过的游戏。平时我们开始的时候一般都是一个人发牌，其他人都是一边摸牌，一边理牌，假如你摸上的第一张牌是 5，第二张牌是 3，自然而然的我们把 3 插到 5 的前面；第三张牌是 4，查到 3 和 5 的中间；第四张牌是 6，放到 5 的后面；第五张牌是 2，插到 3 的前面；……。最后当我们摸完所有的牌时，手上的牌都是从小到大（点数）排好序的。
我们来看这个顺序：
image.png
<?php
namespace Home\Controller;
use think\Controller;
class InsertController extends Controller{
public function index(){
$arr = array(9,1,5,8,3,7,4,6,2);
$this->InsertSort($arr);
var_dump($arr);
}
//直接插入排序
function InsertSort(array &$arr){
$count = count($arr);
//数组中第一个元素作为一个已经存在的有序表
for($i = 1;$i < $count;$i ++){
$temp = $arr[$i]; //设置哨兵
for($j = $i - 1;$j >= 0 && $arr[$j] > $temp;$j --){ //0[] > 1[]
$arr[$j + 1] = $arr[$j]; //记录后移
}
$arr[$j + 1] = $temp; //插入到正确的位置
}
}
}
