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

相关文章

来自专栏技术墨客

React——Fragments特性 转

在我们使用React开发组件的时候,每个React组件都必须返回一个根元素。例如下面这样:

711
来自专栏hbbliyong

c++ list, vector, map, set 区别与用法比较

List封装了链表,Vector封装了数组, list和vector得最主要的区别在于vector使用连续内存存储的,他支持[]运算符,而list是以链表形式实...

5779
来自专栏决胜机器学习

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

PHP数据结构(二十三)——选择排序 (原创内容,转载请注明来源,谢谢) 一、概述 选择排序的基本思想,是每一趟在n-i+1(i=1,2…n-1)个记录中选...

3418
来自专栏来自地球男人的部落格

[LeetCode] 78. Subsets

【原题】 Given a set of distinct integers, nums, return all possible subsets. Not...

2229
来自专栏mathor

C++STL中set的使用策略(二)

663
来自专栏CDA数据分析师

超能教程 十分钟学会 Python!

假设你希望学习Python这门语言,却苦于找不到一个简短而全面的入门教程。那么本教程将花费十分钟的时间带你走入Python的大门。本文的内容介于教程(Totur...

1866
来自专栏趣学算法

数据结构 第1讲 基础知识

        著名的瑞士科学家N.Wirth教授提出:数据结构+算法=程序。数据结构是程序的骨架,算法则是程序的灵魂。

513
来自专栏Google Dart

AngularDart4.0 高级-属性(Attribute)指令 顶

结构指令改变了视图的结构。 两个例子是NgFor和NgIf。 在“结构指令”页面中了解它们。

611
来自专栏大数据挖掘DT机器学习

Python爬虫(urllib2+bs4)数据采集:分析找出百度贴吧谁是水贴王

问题描述 ? 对于这个题目, 书上给出了三种思路 第一种 : 先遍历一次所有的帖子, 统计出 <发帖人, 发帖次数>, 然后在遍历一次映射, 找出发帖次数超...

3165
来自专栏Aloys的开发之路

ACM竞赛之输入输出(以C与C++为例)

本文转自互联网,内容、排版有修正。 在ACM程序设计竞赛中,一道题目的所有测试数据是放在一个文本文件中,选手将一道题目的程序提交给评判系统运行,程序从该文件中读...

2455

扫描关注云+社区