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

相关阅读:

PHP数据结构(十九) ——B+树

PHP数据结构(十八) ——直接插入排序

PHP数据结构(十七) ——内部排序综述

PHP数据结构(十六) ——B树

PHP数据结构(十五) ——哈希表​

PHP数据结构(十四) ——键树(双链树)

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十二) ——静态查找表​

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Educational Codeforces Round 21 D.Array Division(二分)

D. Array Division time limit per test:2 seconds memory limit per test:256 megaby...

31811
来自专栏云霄雨霁

字符串查找----三向单词查找树

1271
来自专栏软件开发 -- 分享 互助 成长

经典算法学习之分治法(以排列、组合程序为例)

分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归的求解这些子问题,然后再合并这些子问题的解来建立原问题的解。 分治法在每层递归是遵循的三个步...

1987
来自专栏技术换美食换不换

块状链表

的复杂度,而如果将整个块状链表维护成有序的,它甚至可以实现平衡树的一些操作[1],毕竟平衡树也可以看作是一种维护序列的方法。 又因为块状链表只在每个分块记录一...

612
来自专栏Python小屋

Python求解进制问题(阿里巴巴2015笔试题)

问题描述:用十进制计算30的阶乘,然后把结果转换成三进制表示,那么该进制表示的结果末尾会有多少个连续0? 解析:作为笔试题的话,要想按照题意先把阶乘结果计算出来...

3107
来自专栏程序生活

Leetcode-Easy 876. Middle of the Linked List

结题思路主要是通过快慢指针来找到中间节点:快指针的移动速度是慢指针移动速度的2倍,因此当快指针到达链表尾时,慢指针到达中点。

683
来自专栏移动开发面面观

快速排序法及优化

1254
来自专栏恰同学骚年

剑指Offer面试题:15.反转链表

  由于题目并没有要求必须原地反转,因此可以借助外部空间实现。这里可以将单链表储存为数组,然后按照数组的索引逆序进行反转。但是,此方式比较浪费空间,而且需要两次...

762
来自专栏C语言及其他语言

【编程经验】关于链表、还有编译器

关注我们 最近有小白来问VC6.0和其他编译器怎么下,小编回了一些,但是也是确实比较多......所以今天就不单单分享知识了,还要分享资源! ...

27910
来自专栏我的技术专栏

数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现

913

扫描关注云+社区