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

相关文章

来自专栏数据库新发现

php中几个字符处理函数的说明

使用字符串 dellimiter 把 data 分割成一个数组返回 类似函数:split()

962
来自专栏企鹅号快讯

JAVA核心技术学习笔记

掌握Java核心技术是学习和掌握好Java技术的关键,下边分17个点对这些Java核心技术进行讲解。 >>>1.Java中没有多继承,而是用接口来代替多继承 >...

1875
来自专栏决胜机器学习

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

PHP数据结构(二十一)——希尔排序 (原创内容,转载请注明来源,谢谢) 一、概述 希尔排序,又称缩小增量排序,也属于插入排序类方法,时间上有较大改进。前面...

3377
来自专栏Vamei实验室

Python基础05 缩进和选择

缩进 Python最具特色的是用缩进来标明成块的代码。我下面以if选择结构来举例。if后面跟随条件,如果条件成立,则执行归属于if的一个代码块。 先看C语言的表...

1879
来自专栏我是业余自学C/C++的

vector

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

【C#学习笔记之一】C#中的关键字

C#中的关键字 关键字是对编译器具有特殊意义的预定义保留标识符。它们不能在程序中用作标识符,除非它们有一个 @ 前缀。例如,@if 是有效的标识符,但 if 不...

4344
来自专栏猿人谷

memcpy的函数

网新恒天2014校园招聘笔试编程题 已知memcpy的函数为: void* memcpy(void *dest , const void* src , s...

2068
来自专栏Python小屋

Python组合列表中多个整数得到最小整数(一个算法的巧妙实现)

'''程序功能: 给定一个含有多个整数的列表,将这些整数任意组合和连接, 返回能得到的最小值。 代码思路: 将这些整数变为相同长度(按最...

3296
来自专栏沈唁志

PHP中系统函数http_build_query系统函数使用方法

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

javascript中function调用时的参数检测常用办法

1.方法重载 js中并不直接支持类似c#的方法重载,所以只能变相的来解决,示意代码:(利用了内置属性arguments) var f1 = function(p...

2068

扫码关注云+社区