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
相关阅读: