php 插入排序程序代码

排序算法的种类是多种多样，各有各的长处，这几天会一一进行分析。学习应该有一个先后递进的过程，从容易的开始。

先说比较简单的 — 插入排序（由PHP代码实现，这里不讲究效率！）

/**
* 插入排序 -- 比冒泡稍微复杂一点的排序算法 *
*
**/
 
$array = array('5','6','3','1','2','4');
 
/**
   * 插入排序1 -- 使用最暴力的排序
   *
**/
 
function insertSort($array)
    {
       $count = count($array); //先取出一个数据最为比较数据
       for($i=1;$i<$count;$i++)
       {
           $key = $array[$i];
           $j = $i-1;
           while($j>=0 && $array[$j]>$key)
          {
               $array[$j+1] = $array[$j];
               $j = $j-1;
               $array[$j+1] = $key;
            }
           var_dump($array);
      }
   }
 
 insertSort($array);

下面是运行结果：

 嗯，整个算法已经完了！如果你只想要代码的。你事情已经完成了，下面开始讲原理。

插入排序之所以叫插入排序，我们可以形象的理解为：

你摸牌的时候，你手里的牌是有序的，而你从牌堆里摸的牌是随机出现的，你只需跟你手里的牌进行比较排序，就能确定新牌的位置

插入的排序的逻辑可以简单的理解为，从第二个元素前，开始跟第一个元素进行比较，如果比对一个元素小，该元素就插入到第一个元素的前面

如果大，则跟第二个元素进行比较，以此类推。（从效果图中，可以看出来）

再来看看插入排序的时间发杂度：

最优的情况，所有的N-1个元素只需要跟前面的元素比较一次，那么时间复杂度是n-1;
最差的勤快，所有的N-1个元素都需要跟前面的所有元素比较一次，那么时间复杂度是一个等差数列 ((n-1)*(n-2))/2+(n-1);
综上所述：插入排序的时间复杂度应该是位于这两则之间。

空间复杂度： 插入排序是一种线性排序。所有空间复杂度跟参与排序的N有关。