插入排序

算法描述：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2

<?php
$arr=array(5,1,0,3,9,10,59,41,78,56,45,47,12,15,45,11);
insertSort($arr);

function insertSort($arr){
    for($i = 1; $i < count($arr); $i++){
        $tmp = $arr[$i];
        $key = $i-1;
        while($key>=0 && $tmp < $arr[$key]){
            $arr[$key+1] = $arr[$key];
            $key--;
        }
        if(($key+1)!=$i)
        $arr[$key+1]=$tmp;
        echo json_encode($arr).PHP_EOL;
    }
    return$arr;
}
?>