一、原理
插入排序原理，通过构建有序序列，对于未排序的数据部分，在已排序的序列中从后往前扫描，找到相应的位置，逐个元素插入。类似于打扑克牌，取牌的过程。

二、算法
0、从第一个元素开始，认为该元素已被排序。
1、取下一个元素，在已经排序的元素序列中从后往前扫描。【取下一个元素这个表述特别赞，如果用第二个元素就不好表达后面的插入了】
2、如果该元素大于新元素，则后移该元素。
3、重复步骤2，直到找到小于、等于新元素的位置。
4、将新元素插入到该位置后。
5、重复步骤1-4。

三、算法实现

// 开始的思考是用一个数组单独存储排序好的元素，这样空间复杂度就高了
function insertSort($arr)
{
        $count = count($arr);
        for ($i = 1; $i < $count; $i++) {
                $value = $arr[$i];
                // $i - 1 之前的元素都是有序的
                for ($j = $i - 1; $j >= 0; $j--) {
                        if ($arr[$j] > $value) {
                                // 后移一个位置
                                $arr[$j + 1] = $arr[$j];
                        } else {
                                break;
                        }
                }
                // 201707开始比较困惑，为啥是$j + 1。因为$j + 1 = $i, 而$i的值已经被赋值$value, 所以$j + 1相当于空隙
                // 201908还是困惑，自己按照程序逻辑走一走，就发现，$j下次比较前会-1, 所以$j + 1始终是空出来的
                $arr[$j + 1] = $value;
        }

        return $arr;
}

$data = [2, 3, 8, 6, 1];
var_dump(insertSort($data));

// 以上输出结果

array(5) {
  [0]=>
  int(1)
  [1]=>
  int(2)
  [2]=>
  int(3)
  [3]=>
  int(6)
  [4]=>
  int(8)
}

四、算法实现改进

function insertSort($arr)
{
        $count = count($arr);
        for ($i = 1; $i < $count; $i++) {
                // 未排序的元素比已排序序列中最后一个元素小时，才移动和插入
                if ($arr[$i - 1] > $arr[$i]) {
                        $value = $arr[$i];
                        for ($j = $i - 1; $j >= 0; $j--) {
                                if ($arr[$j] > $value) {
                                        // 后移一个位置
                                        $arr[$j + 1] = $arr[$j];
                                } else {
                                        break;
                                }
                        }
                        $arr[$j + 1] = $value;
                }
        }

        return $arr;
}

$data = [2, 3, 8, 6, 1];
var_dump(insertSort($data));

参考：维基百科插入排序