插入排序，一般也被称为直接插入排序，插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中。

算法步骤
1、将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置，如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

动图演示

代码实现：

public function insertSort($arr)
{
    $length = count($arr);
    for ($i = 0; $i < $length - 1; $i ++) {
        $tmp = $arr[$i + 1]; // 要插入的数据
        $j = $i; // 取第几个
        while ($j >= 0 && $tmp < $arr[$j]) { // 被插入的数据比前面的数据小(大)，前面的数据就往后面移，前面的数据已经是有序，所以比较一个就知道是否还需要和前面的进行比较
            $arr[$j + 1] = $arr[$j];
            $j --;
        }
        
        $arr[$j + 1] = $tmp; // 插入到移出来的空位置
    }
    return $arr;
}