迹忆客 专注技术分享

本篇承接 插入排序（概念篇） 奉上折半插入排序的实现步骤以及实现代码

折半插入排序算法步骤

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($arr);$i++){
    if($arr[$i]<$arr[$i-1]){
        //使用二分查找法查找适当的位置
        $low = 0;
        $high = $i-1;
        $pos = floor(($low+$high)/2);
        $key = $arr[$i];
        while($low<$high){
            if($arr[$pos]>$key){
                $high = $pos-1;
            }elseif($arr[$pos]<=$key){
                $low = $pos+1;
            }
            $pos = floor(($low+$high)/2);
        }
        //二分查找法结束
        if($arr[$pos]>$arr[$i]){
            $pos = $pos-1;
        }
        for($j=$i-1;$j>$pos;$j--){
            $arr[$j+1]=$arr[$j];
        }
        $arr[$j+1] = $key;
    }
}

以上就是折半插入排序的实现代码，从代码中我们可以看到其不同于直接插入排序的地方只是查找位置的那一段代码，其它的地方都是相同的。折半插入排序需要移动的元素是和直接插入排序相同的。因此其时间复杂度也是O(n²)。

但是进一步分析可知，即使两者的时间复杂度是相同的，但是整体上折半插入排序要比直接插入排序快一些。下面是我做的一段测试（这里需要的数据就不能是上面代码中的那一点数据了，在这里我构造了100条数据的数组用于测试）

$arr = 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,36,57,1334,5567,4432,11178,9997,88851,
4449,33332,9992,76853,67434,1239,98716,5349,90718,3589,213450,6754,24,
562,77,16,127,361,572,13343,55674,44325,1117,99979,88850,44491,3333,99923,
7685,6743,12395,9871,53497,9071,35899,21345,67541,24,56,774,16,127,111,112,
113,114,115,116,117,118,119,110,101,102,103,104,105,106,107,108,109,1000);

直接插入排序的代码是使用的下面这一段

for($i=1;$i<count($arr);$i++){
    $p = $arr[$i];
    for($j=$i-1;$j>=0;$j--){
        if($arr[$j]>$p){
            $arr[$j+1] = $arr[$j];
        }else{
            break;
        }
    }
    $arr[$j+1] = $p;
}

基于同一组数据，然后分别运行这两段代码多次，分别记录各自所用的时间，下面是每次的时间对比，上面的是折半插入排序，下面的是直接插入排序。我们可以做一下对比

从上面的几次对比中可以发现折半插入所需的时间是比直接插入所需的时间短，数据量越大这两种方式的时间差越明显，因此在实际的项目中，如果我们真的需要使用插入排序算法，我个人建议使用折半插入排序，可能折半插入在空间的使用上面并不优于直接插入，因为折半插入需要借助的其它的变量较多于直接插入，所以当我们只有几十条数据的时候，再次运行上面两段代码，你会惊奇的发现前者（折半插入）的时间竟然要比后者（直接插入）的时间长，这是因为这么多的变量需要为其分配内存，其所花费的时间在整个运行过程中占的比例很大，所以前者的时间要比后者时间长，但是随着数据量的增多，渐渐的为变量分配内存的时间占得比重越来越小几乎可以忽略，因此数据量大的时候前者的时间比后者时间要短。而且以现在的硬件水平，在本人看来时间的优势可以弥补空间的相对不足。如果实际情况中我们的数据量真的达到时间的优势已经无法弥补空间的地步，那么也还有其它的排序算法供我们选择。