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

相关文章

来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第3章 Python的数据结构、函数和文件3.1 数据结构和序列3.2 函数3.3 文件和操作系统3.4 结论

本章讨论Python的内置功能,这些功能本书会用到很多。虽然扩展库,比如pandas和Numpy,使处理大数据集很方便,但它们是和Python的内置数据处理工具...

4606
来自专栏函数式编程语言及工具

泛函编程(5)-数据结构(Functional Data Structures)

     编程即是编制对数据进行运算的过程。特殊的运算必须用特定的数据结构来支持有效运算。如果没有数据结构的支持,我们就只能为每条数据申明一个内存地址了,然后使...

2096
来自专栏Java后端技术

这个坑,是时候填上了~

​  这两天,在网上逛的时候,发现了如下的一道面试题,感觉还有蛮有意思的,要是不仔细看还真容易掉到坑里面。第一眼看起来比较绕,所以比较难理解。最终我跳出了这个坑...

671
来自专栏日常学python

爬虫必学知识之正则表达式下篇

这是日常学python的第13篇原创文章 继上篇文章说了正则表达式的简单用法,那今天我们就继续说一下正则表达式的复杂的用法。好了,废话不多说,直接进入正题。 正...

5617
来自专栏有趣的Python

慕课网-Linux C语言结构体-学习笔记

Linux C语言结构体 编译指令:预处理,宏定义, 建立自己的数据类型:结构体,联合体,动态数据结构 逻辑运算符:& | ^ ~ << >> 递归函...

4538
来自专栏老九学堂

2016Java面试题与答案——集合专题(一)

Java集合框架作为Java编程语言的基础,也是Java面试中很重要的一个知识点,不管是学习还是为了入职,这一块都应该被小伙伴们充分重视,老九君列出了一些关于J...

3494
来自专栏向治洪

模板方法模式

概述 概念:定义一个操作中算法的框架,而将一些步骤延迟到子类中,使得子类可以不改变算法的结构即可重定义该算法中的某些特定步骤。模板方法模式属于行为类模式。 模板...

1997
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day10-基础题-继承;抽象类

Java基础-day10-基础题-继承&抽象类 什么是继承?继承有什么好处? 继承是面向对象最显著的一个特性。继承是从已有的类中派生出新的类,新的类能吸收已有类...

3626
来自专栏轮子工厂

3. C语言 -- 叫你一声你敢答应嘛

\(@^0^@)/ 嗨!大家好,我是呆博~前两天的文章还满意嘛,如果有不满意的地方尽管提,我一定……嗯……能做到的我一定做。今天准备给大家分享第三篇文章,变量与...

1155
来自专栏数据结构与算法

1470 数列处理

个人博客:doubleq.win 1470 数列处理  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

2715

扫码关注云+社区