位置: 编程技术 - 正文
详解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代码：
经过上面的分析和程序的实现，我们不难发现，合并已排序的序列的时间应该是线性的，就是说，最多会发生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 转载请保留说明！
