PHP数据结构（二十） ——其他插入排序
PHP数据结构（二十）——其他插入排序
（原创内容，转载请注明来源，谢谢）
注：本文是衔接直接插入排序的，因此直接插入排序的相关内容请点击——PHP数据结构（十八） ——直接插入排序。
一、概述
当数据量n较小时，直接插入排序是一个很好的方法。但是，当n较大时，采用直接插入排序，速度较慢，效果不好。其他插入排序主要是指折半插入排序、2-路插入排序、表插入排序，两者在直接插入排序的基础上，减少比较和移动的次数，以达到加快速度。
二、折半插入排序
直接插入排序中，当需要查找第i个值应该放于哪个位置时，是从最后一个位置开始逐个往前查找。
折半插入排序是改进这一内容，将查找改为二分法查找。因此，查找到元素后，仍需要逐个进行移动。
因此，折半插入排序的时间复杂度仍是O(n2)。
1、算法
折半插入排序，和直接插入排序，最大的区别在于排序过程中找到i要往哪里进行插入的问题。因此，算法也主要讲此部分，其他内容和直接插入排序相同。
1）前提：从小到大排序，0…i-1所对应的值已经从小到大排好，第i对应的值小于第i-1对应的值。
2）取几个中间变量，初始的时候，low为0，high为i-1。则此时中间下标middle为(low+high)/2，结果采用进一法。下列3、4只会发生一种。
3）如果middle对应的值小于i对应的值，则说明i对应的值会出现在middle+1至high下标范围内，因此重设low=middle+1。
4）如果middle对应的值大于i对应的值，则说明i对应的值会出现在0至middle-1下标范围内，因此重设high=middle-1。
5）重复上述步骤，直至high<low，则比较结束，此时middle对应的位置即为第i个值需要插入的位置。
6）将middle至i-1下标对应的结果分别往后挪一位，再把第middle位插入arr[i]。
7）继续比较，直至完成遍历整个数组。
2、核心代码如下：
//折半插入排序
publicfunction foldInsertSort(array $arr = array()){
$arr= $this->_checkNeedSort($arr);
if(!$arr){
return$arr;
}
//0...i-1都是有序的，此时插入第i个值
for($i=1;$i<count($arr);$i++){
//当第i个小于第i-1个时，需要进行插入排序，否则循环下一个数
if($arr[$i]< $arr[$i-1]){
//把第i个值往前挪到x位置，保证arr[x-1]<=arr[i],arr[x+1]>arr[i]
$tmp= $arr[$i];
//折半查找
$low= 0;
$high= $i-1;
while($low<= $high){
//折半排序，中间值为high-low除以2，进一法
//i的结果大于中间值的结果，由于i之前的数组都是有序的，则此时high改为中间值减一继续比较
//否则low改为中间值加一继续比较
$middle= ceil(($high+$low)/2);
if($tmp< $arr[$middle]){
$high= $middle -1;
}else{
$low= $middle +1;
}
}
for($j=$i-1;$j>=$high+1;$j--){
$arr[$j+1]= $arr[$j];//所有元素往后挪一位
}
//第j+1位赋值留给原来的第i位
$arr[$high+1] =$tmp;
}
}
return$arr;
}3、个人评价
由于直接插入排序，是在从后往前一边查找一边调整，而折半插入排序是先找到结果再挪动，因此对同一个需要排序的数组而言，挪动的次数不变，因此效率几乎没差。从时间复杂度都是O(n2)也能说明此问题。
三、2-路插入排序
由于折半插入排序所需要移动的次数于直接插入排序相比不变，性能提升不多，因此还需要对移动速度方面进行优化。2-路插入排序是在折半插入排序的基础上再进行改进，其主要就是减少移动的次数，但是需要n个记录的辅助空间。
1、算法
1）另设一个和原数组a同类型的数组b，将a的第一个元素a0复制给b，并且有两个记录first和final，分别记录当前最大值的位置和最小值的位置，初始时两个值都为0。下面2、3只会发生一种情况。
2）从a的第二个数字开始比较，如果数字大于a0，则插入在a0的后面，具体插入在哪个要根据a0后面的数字的大小决定。final加一。
3）如果小于a0，则插入在a0的前面，由于a0是数组d的第一个元素，因此将插入到d的末尾，而具体插入到哪个，也要根据实际情况。当first为0时，first赋值为数组长度-1；当first不是0时，first-1。
4）完成遍历所有数组后，再根据first和final将d数组还原成从小到大排序的数组。
2、实现源码
//2-路插入排序
publicfunction twoRoadInsertSort(array $arr = array()){
$arr= $this->_checkNeedSort($arr);
if(!$arr){
return$arr;
}
$arrLength= count($arr);//获取原数组长度，这也是辅助数组的长度
//构造辅助数组，并将第一个元素赋值为初始值
$arrTmp= array();
$arrTmp[0]= $arr[0];
$compareNum= $arrTmp[0];//设置比较的元素
$first= 0;
$final= 0;
for($i=1;$i<$arrLength;$i++){
//如果大于第一个元素
if($arr[$i]> $compareNum){
//有序的插入到辅助数组，从0...final找地方插入
for($j=$final;$j>0&& $arrTmp[$j]>$arr[$i] ;$j--){
$arrTmp[$j+1]= $arrTmp[$j];
}
$arrTmp[$j+1]= $arr[$i];
$final++;
}else{
//如果小于第一个元素，需要进行判断
//如果first为0，说明前面没有元素，直接在辅助数组末尾插入，并让first=arrlength即可
if(0== $first){
$arrTmp[$arrLength-1]= $arr[$i];
$first= $arrLength-1;
}else{
//否则，有序的从数组末尾插入数字
for($j=$first;$j<$arrLength&& $arrTmp[$j] < $arr[$i];$j++){
$arrTmp[$j-1]= $arrTmp[$j];
}
$arrTmp[$j-1]= $arr[$i];
$first--;
}
}
}
//将tmp数组挪回原数组
$k= 0;
//将第first至第arrlength-1的值赋给arr的第0至相应的位置
for($i=$first;$i<$arrLength;$i++){
$arr[$k++]= $arrTmp[$i];
}
//如果final<first，则还需要将第0至final的结果赋给arr的相应位置
if($final< $first){
for($i=0;$i<=$final;$i++){
$arr[$k++]= $arrTmp[$i];
}
}
return$arr;
}3、评价
2-路插入排序相比于直接插入、折半插入，有很大几率减少了移动的次数，把比第一个值大的和第一个值小的分开比较与移动，理论上减少了一半的移动。但是，如果选取的第一个值正好是整个数组的最大或者最小的元素，则此举失去意义，等于还是重新比较，而且还要另外占用一个存储空间。
四、表插入排序
上述几种插入排序，或多或少需要移动节点。表插入排序，可以完全避免移动节点。表查入排序，是将数组以链表的形式表示。由于链表的特性就是插入和删除非常方便，只需要修改相应的指针即可，因此此方法可以完全避免移动数据。该方法时间复杂度是O(n2)。
1、算法
1）构造一个节点，其含有几个元素，包括next指针指向下一个节点，data表示这个指针的值。构造一个头指针，其data为null，next指向把待排序的数组a的第一个元素a0所生成的节点。
2）依次取出2至最后一个元素，并且在指针链表中进行比较，如果不符合从小到大的排序，则修改指针的指向，保证其一直是从小到大的指向。
3）全部完成后，将指针从头节点开始逐个往后遍历链表，并把相应的data的值赋值给数组，即为排序后的结果。
2、实现源码
//表插入排序
publicfunction tableInsertSort(array $arr = array()){
$arr= $this->_checkNeedSort($arr);
if(!$arr){
return$arr;
}
//构造链表的头指针，并且初始指向数组的第一个元素
$head= new Node();
$head->next= new Node();
$head->next->data= $arr[0];
//从第二个元素开始遍历
for($i=1;$i<count($arr);$i++){
//设置临时指针等于头指针
$tmp= $head;
while(1){
//两种情况退出循环
//1.当前指针的下一个指针是null表示搜索到最后一个位置，则直接在链表最后加上新节点即可
if(null== $tmp->next){
$tmp->next= new Node();
$tmp->next->data= $arr[$i];
$hasCompare= true;
break;
}
//2.当下一个值要大于或者等于当前值，则把新值生成的节点插入在下一个值之前
if($tmp->next->data>= $arr[$i]){
$curTmp= $tmp->next;
$tmp->next= new Node();
$tmp->next->data= $arr[$i];
$tmp->next->next= $curTmp;
break;
}
//如果没有上述两个if，则临时指针指向下一个，继续循环
//因为tmp为null时必然进行处理，因此不会出现死循环的情况
$tmp= $tmp->next;
}
}
//遍历链表，把结果重新存入数组
$k= 0;
$tmp= $head->next;
while(null!= $tmp){
$arr[$k++]= $tmp->data;
$tmp= $tmp->next;
}
return$arr;
}3、评价
表插入排序仍是将数据插入到已经排列好的数组中，由于运用的是链表，因此不需要移动数据。但是，最终不能以链表的形式返回，否则很不灵活，不能进行二分查找等，因此还需要将结果转成数组的形式。
另外，该方式需要比较的关键字数目也相同。因此，其时间复杂度也还是O(n2)。
——written by linhxx 2017.07.17
相关阅读：