PHP数据结构(二十五) ——并归排序

PHP数据结构(二十五)——并归排序

(原创内容,转载请注明来源,谢谢)

一、概述

并归排序是将两个或两个以上的有序表组合成一个新的有序表。采用并归的思想进行排序的方式如下:

假设初始序列含有n个记录,则看成是n个有序的子序列,每个子序列长度是1,然后两两合并,得到n/2个长度为2或者1(元素总数是奇数时,最后一个元素是单个的)的子序列。然后再进行归并,直至归并成一个数组。此方法也成为2-路并归排序。

二、算法

并归排序有两个核心——拆分、合并。

1)对于拆分,需要把数组拆成仅含一个元素的数组。

2)对于合并,两两合并的过程中再进行排序。

三、程序实现过程

1)获取数组,取数组长度的一半作为中间值,将数组分割成两部分。并用递归的方式将数组拆成更小的模块。直到数组都是一个元素。

2)将数组递归合并,边合并边进行比较,确保合并后的数组是从小到大排好序的数组,合并后返回给上一层。

四、并归排序图(图片来自网络)

五、实现源程序

                  //并归排序
         publicfunction mergeSortArray(array $arr = array()){
                   if(empty($arr)){
                            $arr= $this->arr;
                   }
                   $arrLength= count($arr);
                   //长度只有1直接返回
                   if(1>= $arrLength){
                            return$arr;
                   }
                   //取中间值作为下标
                   $middle= floor($arrLength/2);
                   //分割出左数组,从0到中间
                   $arrLeft= array_slice($arr, 0, $middle);
                   //分割出右数组,从中间到最后
                   $arrRight= array_slice($arr, $middle, $arrLength-1);
                   //采用递归的方式进行分割
                   $arrLeft= $this->mergeSortArray($arrLeft);
                   $arrRight= $this->mergeSortArray($arrRight);
                   $arr= $this->_mergeSplitedArray($arrLeft, $arrRight);
                   return$arr;
         }
         //并归排序的私有方法,将两个数组有序合并
         publicfunction _mergeSplitedArray(array $arrLeft, array $arrRight){
                   $arrRes= array();
                   $leftIndex= 0;
                   $rightIndex= 0;
                   //遍历数组,合成最终的数组
                   while($leftIndex< count($arrLeft) && $rightIndex < count($arrRight)){
                            //如果左边小,则取左边的值,并把左边的下标加一。否则取右边的值,并把右边的下标加一。
                            $arrRes[]= $arrLeft[$leftIndex] < $arrRight[$rightIndex] ? $arrLeft[$leftIndex++] :$arrRight[$rightIndex++];
                   }
                   //将其中一边数组剩余的结果合并进来,下面两个while会执行其中一个
                   while($leftIndex< count($arrLeft)){
                            $arrRes[]= $arrLeft[$leftIndex++];
                   }
                   while($rightIndex< count($arrRight)){
                            $arrRes[]= $arrRight[$rightIndex++];
                   }                
                   return$arrRes;
         }

——written by linhxx 2017.07.20

相关阅读:

PHP数据结构(二十四) ——堆排序

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

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

PHP数据结构(二十一) ——希尔排序

PHP数据结构(二十) ——其他插入排序

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-20

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏拭心的安卓进阶之路

Android 框架学习2:源码分析 EventBus 3.0 如何实现事件总线

Go beyond yourself rather than beyond others. 上篇文章 深入理解 EventBus 3.0 之使用篇 我们了解了 ...

3795
来自专栏曾大稳的博客

Android EventBus3.0源码分析

在我们开发过程中,相信应该有很多人使用过EventBus 3.0,这个确实方便了我们,少些了很多代码,这是个优秀的库,我们接下来进行对他剖析。 我们使用Even...

621
来自专栏Android中高级开发

Android开发之漫漫长途 Ⅶ——Android消息机制(Looper Handler MessageQueue Message)

该文章是一个系列文章,是本人在Android开发的漫漫长途上的一点感想和记录,我会尽量按照先易后难的顺序进行编写该系列。该系列引用了《Android开发艺术探索...

762
来自专栏码匠的流水账

修复zuul跨域配置异常

多次请求的时候,会把这些header再带过来,然后请求zuul转发的接口又在写入一次,造成重复了,方案就是zuul转发的时候,过滤掉这些header,比如

712
来自专栏小灰灰

Greenrobot-EventBus源码学习(四)

EventBus 深入学习四之实例&类说明 本篇开始,则转向greenrobot/EventBus, 之前基本上将Guava中设计的思路捋了一遍,逻辑比较简...

2789
来自专栏汪毅雄的专栏

深入理解 Android 消息机制原理

本文讲述的是 Android 的消息机制原理,从 Java 到 Native 代码进行了梳理,并结合其中使用到的Epoll模型予以介绍。

5943
来自专栏技术小黑屋

Android中检测当前是否为主线程

如果在Android中判断某个线程是否是主线程?对于这个问题,你可能说根据线程的名字,当然这个可以解决问题,但是这样是最可靠的么?万一某天Google一下子将线...

723
来自专栏开发之途

Handler、Looper与MessageQueue源码解析

945
来自专栏拭心的安卓进阶之路

Android 进阶14:源码解读 Android 消息机制( Message MessageQueue Handler Looper)

不要心急,一点一点的进步才是最靠谱的。 前言 本来我以为自己很了解 Handler,在印象中 Android 消息机制无非就是: Handler 给 Messa...

2109
来自专栏小灰灰

Greenrobot-EventBus源码学习(六)

EventBus 深入学习六之消息发送 消息推送 发布消息的业务方没有限制,任何人,可以在任何地方,任何时间推送一条消息(或者说触发一个自定义事件) 代码一览...

1739

扫码关注云+社区