位置: 编程技术 - 正文

详解PHP归并排序的实现(详解php归并排序数据)

编辑:rootadmin

推荐整理分享详解PHP归并排序的实现(详解php归并排序数据),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:详解php归并排序数据,详解php归并排序数据,详解php归并排序的方法,归并排序python代码,php合并数组的方法,详解php归并排序函数,详解php归并排序数据,详解php归并排序数据,内容如对您有帮助,希望把文章链接给更多的朋友!

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表。归并排序的一个缺点是它需要存储器有另一个大小等于数据项数目的数组。如果初始数组几乎占满整个存储器,那么归并排序将不能工作,但是如果有足够的空间,归并排序会是一个很好的选择。

假设待排序的序列:

4 3 7 9 2 8 6

先说思路,归并排序的中心思想是将两个已经排序好的序列,合并成一个排序的序列。

上面的序列可以分成:

4 3 7 9和2 8 6

这两个序列,然后对这两个序列分别排序:结果为:

设置为序列A,与序列B,

3 4 7 6 8

将上面的两个序列 合并成一个排序好的序列:

合并的具体思路是:

设置两个位置指示器,分别指向序列A与序列B开始的位置:红色为指示器指向位置:

3 4 7 6 8

比较两个指示器所指向的元素的值,将较小的插入到一个新的数组内,例如序列C,同时将对应的指示器向后移动一位:结果为:

3 4 7 6 8

形成的序列C:已经被插入一个元素了,刚才较小的 元素2.2

然后 再次 比较序列A与序列B中指示器所指向的元素:将小的放入到序列C中,移动相应指针,结果为:

3 4 7 6 3

以此类推,迭代执行,直到序列A或者序列B中某个指示器已经移到到数组末端。例如:多次比较后,序列B已经将指示器移出到序列末端(最后一个元素之后)了。3 4 7 6 3 4 6 7 8

然后将没有用完的序列,这里面是序列A中其余的元素全部插入到序列C的后边即可,就剩下一个9 了,将其插入到序列C后即可:

序列C结果:

2 3 4 5 6 7 8 9

这样就实现了将两个有序序列合并成一个有序序列的操作,

详解PHP归并排序的实现(详解php归并排序数据)

下面先看这个合并的php代码:

经过上面的分析和程序的实现,我们不难发现,合并已排序的序列的时间应该是线性的,就是说,最多会发生N-1次比较,其中N是所有元素之和。

通过上面的描述,我们实现了将两个排序好的数组进行和并的过程。

此时,大家可能会有疑问,这个和归并排序整个序列有什么关系?或者你是如何能够得到最开始的两个排序好的子序列的呢?下面,我们就来描述以下什么是归并排序,然后再看,上面的合并与归并排序的关系是如何的:

大家不妨去想,当我们需要排序如下的数组时,我们是否可以先将数组的前半部分与数组的后半部分分别进行归并排序,然后将排序的结果合并起来呢?

例如:待排序的数组:4 3 7 9 2 8 6

先分成2部分:

4 3 7 8 6

将前半部分 与 后半部分 分别看成一个序列,再次进行归并(就是拆分,排序,合并)操作就会变成:

前:4 9

后:2 8 6

同样 再对每个自序列进行 归并排序,再次(拆分,排序,合并)。

当拆分的子序列内只存在一个元素(长度为1)时,那么这个序列就不必再拆分了,就是一个排序好的数组了。然后将这个序列,与其他的序列再合并到一起即可,最终就将所有的都合并好了,成为一个完整的排序好的数组。

程序实现:

通过上面的描述 大家应该想到,可以使用递归程序来实现这个程序设计吧:

想要实现这个程序,可能需要解决如下问题:

怎么将数组做拆分:

设定两个指示器,一个指向数组开始假定为$left,一个指向数组最后一个元素$right:4 3 7 9 2 8 6

然 后判断 $left 是否小于$right,如果小于,说明这个序列内元素个数大于一个,就将其拆分成两个数组,拆分的方式是生成一个中间的指示器$center,值 为$left + $right /2 整除。结果为:3,然后将$left 到$center 分成一组,$center+1到$right分成一组:4 3 7 8 6接下来,递归的 利用$left, $center, $center+1, $right分别做为 两个序列的 左右指示器,进行操作。知道数组内有一个元素$left==$right .然后按照上面的合并数组即可:

注意上面的代码带排序的数组都使用的是 引用传递,为了节约空间。

而且,其中的合并数组的方式也为了节约空间做了相对的修改,把所有的操作都放到了$arr上完成,引用传递节约资源。

好了 上面的代码就完成了归并排序,归并排序的时间复杂度为O(N*LogN) 效率还是相当客观的。

