php实现插入排序（Insertion Sort）

插入排序

        基本思想: 在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

算法描述

       从第一个元素开始，该元素可以认为已经被排序；

取出下一个元素，在已经排序的元素序列中从后向前扫描；

如果该元素（已排序）大于新元素，将该元素移到下一位置；

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

将新元素插入到该位置后；

重复步骤2~5。

图片描述

代码实现(php）

<?php
 $arr = [2, 3, 1, 6, 4, 7, 5, 9];

 var_dump(insertsort($arr));
 function insertSort($arr) {
     $len = count($arr);
     for ($i = 1; $i < $len; $i++) {
       // 当前值
        $key = $arr[$i];
         // 当前位置
       $pos = $i;
        // 如是当前位置 >0 && 当前值的前一个值 > 当前值 选出最值
         while ($pos > 0 && $arr[$pos - 1] > $key) {
            // 当前值  =  前一个值
            $arr[$pos] = $arr[$pos - 1];
            // 当前位置后移
            $pos = $pos - 1;
       }
       // 找到当前值的位置
        $arr[$pos] = $key;
    }
   return $arr;
 }