PHP实现插入排序算法
1 | <?php |
循环不变式(理解算法的正确性)
循环不变式的三条性质:
- 初始化:循环的第一次迭代之前,它为真
- 保持:如果循环的某次迭代之前他为真,那么下一次迭代之前它仍为真。
- 终止:在循环终止时,不变式为我们提供一个有用的性质,该性质是用于证明算法是正确的。
利用循环不变式证明插入排序是正确的
- 初始化:当$i=2时,进入循环,$i=2所在数组元素前只有一个A[1],因为只有一个元素,那么这个判断之前,该数组一定是有序的。
- 保持:第二条性质,当第一次循环执行下来,A[1]与A[2]进行比较,A[1],A[2]按照由小到大进行排列,保持了初始化中的性质,循环到$i为任意值,那么循环过后1-j一定是有序的,保持数组是有序的性质。
- 终止:循环终止的条件是i > 数组.length = n,因为每次循环i都会增加1,最终 1-n一定是有序排列的。
总结
插入一个数据之前,所在位置n之前的数据一定是有序排列的。
插入排序最坏运行时间为n² 最好的运行时间为n 那么该数组一定是有序的。