再说,归并排序算法,中心思想是 将一个复杂问题分解成相似的小问题,再把小问题分解成更小的问题,直到分解到可以马上求解为止,然后将分解得到的结果再合并起来的一种方法。这个思想用个 成语形容叫化整为零。 放到计算机科学中有个专业属于叫分治策略(分治发)。分就是大问题变小问题,治就是小结果合并成大结果。

分治策略是很多搞笑算法的基础,我们在讨论快速排序时,也会用到分治策略的。

最后简单的说一下这个算法,虽然这个算法在时间复杂度上达到了O(NLogN)。但是还是会有一个小问题,就是在合并两个数组时,如果数组的总元素个数为 N,那么我们需要再开辟一个同样大小的空间来保存合并时的数据(就是mergeArray中的$temp数组),而且还需要将数据有$temp拷贝 会$arr,因此会浪费一些资源。因此在实际的排序中还是 相对的较少使用。

Yii统计不同类型邮箱数量的方法 本文实例讲述了Yii统计不同类型邮箱数量的方法。分享给大家供大家参考,具体如下:效果图:控制器://查询邮箱publicfunctionactionEmail(){/*//查询所有邮

Yii实现文章列表置顶功能示例 本文实例讲述了Yii实现文章列表置顶功能的方法。分享给大家供大家参考,具体如下:我的理解:首先点击获取当前ID,model层查询所有sort字段,遍历数

PHP实现文件上传下载实例 本文介绍了PHP实现文件上传与下载,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧。一、上传原理与配置1.1原理将客户端文件上传

标签: 详解php归并排序数据

本文链接地址:https://www.jiuchutong.com/biancheng/301970.html 转载请保留说明!

上一篇:Yii框架中sphinx索引配置方法解析(yii框架教程)

下一篇:Yii统计不同类型邮箱数量的方法(统计不同类型的数量)

  • 什么是进项税额转出
  • 财税咨询
  • 房地产企业递延所得税资产计算方法
  • 企业购买电话充值卡的分录
  • 境外非居民企业所得税
  • 购买了材料怎么做账
  • 个人资金借给企业
  • 民办职业技能培训学校办学许可证
  • 房地产开发企业预缴增值税
  • 汇算清缴职工福利支出
  • 税务年检流程
  • 委托加工的账务处理
  • 复式记账法和会计分录
  • 研发新产品成功案例简短
  • 个人出租住房缴纳个税可以扣除房产税吗
  • 不预缴会怎么样
  • 以公允价值模式后续计量的投资性房地产无须计提减值
  • 应收账款的贷方反映
  • 1697510840
  • 法院扣款图片
  • 购入土地建厂房要交的税
  • 非上市公司转让股权需要缴纳增值税吗
  • PHP+Mysql+jQuery查询和列表框选择操作实例讲解
  • u盘如何装系统win7
  • 职工教育经费怎么记账
  • 存货报废会计分录例题
  • 一台电脑两个显示器显示不一样的内容
  • 房产权利转移
  • 车辆违章罚款的钱上交到那了
  • 外汇业务的核算ppt
  • 权益法转成本法为什么用账面价值
  • php 可变变量
  • yii2框架中文手册
  • 矿产资源补偿费与采矿权价款区别
  • 中秋快乐图片大全
  • 提交表单后重定向
  • php代码用什么工具
  • 待转销销项税额是什么
  • 增值税留抵税额计入什么科目
  • 银行承兑汇票贴现分录
  • 现金流量表哪些数据和资产负债表一致
  • vue elementui table
  • php安装不了
  • 大气污染物排放2020标准
  • sqlserver2008误操作数据
  • 旅游门票费用可以用来报销吗?
  • 坏账准备的账务处理例题视频讲解
  • 物流公司进项包括什么
  • 航天信息服务费280元会计处理
  • 长期股权投资收益要交企业所得税吗
  • 企业所得税和个人所得税怎么算
  • 个人餐饮费发票
  • 税前弥补以前年度亏损
  • 固定资产清理后折旧怎么处理
  • 什么是委托检验报告
  • 政府补贴收入的账务处理
  • 将本月应交未交增值税转入未交增值税
  • 投标保证金分为几种
  • 收到先征后返的增值税计入哪里
  • 高新技术企业进项税加计扣除10%如何填企业所得税季报
  • 个人垫付的费用如何向单位报销行政单位
  • 附加税减半征收从什么时候开始
  • 负数发票要交税吗
  • 长期待摊费用是当月摊销还是次月摊销
  • 建立新公司需要做什么
  • sql游标用法
  • 低配置装什么系统
  • ubuntu选择语言
  • wincomm.exe - wincomm是什么进程
  • win10控制面板中没有防火墙
  • macbook看视频卡顿
  • win7开始菜单在哪个文件夹
  • explore.exe是什么意思
  • centos开机grub
  • linux windows转linux
  • windows7 usb
  • node.js安装后自带哪个工具
  • 基于arcgis的python编程
  • javascript如何
  • 税务实名认证如何操作
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设