PHP实现插入排序算法

<?php
function insert_sort($arr){
    for ($i=1;$i<count($arr);$i++){
        $key=$arr[$i];
        $j=$i-1;
        //插入排序判断条件
        while($j>=0 && $arr[$j]>$key){
            $arr[$j+1]=$arr[$j];
            $j=$j-1;
        }
        $arr[$j+1]=$key;
    }
    return $arr;
}

$arr= array(5,2,4,6,1,3);
$arr=insert_sort($arr);
var_dump($arr);
?>

循环不变式(理解算法的正确性)

循环不变式的三条性质:

  1. 初始化:循环的第一次迭代之前,它为真
  2. 保持:如果循环的某次迭代之前他为真,那么下一次迭代之前它仍为真。
  3. 终止:在循环终止时,不变式为我们提供一个有用的性质,该性质是用于证明算法是正确的。

    利用循环不变式证明插入排序是正确的

  4. 初始化:当$i=2时,进入循环,$i=2所在数组元素前只有一个A[1],因为只有一个元素,那么这个判断之前,该数组一定是有序的。
  5. 保持:第二条性质,当第一次循环执行下来,A[1]与A[2]进行比较,A[1],A[2]按照由小到大进行排列,保持了初始化中的性质,循环到$i为任意值,那么循环过后1-j一定是有序的,保持数组是有序的性质。
  6. 终止:循环终止的条件是i > 数组.length = n,因为每次循环i都会增加1,最终 1-n一定是有序排列的。

    总结

    插入一个数据之前,所在位置n之前的数据一定是有序排列的。

插入排序最坏运行时间为n² 最好的运行时间为n 那么该数组一定是有序的。