专栏首页决胜机器学习PHP数据结构(二十五) ——并归排序

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),作者:linhxx

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-07-20

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    用户1327360
  • PHP数据结构(二十三) ——快速排序

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

    用户1327360
  • PHP实用功能——modern PHP读书笔记(一)

    PHP实用功能——modern PHP读书笔记 (原创内容,转载请注明来源,谢谢) 一、命名空间 1、命名空间按照虚拟的层次结构组织PHP代码,类似操作系统的目...

    用户1327360
  • PHP数据结构(二十二) ——快速排序

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

    用户1327360
  • PHP技能树—大神的进阶之路

    沈唁
  • PHP 霸主地位被动摇,JIT 是穷途末路后的绝地反击?

    TIOBE 2017 年度编程语言榜单已出炉,世界上最好的语言 PHP 再度无缘年度编程语言。

    猿哥
  • PHP的优势在哪?

    PHP(PHP: Hypertext Preprocessor的缩写,中文名:“超文本预处理器”)是一种通用开源脚本语言。语法吸收了C语言、Java和 Perl...

    云豹科技lk
  • PHP 霸主地位被动摇,JIT 是穷途末路后的绝地反击?

    关键时刻,第一时间送达! 摘要:PHP 是 Web 开发最常用的语言,自创建以来,PHP 语言经历了许多激烈的改进,其中性能是开发人员在评估新版本时考虑的主要标...

    企鹅号小编
  • 【问底】徐汉彬:PHP7和HHVM的性能之争

    【导读】徐汉彬曾在阿里巴巴和腾讯从事4年多的技术研发工作,负责过日请求量过亿的Web系统升级与重构,目前在小满科技创业,从事SaaS服务技术建设。最近,PHP7...

    CSDN技术头条
  • PHP 7终于发布:开发者会选择PHP 7吗?

    大家可以通过阅读本文,学习关于PHP7.0的五个方面的内容:PHP7.0简介、主要新特性、过去几周关于程序员是否采用php7.0的意愿调查结果、以上调查结果的分...

    CSDN技术头条

作者介绍

精选专题

活动推荐

扫码关注云+社区

领取腾讯云代金券