全面分析插入排序的三种插入方式

何谓‘插入排序’？其概念如是说：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中，直到全部记录插入完成为止。

概念的东西总是有些抽象，也可称其为基本思想。上述插入排序的概念同样也可说是插入排序的基本思想。抽象的东西理解起来总是有些困难，因此这里需要的是将抽象的概念具体化。

我们不妨将其转换成整队问题：开始会有两队，其中一队是按从低到高的顺序排列的，将其命名为A队。另一队是无序的，将其命名为B队。如下图：

现在把B队的第一个人（不妨称其为jack）放到A队中，并且保持A队依然是有序的，为了保持A队依然有序就需要在A队中找一个适当的位置给jack，这个位置前面的人要比jack矮，后面的人要比jack高。现在就可以让jack站到这个位置上面，此时A中依然有序。

然后再把B队的第二个人（称其为tom）放到A队，方式和jack相同，要保证A队依然有序。

依次类推直到B队的人全部站到A队当中。到此为止，两队合成了一队，而且这一队是有序的。

看到这对插入排序应该有一个比较清晰的认识了。但是这里还存在着一个疑问，排序问题是对一个队列进行排序，何来的两队呢。我们不妨再来转换一下，起初的时候A、B两队站在同一列，并且A队整体在B队前面，并且A队是一个人。对于一个人的队列肯定是有序的。

然后再向代码方面靠近一下，不妨将A、B两队映射成数组。有这样一个数组

其中 3 就表示刚开始的A队，5、2…. 表示刚开始的B队。而5 就是 Jack， 2 就是Tom。

我当时学习插入排序的时候就是按照这个思路来理解的。到这里我对插入排序的思想基本上已经完全掌握了。

思想的东西转换成代码，不同的方式也会产生不同的‘派系’。好比《春秋经》读起来总是有些难懂，这时就有人出来为春秋作传，不同的人作出来的传也是不同的，有《左传》，有《公羊传》，有《谷梁传》。虽然有所不同，但是整体都是传承的《春秋》的思想。

现在回到我们的插入排序上来，既然思想的东西都已经明了了，无非就是实现方式的差别。关键的地方还是在于A队，当在A队为B队的人查找适当位置的时候，查找的方式有很多种。
1、每次开始从头遍历查找位置称其为直接插入排序
2、用二分法查找位置称其为二分插入排序/折半插入排序

以上两种方式都是在一个队列中查找和移动元素，主要时间花费在查找和移动两个方面。
还有第三种方式就是借助额外的队列，来做一个映射，这样可以省去了移动所花费的时间。
就是用空间换时间的做法，这种方式被称为：
3、表插入排序

下面我们分别看一下三种方式的实现代码

一、直接插入排序

实现步骤：

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

$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;
}

二、折半插入排序

折半插入排序算法步骤

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

$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;
    }
}

三、表插入排序

表插入排序，顾名思义，借助一个索引表对原表进行插入排序，这样做的好处就是省去了对原来表中元素的移动过程。当然单一的整数数组（仅作为试验用）移动元素也是挺方便的，但是对于结构有些复杂的表来说，要想移动表中的元素那可真真不是一件容易的事情了。举个例子（以下PHP中的二维数组）

$link = array();  //链表
 
   $link[0]=array('next'=>1);//初始化链表  $link第一个元素仅仅作为头部
 $link[1]=array('next'=>0); //将第一个元素放入$link
/*
  * 开始遍历数组 从第二个元素开始
  */
 for($i=2;$i<=count($arr);$i++){
     $p = $arr[$i]; //存储当前待排序的元素
     $index =0;
     $next = 1;  //从开始位置查找链表
     while($next!=0){
         if($arr[$next]['age']<$p['age']){
             $index = $next;
             $next = $link[$next]['next'];
         }
         else break;
     }
     if($next == 0){
         $link[$i]['next'] = 0;
         $link[$index]['next'] = $i;
     }else{
         $link[$i]['next']=$next;
         $link[$index]['next']=$i;
     }
 }

以上是三种插入排序的简单步骤及实现代码，详细的介绍可以参考下面三篇文章

全面分析插入排序的三种插入方式

推荐阅读