思路分析

每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。(从而得到一个新的、个数加一的有序数据)

/*
 * 插入排序法
 * 每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
 * */
 function insertSort($arr){
     $len = count($arr);
     if ($len <= 1) {return $arr;}
     //先默认$array[0]，已经有序，是有序表
     for($i = 1;$i < $len;$i++){
         if ($arr[$i] < $arr[$i-1]){
             $insertVal = $arr[$i]; //$insertVal是准备插入的数
             $insertIndex = $i - 1; //有序表中准备比较的数的下标
             while($insertIndex >= 0 && $insertVal < $arr[$insertIndex]){
                 $arr[$insertIndex + 1] = $arr[$insertIndex]; //将数组往后挪
                 $insertIndex--; //将下标往前挪，准备与前一个进行比较
             }
             if($insertIndex + 1 !== $i){
                 $arr[$insertIndex + 1] = $insertVal;
             }
         }
     }
     return $arr;
 }
 function insertSort2($arr){
     $len = count($arr);
     if ($len <= 1) {return $arr;}
     //先默认$array[0]，已经有序，是有序表
     for($i = 1;$i < $len;$i++){
         if ($arr[$i] < $arr[$i-1]){
             $insertVal = $arr[$i]; //$insertVal是准备插入的数
             //$j 有序表中准备比较的数的下标
             //$j-- 将下标往前挪，准备与前一个进行比较
             for ($j = $i-1;$j >= 0 && $insertVal < $arr[$j];$j--){
                 $arr[$j+1]= $arr[$j];//将数组往后挪
             }
             $arr[$j + 1] = $insertVal;
         }
     }
     return $arr;
 }

小结：

时间复杂度：O(n^2)

空间复杂度：O(1)

算法适用于少量数据的排序

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

插入排序属于稳定排序