迹忆客 专注技术分享

本篇承接 插入排序（概念篇） 奉上直接插入排序的实现步骤以及实现代码由于概念篇已经有了大量的图解，本篇如果再进行图解，未免显得有些啰嗦，因此在这里直接罗列步骤和代码。

实现步骤：

1. 将第一个待排序的序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从头到尾一次扫描未排序的序列，将扫描到的每个元素插入有序序列的适当位置（在这里需要注意一个问题，如果在有序序列中有一个和待插入的元素相等，则将待插入的元素查到此元素的后面，这样方式的插入排序是稳定的。如果插入到此元素的前面，那么此种方式的插入排序是不稳定的

实现代码（PHP代码）:

第一种实现代码是从第一个元素开始向后遍历，找到相应的位置，然后进行元素移动和插入 代码如下

$arr1 = array(
15,77,23,43,90,87,68,32,11,22,33,99,88,66,44,113,
224,765,980,159,456,7,998,451,96,0,673,82,91,100
);
for($i=1;$i<count($arr1);$i++){
    $p = $arr1[$i];
    for($j=0;$j<$i;$j++){
        if($arr1[$j]>$p){
            break;
        }
    }
    for($k=$i-1;$k>=$j;$k--){
        $arr1[$k+1] = $arr1[$k];
    }
    $arr1[$j] = $p;
}

第二种实现代码是从当前待排序元素的前一个元素（也就是有序序列的最后一个元素）开始向前遍历，找到相应的位置，然后进行元素移动和插入 代码如下

$arr2 = array(
15,77,23,43,90,87,68,32,11,22,33,99,88,66,44,113,
224,765,980,159,456,7,998,451,96,0,673,82,91,100
);
for($i=1;$i<count($arr2);$i++){
    $p = $arr2[$i];
    for($j=$i-1;$j>=0;$j--){
        if($arr2[$j]>$p){
            $arr2[$j+1] = $arr2[$j];
        }else{
            break;
        }
    }
    $arr2[$j+1] = $p;
}

以上两种方式的代码，都能实现插入排序，但是在写完代码以后对这两种代码进行了一下测试，通过打印运行时间比较出第二种方式要比第一种方式运行的快，以下是运行5次得到的各自的运行时间（注：上面的是第一种情况，下面的是第二种情况）

通过以上时间对比其实想说明的就是，同样的算法，实现的方式不一样需要的时间就不一样，对于上面的测试数据只是简单的数字，快慢也不过是微秒级的。对于我们来说没有明显的差别，但是应用到项目中，对于复杂庞大的数据，一种好的实现方式可以为我们节省大量的时间。所以说即使是在学习原理的阶段，也应该尽可能的优化代码。

对于直接插入排序来说，不管是第一种的实现方式还是第二种的实现方式，他们的时间复杂度是相同的都是 O(n²)