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 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

PHP数据结构(二十二) ——快速排序

PHP数据结构(二十二)——快速排序 (原创内容,转载请注明来源,谢谢) 一、概述 前面的插入排序,都是以移动的方式进行排序。快速排序,则是以交换的方式进行...

3619
来自专栏醒者呆

正则表达式——Java程序员懂你

正则表达式 关键字:正则表达式,Pattern,Matcher,字符串方法,split,replace 前文书立下了一个flag,这里要把它完成,就是正则...

3445
来自专栏C/C++基础

C++编码格式建议

每个人都可能有自己的代码风格和格式,但如果一个项目中的所有人都遵循同一风格的话,这个项目就能更顺利地进行。每个人未必能同意下述的每一处格式规则,而且其中的不少规...

712
来自专栏轻扬小栈

[半zz]迅雷笔试题

1323
来自专栏小樱的经验随笔

【Java学习笔记之十一】Java中常用的8大排序算法详解总结

分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基...

3016
来自专栏菩提树下的杨过

数据结构与算法C#版笔记--排序(Sort)-上

这里讨论的仅限于内部排序(即全部数据都在内存中,通过CPU运算处理元素排序),而且仅限顺序表排序(即不讨论链表,树状结构等结构的排序) 注:排序后的结果可以从小...

20110
来自专栏小樱的经验随笔

python学习笔记之运算符

目录 前言 软件环境 身份运算符 算术运算符 比较运算符 位移运算符 自变运算符 位运算符 逻辑运算符 成员关系运算符 Python真值表 最后 前言 在前面的...

2583
来自专栏软件开发

JavaScript学习总结(一)——ECMAScript、BOM、DOM(核心、浏览器对象模型与文档对象模型)

一、JavaScript简介 JavaScript是一种解释执行的脚本语言,是一种动态类型、弱类型、基于原型的语言,内置支持类型,它遵循ECMAScript标准...

1977
来自专栏软件开发

JavaScript学习总结(一)——ECMAScript、BOM、DOM(核心、浏览器对象模型与文档对象模型)

JavaScript是一种解释执行的脚本语言,是一种动态类型、弱类型、基于原型的语言,内置支持类型,它遵循ECMAScript标准。它的解释器被称为JavaSc...

1184
来自专栏CDA数据分析师

算法和数据结构—— 查找和排序

本文为简书作者郑永欣原创,CDA数据分析师已获得授权 查找和排序都是程序设计中经常用到的算法。查找相对而言较为简单,不外乎顺序查找、二分查找、哈希表查找和二叉排...

2006

扫码关注云+社区