直接插入排序(Insertion Sort)就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

视频

InsertSort1一般思路,计算执行效率
InsertSort2代码精简版,计算执行效率
InsertSort3 精简

$arr = createArray(4000);
$r = InsertSort1($arr);
echo "\n<br/>";
$r = InsertSort2($arr);

function InsertSort1($arr)
{
 $start = microtime(TRUE);   //排序开始时间
    $n = count($arr);
   $s = 0;     //循环记数
  for($i=1;$i<$n;$i++) {
       if($arr[$i-1] > $arr[$i]) {
          $flag = TRUE;
           $j = $i;
            while($flag) {
              if($j && $arr[$j-1] > $arr[$j]) {
                    swap($arr[$j-1], $arr[$j]);     //交换两个数
             }else{
                  $flag = false;
              }
               $j--;
               $s++;
           }
       }
   }
   echo "*$s*\n";   //打印循环次数
    $end = microtime(TRUE)-$start;      //排序结束时间
    echo "InsertSort1:$end\n<br/>";
    return $arr;
}

function InsertSort2($arr)
{
    $start = microtime(TRUE);
   $n = count($arr);
   $s = 0;
 for($i=1;$i<$n;$i++) {
       for($j=$i; $j>0 && $arr[$j-1]>$arr[$j];$j--) {
            swap($arr[$j-1], $arr[$j]);
         $s++;
       }
   }
   echo "*$s*\n";
   $end = microtime(TRUE)-$start;
  echo "InsertSort1:$end\n<br/>";
    return $arr;
}

function InsertSort3($arr)
{
    $n = count($arr);
   for($i=1;$i<$n;$i++) {
       for($j=$i; $j>0 && $arr[$j-1]>$arr[$j];$j--) {
            swap($arr[$j-1], $arr[$j]);
         $s++;
       }
   }
   return $arr;
}

function swap(&$a, &$b)
{
   list ( $a, $b ) = array ($b, $a );
}

function createArray($length)
{
   $start = microtime(TRUE);
   $arr = array();
 while ($length--) {
     $arr[] = rand();
    }
   $end = microtime(TRUE)-$start;
  echo "createArray:$end\n<br/>";
    return $arr;
}